Convergence Rates for Greedy Kaczmarz Algorithms, and Randomized Kaczmarz Rules Using the Orthogonality Graph

Julie Nutini, Behrooz Sepehry, Issam Laradji, Mark Schmidt, Hoyt Koepke Dato, Alim Virani
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:218-227, 2016.

Abstract

The Kaczmarz method is an iterative algorithm for solving systems of linear equalities and inequalities that iteratively projects onto the constraints. Recently, Strohmer and Vershynin [J. Fourier Anal. Appl., 15(2):262-278, 2009] gave the first non-asymptotic convergence rate analysis for this algorithm, spurring numerous extensions and generalizations of the Kaczmarz method. Rather than the randomized selection rule analyzed in that work, in this paper we instead discuss greedy and approximate greedy selection rules. We show that in some applications the computational costs of greedy and random selection are comparable, and that (except in extreme cases) greedy selection rules give faster convergence rates than random selection rules. Further, we give the first multi-step analysis of Kaczmarz methods for a particular greedy rule, and propose a provably-faster randomized selection rule for matrices with many orthogonal rows.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-nutini16a, title = {Convergence Rates for Greedy Kaczmarz Algorithms, and Randomized Kaczmarz Rules Using the Orthogonality Graph}, author = {Nutini, Julie and Sepehry, Behrooz and Laradji, Issam and Schmidt, Mark and Dato, Hoyt Koepke and Virani, Alim}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {218--227}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/nutini16a/nutini16a.pdf}, url = {https://proceedings.mlr.press/r14/nutini16a.html}, abstract = {The Kaczmarz method is an iterative algorithm for solving systems of linear equalities and inequalities that iteratively projects onto the constraints. Recently, Strohmer and Vershynin [J. Fourier Anal. Appl., 15(2):262-278, 2009] gave the first non-asymptotic convergence rate analysis for this algorithm, spurring numerous extensions and generalizations of the Kaczmarz method. Rather than the randomized selection rule analyzed in that work, in this paper we instead discuss greedy and approximate greedy selection rules. We show that in some applications the computational costs of greedy and random selection are comparable, and that (except in extreme cases) greedy selection rules give faster convergence rates than random selection rules. Further, we give the first multi-step analysis of Kaczmarz methods for a particular greedy rule, and propose a provably-faster randomized selection rule for matrices with many orthogonal rows.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Convergence Rates for Greedy Kaczmarz Algorithms, and Randomized Kaczmarz Rules Using the Orthogonality Graph %A Julie Nutini %A Behrooz Sepehry %A Issam Laradji %A Mark Schmidt %A Hoyt Koepke Dato %A Alim Virani %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-nutini16a %I PMLR %P 218--227 %U https://proceedings.mlr.press/r14/nutini16a.html %V R14 %X The Kaczmarz method is an iterative algorithm for solving systems of linear equalities and inequalities that iteratively projects onto the constraints. Recently, Strohmer and Vershynin [J. Fourier Anal. Appl., 15(2):262-278, 2009] gave the first non-asymptotic convergence rate analysis for this algorithm, spurring numerous extensions and generalizations of the Kaczmarz method. Rather than the randomized selection rule analyzed in that work, in this paper we instead discuss greedy and approximate greedy selection rules. We show that in some applications the computational costs of greedy and random selection are comparable, and that (except in extreme cases) greedy selection rules give faster convergence rates than random selection rules. Further, we give the first multi-step analysis of Kaczmarz methods for a particular greedy rule, and propose a provably-faster randomized selection rule for matrices with many orthogonal rows. %Z Reissued by PMLR on 04 October 2026.
APA
Nutini, J., Sepehry, B., Laradji, I., Schmidt, M., Dato, H.K. & Virani, A.. (2016). Convergence Rates for Greedy Kaczmarz Algorithms, and Randomized Kaczmarz Rules Using the Orthogonality Graph. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:218-227 Available from https://proceedings.mlr.press/r14/nutini16a.html. Reissued by PMLR on 04 October 2026.

Related Material