Source-linked AI summary
A randomized Kaczmarz algorithm with exponential convergence
Thomas Strohmer, Roman Vershynin
TL;DR
Useful convergence-rate estimates for Kaczmarz’s method were scarce, particularly because its rate depends on equation ordering. The paper introduces a randomized method for consistent overdetermined systems, proves exponential expected convergence, and reports advantages over prior solvers, including conjugate gradient in some settings.
Problem
Useful theoretical convergence-rate estimates for Kaczmarz’s method were scarce, and existing rates depended strongly on equation order rather than condition numbers.
Method
The paper randomly selects equations by row relevance and analyzes the resulting independent projection process for consistent overdetermined systems.
Results
The method achieves exponential expected convergence governed by the scaled condition number, independent of equation count, and can outperform conjugate gradient on moderately overdetermined systems.
Takeaways & Limitations
The solver can operate using only a small random part of the system and outperforms previously known methods on general extremely overdetermined systems.
Takeaways & Limitations
The method is less favorable when matrix-vector multiplication is much cheaper than O(mn), such as for Toeplitz-type matrices, where conjugate-gradient methods can outperform it.
Abstract
from arXiv · showhide
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.
1 Introduction and state of the art
The paper addresses the lack of useful convergence-rate estimates for Kaczmarz’s method, whose rate depends strongly on row order. It introduces a randomized method with an exponential expected rate that depends on matrix conditioning rather than the number of equations.
- Existing method: Kaczmarz’s method solves overdetermined systems by cyclically projecting iterates onto the solution hyperplanes of individual equations.It is also known as ART in computer tomography and is a special case of POCS.
- Open problem: Useful convergence-rate estimates are difficult to obtain, especially when more than two equations are involved.Existing estimates rely on matrix quantities that are hard to compute and compare across iterative methods.
- Open problem: The convergence rate depends strongly on equation order, whereas condition numbers are invariant to row order.This mismatch prevented condition-number-based rate estimates before this work.
- Prior randomized methods: Random row ordering can substantially improve convergence, but prior randomized Kaczmarz methods lacked rate guarantees.The paper proposes a randomized method to address this gap.
- Contribution: The proposed solver has an exponential expected convergence rate independent of the number of equations and uses only a small random part of the system.The authors report that it outperforms previously known methods on general extremely overdetermined systems.
- Contribution: Numerical simulations and theoretical analysis show that the method can outperform conjugate gradient on moderately overdetermined systems.Experiments also apply it to reconstructing bandlimited functions from non-uniformly spaced samples.
2 Randomized Kaczmarz algorithm and its rate of convergence
The paper samples equations randomly according to row relevance and analyzes the resulting projection process. It proves exponential expected convergence governed by the scaled condition number, with computational and data-access advantages for overdetermined systems.
- Algorithm: The randomized Kaczmarz algorithm selects each row with probability proportional to the square of its Euclidean norm.Each iteration projects the current approximation onto the selected equation’s solution hyperplane.
- Convergence result: Theorem 2 proves exponential convergence in expectation, with a rate depending only on the scaled condition number κ(A).The expected error decreases geometrically toward the solution.
- Proof strategy: The proof models the selected equation normal as a random vector and uses independent random projections at successive iterations.Orthogonality between the projection correction and the projected solution-space error yields the error reduction identity.
- Complexity: The expected iteration count provides a bound for reaching a prescribed accuracy ε.The theorem supplies the basis for the algorithm’s expected computational-complexity estimate.
- Complexity: O(n^2) operations suffice under the stated condition-number scaling, compared with O(mn^2) for Gaussian elimination.Each projection costs O(n), while the algorithm’s convergence bound uses κ(A)^2 = O(n).
- Implementation condition: Computing approximate row lengths initially costs O(nm), although row lengths may be known or tightly concentrated in important matrix families.Examples include normalized Vandermonde matrices and random matrices.
- Data access: The number m of equations is essentially irrelevant because the algorithm needs only O(n) random rows rather than the whole matrix.This supports its use on extremely overdetermined systems.
3 Optimality
The paper examines when the convergence-rate estimate is optimal and shows that it cannot generally be improved beyond a constant factor. The estimate is attained for specific systems, including arbitrarily large systems with arbitrarily large condition numbers.
- The estimate cannot be improved beyond a constant factor for any linear system.
- The proof constructs an initial approximation aligned with a condition-number-realizing direction and analyzes one random projection by decomposing vectors into parallel and orthogonal components.
- When κ(A) = √n, the estimate in Theorem 2 becomes an equality.
- Arbitrarily large systems can attain equality for every iteration, with arbitrarily large condition numbers κ(A), when m/κ^2 is an integer.
- The equality construction repeats orthogonal row vectors, and an initial approximation reaches the solution with probability κ^-2 at each step under the described sampling.
4 Numerical experiments and comparisons
The experiments examine randomized Kaczmarz for nonuniform sampling and compare its convergence and computational efficiency with conjugate-gradient methods on overdetermined systems. Theoretical analysis and simulations show advantages in several settings, while also identifying cases where conjugate gradients remain preferable.
- Nonuniform sampling: Algorithm 1 samples rows with probability proportional to their squared Euclidean norms, equivalently selecting row j with probability w_j in the sampling model.This gives a probabilistic, computationally efficient implementation of the maximal-correction strategy.
- Nonuniform sampling: The convergence-rate bound for Algorithm 1 depends on the scaled condition number κ(A), with the trigonometric-system condition number bounded using sampling-point spacing estimates.For the stated spacing condition, the cited estimate gives k(A) ≤ 3.
- Nonuniform sampling: In the nonuniform sampling experiment, standard, equally randomized, and norm-weighted randomized Kaczmarz methods are compared using least-squares error versus projections.The experiment uses r = 50, m = 700, and uniformly drawn, ordered sampling points.
- Comparison with conjugate gradients: For Gaussian matrices, the predicted computational complexities of randomized Kaczmarz and CGLS are essentially equal near y ≈ 1/3, with Algorithm 1 favored when m > 3n.The comparison treats n^2 and log(1/ε) as common factors.
- Comparison with conjugate gradients: For a 300 × 100 Gaussian system, randomized Kaczmarz is almost twice as efficient as CGLS, while for a 500 × 100 system it outperforms CGLS by a factor of 3.The 300 × 100 experiment compares averaged least-squares error against floating-point operations; the 500 × 100 result exceeds the theoretical factor-of-about-2 prediction.
- Comparison with conjugate gradients: Conjugate-gradient methods can outperform Kaczmarz methods when matrix-vector multiplication is substantially cheaper than O(mn), as for Toeplitz-type matrices.The paper also gives a spectral example where CGLS converges in two iterations despite a very small singular value, whereas Kaczmarz converges extremely slowly.
5 Some open problems
The section discusses relaxation as a possible acceleration and identifies open questions about its optimality and applicability to inconsistent systems.
- Kaczmarz method with relaxation: Relaxation has been observed to accelerate Kaczmarz convergence, changing the iteration through relaxation parameters λk,i.
- Kaczmarz method with relaxation: For Gaussian matrices, the authors observed that setting λk,i := λ = m for all k and i can be effective.
- Kaczmarz method with relaxation: The paper provides a typical numerical simulation but no proof that the observed relaxation choice improves performance or is optimal.
- Inconsistent systems: For inconsistent systems caused by noise in the right-hand side, convergence to the least-squares solution has been obtained with strong underrelaxation.
- Inconsistent systems: Although the paper assumes consistency theoretically, the authors consider randomized Kaczmarz with appropriate underrelaxation plausibly useful for inconsistent systems.