Randomized Kaczmarz converges along small singular vectors

S. Kaczmarz, Stefan, Angenaherte Auflosung von Systemen linearer Gleichungen, Bulletin International de l’Academie Polonaise des Sciences et des Lettres. Classe des Sciences Mathematiques et Naturelles. Serie A, Sciences Mathematiques, 35 (1937), pp. 355–357

1937

Earlier work this paper cites.

R. Gordon, R. Bender and G. Herman, Algebraic reconstruction techniques (ART) for threedimensional electron microscopy and x-ray photography, Journal of Theoretical Biology, 29 (1970): p. 471–481

1970

Earlier work this paper cites.

G.T. Herman. Image reconstruction from projections. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1980. The fundamentals of computerized tomography, Computer Science and Applied Mathematics

1980

Earlier work this paper cites.

F. Natterer. The Mathematics of Computerized Tomography. Wiley, New York, 1986

1986

Earlier work this paper cites.

K.M. Sezan and H. Stark. Applications of convex projection theory to image recovery in tomography and related areas. In H. Stark, editor, Image Recovery: Theory and application, pages 415–462. Acad. Press, 1987

1987

Earlier work this paper cites.

C. Cenker, H. G. Feichtinger, M. Mayer, H. Steier, and T. Strohmer. New variants of the POCS method using affine subspaces of finite codimension, with applications to irregular sampling. In Proc. SPIE: Visual Communications and Image Processing, pages 299–310, 1992

1992

Earlier work this paper cites.

E. L. Piccolomini, and F. Zama. The conjugate gradient regularization method in computed tomography problems. Applied mathematics and computation 102.1 (1999): 87–99

1999

Earlier work this paper cites.

T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm for linear systems with exponential convergence, Journal of Fourier Analysis and Applications, 15 (2009): p. 262–278

2009

Earlier work this paper cites.

D. Leventhal and A. S. Lewis, Randomized Methods for Linear Constraints: Convergence Rates and Conditioning, Mathematics of Operation Research, Vol. 35, No. 3, August 2010, pp. 641–654

2010

Cited alongside, same era.

D. Needell. Randomized Kaczmarz solver for noisy linear systems. BIT, 50(2):395–403, 2010

2010

Cited alongside, same era.

Y. C. Eldar and D. Needell. Acceleration of randomized Kaczmarz method via the JohnsonLindenstrauss lemma. Numer. Algorithms, 58(2):p. 163–177, 2011

2011

Cited alongside, same era.

Y.-T. Lee and A. Sidford, Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, FOCS 2013

2013

Cited alongside, same era.

A. Zouzias and N. M. Freris. Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl., 34(2): p. 773–793, 2013

Original

A. Ma, D Needell and A Ramdas, Convergence properties of the randomized extended Gauss–Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl. 36 (2015), pp. 1590–1604

2015

Later among the works it cites.

D. Needell, R. Zhao and A. Zouzias, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra and its Applications 484 (2015), p. 322–343

2015

Later among the works it cites.

J. Liu and S. Wright, An accelerated randomized Kaczmarz algorithm, Math. Comp. 85 (2016), p. 153-178

2016

Later among the works it cites.

Y. Jiao, B. Jin and X. Lu, Preasymptotic Convergence of Randomized Kaczmarz Method, Inverse Problems 33 (2017), article: 125012

2017

Later among the works it cites.

Z.-Z. Bai and W.-T. Wu, On convergence rate of the randomized Kaczmarz method, Linear Algebra and its Applications 553 (2018), p. 252–269

2018