A greedy block Kaczmarz algorithm for solving large-scale linear systems

Kaczmarz, 1937, Angenäherte auflösung von systemen linearer gleichungen, Bull. Int. Acad. Polon. Sci. Lett. A, 35, 355 Gordon, 1970, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theoret. Biol., 29, 471, 10.1016/0022-5193(70)90109-8 Popa, 2004, Kaczmarz extended algorithm for tomographic image reconstruction from limited-data, Math. Comput. Simulation, 65, 579, 10.1016/j.matcom.2004.01.021 Eggermont, 1981, Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Linear Algebra Appl., 40, 37, 10.1016/0024-3795(81)90139-7 McCormick, 1975, An iterative procedure for the solution of constrained nonlinear equations with application to optimization problems, Numer. Math., 23, 371, 10.1007/BF01437037 Ansorge, 1984, Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations, Computing, 33, 367, 10.1007/BF02242280 Strohmer, 2009, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 262, 10.1007/s00041-008-9030-4 Leventhal, 2008, Randomized methods for linear constraints: Convergence rates and conditioning, Math. Oper. Res., 35, 641, 10.1287/moor.1100.0456 Zouzias, 2012, Randomized extended Kaczmarz for solving least squares, SIAM J. Matrix Anal. Appl., 34, 773, 10.1137/120889897 Ma, 2015, Convergence properties of the randomized extended Gauss–Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36, 1590, 10.1137/15M1014425 Du, 2019, Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss–Seidel algorithms, Numer. Linear Algebra Appl., 26, 10.1002/nla.2233 Bai, 2018, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40, A592, 10.1137/17M1137747 Elfving, 1980, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35, 1, 10.1007/BF01396365 Needell, 2014, Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441, 199, 10.1016/j.laa.2012.12.022 Needell, 2015, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484, 322, 10.1016/j.laa.2015.06.027 J. Nutini, B. Sepehry, I. Laradji, M. Schmidt, H. Koepke, A. Virani, Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph, Jersey City, New Jersey, USA, 2016, pp. 547–556. Eldar, 2011, Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss lemma, Numer. Algorithms, 58, 163, 10.1007/s11075-011-9451-z Björck, 1996, 269 Davis, 2011, The university of florida sparse matrix collection, ACM Trans. Math. Software, 38, 1