Tight Convergence Bounds for the Classical Kaczmarz Method
Abstract
The classical method of Kaczmarz, introduced in 1937, is a textbook iterative method for solving linear systems A x = b. Despite its widespread use, particularly in the context of solving inverse problems where it is commonly included in software packages within Matlab, Python, and Julia, the precise characterization of convergence has long been deemed difficult to obtain. While different bounds on convergence rates have been established, they are largely unsatisfying as they cannot explain the classical, cyclic-update method's efficient convergence in practice. In this work, we obtain a tight characterization of convergence of the classical Kaczmarz method, establishing both linear and sublinear convergence bounds. The worst-case tight (i.e., exactly attained by some instances in the considered family) bounds are expressed in terms of a fixed matrix that depends only on A, but are not fully interpretable in terms of the matrix spectrum and row correlations, which had been observed to have an impact on convergence. We thus provide relaxations of these bounds that are fully expressible in terms of matrix row norms, row correlations, rank, and extremal positive singular values. The provided relaxed bounds explain one-cycle convergence in special cases where the matrix rows are all either parallel or orthogonal to each other. We further argue that the dependence on different parameters appearing in the bounds is necessary and within a small constant factor of the best attainable in the worst case. Finally, our bounds explain why the classical cyclic update is faster than the randomized one when matrix rows are weakly correlated, which is often observed in inverse problems where the cyclic method is used.
Related
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- A greedy double-block nonlinear Bregman-Kaczmarz method for nonlinear equations
- Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
- Peppy: An AI-Assisted Workflow for Tight Convergence Analysis of Optimization Algorithms
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
BibTeX
@misc{yu2026tight,
title = {{Tight Convergence Bounds for the Classical Kaczmarz Method}},
author = {Runbo Yu and Jelena Diakonikolas},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32034},
eprint = {2609.32034},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32034},
}
RIS
TY - UNPB
TI - Tight Convergence Bounds for the Classical Kaczmarz Method
AU - Runbo Yu
AU - Jelena Diakonikolas
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.32034
UR - https://arxiv.org/abs/2609.32034
AB - The classical method of Kaczmarz, introduced in 1937, is a textbook iterative method for solving linear systems A x = b. Despite its widespread use, particularly in the context of solving inverse problems where it is commonly included in software packages within Matlab, Python, and Julia, the precise characterization of convergence has long been deemed difficult to obtain. While different bounds on convergence rates have been established, they are largely unsatisfying as they cannot explain the classical, cyclic-update method's efficient convergence in practice. In this work, we obtain a tight characterization of convergence of the classical Kaczmarz method, establishing both linear and sublinear convergence bounds. The worst-case tight (i.e., exactly attained by some instances in the considered family) bounds are expressed in terms of a fixed matrix that depends only on A, but are not fully interpretable in terms of the matrix spectrum and row correlations, which had been observed to have an impact on convergence. We thus provide relaxations of these bounds that are fully expressible in terms of matrix row norms, row correlations, rank, and extremal positive singular values. The provided relaxed bounds explain one-cycle convergence in special cases where the matrix rows are all either parallel or orthogonal to each other. We further argue that the dependence on different parameters appearing in the bounds is necessary and within a small constant factor of the best attainable in the worst case. Finally, our bounds explain why the classical cyclic update is faster than the randomized one when matrix rows are weakly correlated, which is often observed in inverse problems where the cyclic method is used.
ER -