Randomized Kaczmarz methods with beyond-Krylov convergence

Randomized Kaczmarz methods form a family of linear system solvers that converge by repeatedly projecting their iterates onto randomly sampled equations. While effective in some contexts, such as highly over-determined least squares, Kaczmarz methods are traditionally deemed secondary to Krylov subspace methods, since this latter family of solvers can exploit outliers in the input's singular value distribution to attain fast convergence on many ill-conditioned systems. In this talk, we introduce an accelerated randomized block Kaczmarz algorithm that exploits outlying singular values in the input to attain a fast Krylov-style convergence. Moreover, we show that our approach captures large outlying singular values provably faster than popular Krylov methods. We also develop an optimized variant for positive semidefinite systems, demonstrating empirically that it is competitive in arithmetic operations with both CG and GMRES on a collection of benchmark problems. To attain these results, we introduce several novel algorithmic improvements to the Kaczmarz framework, including adaptive momentum acceleration, Tikhonov-regularized projections, and a memoization scheme for reusing information from previously sampled equation blocks. This work is joint with Michał Dereziński, Elizaveta Rebrova, and Jiaming Yang.