Abstract
The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system, but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling.
Introduction
Solving large, overdetermined linear systems ($Ax = b$, where $A \in \mathbb{R}^{m \times n}$ and $m \ge n$) is a fundamental challenge in computational science, appearing in fields as diverse as medical imaging (CT scans) and digital signal processing. One of the most enduring approaches is the Kaczmarz method, first introduced in 1937. In the context of medical imaging, this method is often referred to as the Algebraic Reconstruction Technique (ART).
The Kaczmarz method is an iterative solver that treats each equation in the system as a hyperplane. In each step, the current estimate is projected onto one of these hyperplanes. While the method is prized for its simplicity and low memory footprint, its convergence speed has historically been difficult to quantify. The primary bottleneck is that the convergence rate depends heavily on the order in which the equations are processed. While practitioners long suspected that a random ordering of equations improved performance, a rigorous mathematical guarantee for this phenomenon remained elusive until now.
The Randomized Kaczmarz Algorithm
This paper introduces a randomized version of the Kaczmarz method that selects equations based on a specific probability distribution. Instead of cycling through the rows of the matrix $A$ in a fixed order, the algorithm selects row $i$ with a probability proportional to the square of its Euclidean norm:
$$P(\text{row } i) = \frac{\|a_i\|_2^2}{\|A\|_F^2}$$
where $\|A\|_F$ is the Frobenius norm of the matrix. By favoring "heavier" rows—those that represent more significant constraints in the system—the algorithm ensures that each iteration makes a substantial expected step toward the solution. This selection strategy is the "secret sauce" that allows for a clean theoretical analysis of the convergence rate.
Theoretical Convergence and the Scaled Condition Number
The central contribution of this work is the proof that the Randomized Kaczmarz algorithm converges at an expected exponential (or geometric) rate. Specifically, the expected error at iteration $k$ is bounded by:
$$E\|x_k - x\|_2^2 \leq \left(1 - \frac{1}{\kappa(A)^2}\right)^k \|x_0 - x\|_2^2$$
Here, $\kappa(A)$ is a "scaled condition number" defined as $\kappa(A) = \|A\|_F \|A^{-1}\|_2$. This result is significant for several reasons:
- Independence from System Size: Remarkably, the convergence rate does not depend on $m$, the number of equations. This implies that adding redundant or additional information to a system does not slow down the solver, a property not shared by most classical methods.
- Geometric Interpretation: The rate is governed by the geometry of the matrix. If the hyperplanes are nearly orthogonal, the condition number is small, and convergence is rapid.
- Minimal Information Requirements: The solver does not need to load the entire matrix into memory. It only requires the norms of the rows to establish the probability distribution, after which it can process the system by sampling individual rows.
Performance Comparison
While the Conjugate Gradient (CG) method is often the default choice for linear systems, this research demonstrates that Randomized Kaczmarz can be more efficient for "extremely overdetermined" systems.
Through analysis of synthetic Gaussian matrices, the authors show that when the number of equations $m$ is significantly larger than the number of unknowns $n$ (specifically when $m > 3n$), the Randomized Kaczmarz algorithm can outperform the Conjugate Gradient Least Squares (CGLS) method in terms of total computational operations. This is because each iteration of Kaczmarz is extremely cheap ($O(n)$), whereas CG requires matrix-vector multiplications ($O(mn)$).
Empirical Validation: Nonuniform Sampling
The algorithm's efficacy was tested on the problem of reconstructing bandlimited functions from nonuniform samples. This is a practical challenge in signal processing where a signal is captured at irregular intervals. Numerical simulations confirmed that the proposed randomized method reached high precision ($10^{-15}$) significantly faster than both the standard cyclic Kaczmarz method and a version of the randomized algorithm that picks rows with uniform probability. These results validate a long-standing prediction by Feichtinger et al. regarding the efficiency of randomized projections in signal reconstruction.
Limitations and Conclusion
Despite its strengths, the current theoretical framework assumes the linear system is consistent (i.e., there exists a perfect solution $x$ such that $Ax=b$). In many real-world scenarios, noise makes the system inconsistent. While the algorithm can be adapted using relaxation parameters—where the update does not move the estimate all the way to the hyperplane—the full theoretical analysis for inconsistent systems remains an area for future work.
In conclusion, the Randomized Kaczmarz algorithm provides a powerful, memory-efficient alternative for solving massive, overdetermined linear systems. By providing the first proof of exponential convergence that is independent of the number of equations, this work bridges the gap between randomized algorithms and classical numerical analysis, offering a robust tool for modern data-intensive applications.
Summary updated