Randomized Kaczmarz Methods with Beyond-Krylov Convergence
Michał Dereziński, Deanna Needell, Elizaveta Rebrova, Jiaming Yang · SIAM Journal on Matrix Analysis and Applications · 2025
Abstract. Randomized Kaczmarz methods form a family of linear system solvers which converge by repeatedly projecting their iterates onto randomly sampled equations. While effective in some contexts, such as highly overdetermined 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 ill-conditioned systems. In this paper, we introduce Kaczmarz[Formula: see text], 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 Kaczmarz[Formula: see text] captures large outlying singular values provably faster than popular Krylov methods, for both over- and underdetermined systems. We also develop an optimized variant for positive semidefinite systems, called CD[Formula: see text], 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. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/EdwinYang7/kaczmarz-plusplus and in the supplementary materials ( supplement_v2.pdf [ 1.23MB], code_v2.zip [ 20.2KB]). [Formula: see text]