Source-linked AI summary
Tight Convergence Bounds for the Classical Kaczmarz Method
Runbo Yu, Jelena Diakonikolas
TL;DR
The classical cyclic Kaczmarz method is widely used, but its convergence has been difficult to characterize. The paper derives tight convergence bounds and interpretable relaxations, including worst-case sublinear behavior that cannot be improved in order and a linear-rate bound within a factor of three of the best worst-case value.
Problem
The classical cyclic method is widely used, but its convergence has been difficult to characterize quantitatively.
Source: §1 · pp. 1–2Method
The paper derives tight convergence bounds for consistent systems and relaxes them into bounds expressed through matrix structure.
Source: §2.1 · p. 10, §3 · p. 15Results
The worst-case residual decay has order 1/k and cannot be improved, while the predicted linear-rate bound is within a factor of three of the smallest value attainable in a worst-case linear-rate bound.
Source: §2.2 · pp. 12–13Takeaways & Limitations
The bounds identify parameter dependence that is necessary up to a small constant factor in the worst case.
Source: §2.2 · pp. 12–13The analysis assumes a consistent system, and its stated row ordering is deterministic cyclic order, with other deterministic orders handled by reordering rows.
Source: §1 · p. 1, §1.1 · p. 2
Abstract
from arXiv · showhide
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.
1 Introduction
The classical cyclic Kaczmarz method is widely used, but its convergence has been difficult to characterize, and earlier bounds do not explain its efficient practical convergence. This work gives tight convergence bounds and more interpretable relaxations tied to matrix structure.
1.1 Preliminaries
- Each cyclic sweep updates the iterate using one row at a time, traversing the rows from 1 to m; the analysis assumes a consistent system and fixes a closest solution when it is not unique.The row order 1, 2, …, m is without loss of generality because any deterministic ordering can be represented by reordering the rows.Source: §1 · p. 1, §1.1 · p. 2
1 Introduction
- The classical method is widely used in inverse problems, yet its convergence has resisted meaningful guarantees and earlier bounds do not explain its efficient practical behavior.Prior theoretical work focused largely on randomized variants, while analyses of the classical method often depended on dimensions or rank.Source: §1 · pp. 1–2
1.2 Contributions
- The authors establish sharp convergence characterizations and relax them into bounds involving row norms, row correlations, rank, and extreme positive singular values.The relaxed bounds imply one-cycle convergence when rows are all orthogonal or all parallel, and the bounds depend on row ordering.Source: §1 · p. 2, §1.2 · p. 3
1.3 Related Work
- Earlier bounds often omit row-order and correlation structure; the paper focuses on quantitative convergence estimates rather than asymptotic convergence, which was already established.The paper also relates its analysis to prior triangular-matrix approaches and notes that a related cyclic sweep analysis did not provide explicit nonasymptotic bounds.Source: §1.3 · pp. 4–5
2 Main results
The section characterizes cyclic Kaczmarz using an exact matrix-dependent recurrence and tight convergence bounds, then develops more interpretable rates in terms of row correlations, rank, and singular values. Examples illustrate one-cycle convergence, tightness of worst-case rates, and cases where cyclic updates outperform randomized updates.
2 Main results
- Theorem 1 establishes exactly tight convergence bounds for the classical cyclic update, including linear and sublinear rates.The section overview describes the bounds as exactly tight; the proof covers residual and last-iterate bounds.Source: §2 · pp. 5, 7, 8
- In singular-vector coordinates, the residual follows e_{k+1} = M e_k for a matrix M determined by A, with operator norm strictly below one.This gives an exact characterization of each update and implies contraction.Source: §2 · pp. 5–6
2.1 More Interpretable Convergence Bounds
- Relaxing the tight bounds yields explicit geometric rates, and the row-correlation corollary bounds squared residual convergence using interpretable matrix quantities.The relaxations are expressed through row correlations, matrix spectrum, and rank.Source: §2.1 · pp. 8, 11
- Orthogonal rows predict convergence in one cycle, near-orthogonal rows predict fast convergence when σ_r^2(Ahat) dominates squared row correlations, and near-parallel rows predict slow convergence.For near-parallel rows and σ_r = Θ(1), the stated contraction factor is approximately 1 − 1/m^2.Source: §2.1 · p. 10
- The relaxation for the auxiliary-matrix norm also yields sublinear rate bounds in terms of row correlations, spectrum, and rank, and implies iterate-convergence bounds.The iterate bounds follow by applying the quantitative operator-norm bounds to Theorem 1.Source: §2.1 · p. 11
- Lemma 3 can upper-bound ||M||op to yield a fully quantifiable convergence-rate estimate.This estimate can be combined with the initial error ||x0 − x*||.Source: §2.1 · p. 11
2.2 Discussion of Tightness of Provided Convergence Bounds
- Theorem 1 bounds are instance-tight up to initialization, while the more interpretable bounds relax them using row correlations, rank, and the smallest nonzero singular value.The latter quantities help explain convergence behavior that the tight bounds do not directly express.Source: §2.2 · p. 11
- When rows are all parallel or mutually orthogonal, the stated linear bounds correctly predict convergence in one cycle.For parallel rows the rank is one; for orthogonal rows, the contraction factor and ||L − I_m||op are zero.Source: §2.2 · p. 11
- For a 2×2 example with neither parallel nor orthogonal rows, Lemma 2 prefactors and Corollary 1’s linear bound are tight at k = 1, and its predicted rate is within a factor of four of the true rate.The example also shows the sublinear bound’s 1/k order cannot be improved in the worst case.Source: §2.2 · p. 12
- Examples with rows far from parallel or orthogonal show worst-case 1/k decay cannot be improved, and arbitrarily small singular values can make convergence arbitrarily slow.The 3×3 example makes the sublinear bound tight up to a constant and shows the linear-rate bound is within a factor of three of the best worst-case value.Source: §2.2 · pp. 12–14
2.3 When is Classical Cyclic Ordering Faster than Randomized?
- A sufficient condition for cyclic updates to outperform randomized updates holds for a range of near-orthogonal systems; in the 2×2 family, cyclic is faster for every c ∈ (0, 1) under initialization perpendicular to the second row, even when rows are neither nearly orthogonal nor nearly parallel.Source: §2.3 · p. 15
3 Conclusion
The paper presents new convergence bounds for the classical Kaczmarz method on consistent linear systems and argues that they are tight.
3 Conclusion
- The paper presents new convergence bounds for the classical Kaczmarz method on consistent linear systems.Source: §3 · p. 15
- The authors argue that the bounds are tight.Source: §3 · p. 15
- Comparable bounds for inconsistent systems, block variants, and more general projections onto convex sets remain interesting directions for future work.Source: §3 · p. 15