Precise limits on how fast the Kaczmarz method solves equations
Tight Convergence Bounds for the Classical Kaczmarz Method
Data Structures and Algorithms
Summary
Solving systems of linear equations is a common task in math and computing. The classical Kaczmarz method, used especially in solving inverse problems, has long puzzled experts because its practical speed didn't match earlier theoretical predictions. The authors provide exact upper and lower limits on how quickly this method converges to a solution, explaining why it often works better in practice. Their findings clarify why updating the solution cyclically often beats randomized approaches when the system's data rows are not strongly related.
What this means in practice
- •For software engineers: Improve the efficiency of linear equation solvers in numerical libraries by selecting the best update strategy based on matrix properties.
- •For medical imaging developers: Enhance iterative reconstruction algorithms for imaging devices by exploiting convergence properties of the Kaczmarz method tailored to weakly correlated data.
Authors
Runbo Yu, Jelena Diakonikolas
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.