Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph
From MaRDI portal
Publication:6281186
arXiv1612.07838MaRDI QIDQ6281186FDOQ6281186
Authors: Julie Nutini, Behrooz Sepehry, Issam Laradji, Mark Schmidt, Hoyt A. Koepke, Alim Virani 
Publication date: 22 December 2016
Abstract: The Kaczmarz method is an iterative algorithm for solving systems of linear equalities and inequalities, that iteratively projects onto these constraints. Recently, Strohmer and Vershynin [J. Fourier Anal. Appl., 15(2):262-278, 2009] gave a 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 in many 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 pairwise-orthogonal rows.
Has companion code repository: https://github.com/jdmoorman/kaczmarz-algorithms
Computational methods for sparse matrices (65F50) Iterative numerical methods for linear systems (65F10)
This page was built for publication: Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281186)
