Source-linked AI summary
An Accelerated Randomized Kaczmarz Algorithm
Ji Liu, Stephen J. Wright
TL;DR
For consistent linear systems, the paper examines how to improve randomized Kaczmarz convergence without losing sight of the costs imposed by sparsity. It applies acceleration to RK and proposes a cached sparse implementation; ARK is reported to converge faster on poorly conditioned systems, while sparse costs create trade-offs with RK. The comparison with conjugate gradient also depends on eigenvalue behavior.
Problem
The paper studies how randomized Kaczmarz convergence and per-iteration cost compare across conditioning and sparsity settings for consistent linear systems.
Source: §1 · pp. 1–2Method
The paper applies Nesterov acceleration to RK to form ARK and proposes SARK, which caches updates to address ARK's higher cost on sparse matrices.
Source: §1 · p. 2Results
ARK is reported to converge faster than RK on poorly conditioned systems, while RK costs O(δn) per sparse iteration versus O(n) for ARK, making SARK competitive in some regimes.
Source: §1 · p. 2Takeaways & Limitations
Algorithm choice depends on sparsity and conditioning, and the paper compares RK, ARK, and SARK to guide that choice.
Source: §1 · p. 2, §5.2 · p. 11The paper notes that CG's asymptotic rate may be pessimistic because practical performance depends on the eigenvalue distribution of A^T A.
Source: §5.3 · p. 13
Abstract
from arXiv · showhide
The randomized Kaczmarz ($\RK$) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$. This paper proposes an accelerated randomized Kaczmarz ($\ARK$) algorithm with better convergence than the standard $\RK$ algorithm on ill conditioned problems. The per-iteration cost of $\RK$ and $\ARK$ are similar if $A$ is dense, but $\RK$ is much more able to exploit sparsity in $A$ than is $\ARK$. To deal with the sparse case, an efficient implementation for $\ARK$, called $\SARK$, is proposed. A comparison of convergence rates and average per-iteration complexities among $\RK$, $\ARK$, and $\SARK$ is given, taking into account different levels of sparseness and conditioning. Comparisons with the leading deterministic algorithm --- conjugate gradient applied to the normal equations --- are also given. Finally, the analysis is validated via computational testing.
1. Introduction
The paper addresses consistent linear systems and introduces accelerated and sparse variants of randomized Kaczmarz to improve convergence while accounting for conditioning and sparsity. Its analysis assumes normalized rows, although the algorithms do not require normalization.
1. Introduction
- The analysis assumes normalized rows, but the randomized algorithms generate the same iterates without normalization when b is scaled correspondingly.The paper says normalization may improve conditioning and simplify analysis.Source: §1 · pp. 1–2
- RK randomly selects a row and projects the current estimate onto its hyperplane; it uses O(n) storage and converges linearly.The paper frames RK as a method for solving consistent systems and relates its update to dual coordinate descent.Source: §1 · p. 2
- ARK converges faster than RK on poorly conditioned systems, while SARK caches updates to retain sparsity and has average per-iteration cost O(δn).The paper compares RK, ARK, and SARK across sparsity ratios and minimum nonzero eigenvalues to guide algorithm choice.Source: §1 · p. 2
1.1. Notation.
- The notation defines λmin and λmax as the minimum and maximum nonzero eigenvalues of A^T A, and distinguishes spectral and Frobenius norms.It also identifies X+ as the Moore–Penrose pseudoinverse and defines projections onto hyperplanes and the solution set.Source: §1.1 · p. 3
2. Related Work
Prior work developed cyclic and randomized projection methods for linear systems, extending them to inconsistent systems and inequalities. The paper situates its methods among these approaches and their differing convergence guarantees.
2. Related Work
- Kaczmarz proposed cyclic projections for consistent systems, with a linear rate in cycles later proved by Galantai.The method has also been used in Algebraic Reconstruction Techniques for image reconstruction [4, 5].Source: §2 · p. 3
- Strohmer and Vershynin proved expected linear convergence for RK on consistent full-column-rank systems; Needell treated inconsistent systems, with convergence to a ball around the solution.The ball's radius is proportional to b's distance from the image space of A.Source: §2 · p. 3
- Extensions adapt RK to consistent linear inequalities and equalities, address possibly inconsistent systems through two projections [16], and use parallel component averaging to handle inconsistency.The optimal-projection variant improves convergence rate but requires more computation per iteration.Source: §2 · pp. 3–4
3. Algorithm
The section reviews RK, derives ARK by applying Nesterov acceleration to its projection update, and presents an equivalent implementation intended to reduce per-iteration work. The analysis assumes normalized rows and uniform row selection.
3. Algorithm
- The analysis assumes normalized rows and uniform row selection; dropping these assumptions complicates accelerated-method analysis, and the authors consider the added generality minor.Without normalization, RK's row-selection rule differs from versions in.Source: §3 · p. 4
- ARK applies Nesterov’s accelerated procedure to the RK projection step, with scalar sequences that can be calculated offline.The accelerated procedure introduces sequences that combine the iterates before projecting onto a randomly selected row hyperplane.Source: §3 · pp. 4–5
- For dense A, RK costs about 4n operations per iteration, while Algorithm 2 costs about 11n.The stated counts assume row norms are precomputed in an initial pass.Source: §3 · p. 5
- Algorithm 3 is an equivalent ARK implementation that lowers the dense per-iteration count from about 11n to 9n operations.With parallel computation, its cost can be reduced to about 4n, matching RK.Source: §3 · pp. 5–7
4. Efficient Implementation for Sparse Data
SARK adapts ARK for sparse matrices by caching updates between explicit iterate refreshes. Its potential advantage depends on row sparsity and cycle length, and the paper describes regimes where it can compete with RK.
4. Efficient Implementation for Sparse Data
- The sparse implementation assumes nonzeros are not concentrated in particular rows, and estimates cached-vector sparsity assuming selected rows do not overlap significantly.Each selected row is assumed to have about δn nonzeros.Source: §4 · pp. 7–8
- RK costs O(δn) per iteration on sparse A, whereas ARK generally costs O(n); SARK seeks to reduce ARK's average cost by caching updates.The paper notes ARK needs fewer iterations than RK in general, making SARK competitive in some regimes.Source: §4 · pp. 7, 9
- SARK caches successive row updates in sparse vectors and refreshes the explicit iterates after each cycle of T steps.The implicit representation is advantageous while the cached vectors have not become too dense.Source: §4 · p. 7
- The paper estimates cycle operation counts from the updates to cached scalars and vectors, then uses the cycle length to obtain an approximate average per-iteration cost.The reported operation-count expression is in terms of δ, n, and T.Source: §4 · p. 8
5. Convergence Rate
Section 5 studies convergence behavior and estimates the operations needed to reach a specified accuracy. It compares RK, ARK, and SARK with each other and with conjugate gradient (CG) on the normal equations.
5. Convergence Rate
- For λ > 0, ARK converges linearly in expectation to the projection of the initial point onto Ax = b; for λ = 0, its rate is sublinear.The analysis compares rates with λ set to λmin and focuses on ill-conditioned systems, where λmin is small.Source: §5 · p. 10
5.1. Comparison between RK and ARK for Dense A.
- For small λ, ARK has significantly faster linear convergence than RK and is generally faster per operation, despite requiring twice as many operations per iteration.The comparison is for dense A; the per-iteration decrease is governed by the σ1 term in the ARK bound's denominator.Source: §5.1 · p. 11
5.2. Comparison among RK, ARK, and SARK for Sparse A.
- For fixed small λmin, RK is superior at low δ, SARK at intermediate δ, and ARK at high δ; the comparisons use approximate, worst-case analyses.As λmin increases, RK is favored; ARK favors small λmin and large δ, while SARK is superior to ARK for small δ.Source: §5.2 · pp. 11–12, Figure 1 · p. 12
5.3. Comparison among RK, SARK, and CG.
- CG may be competitive with RK when √(λminλmax) is significantly larger than 1, and with SARK when δλmax is significantly greater than 1.CG uses products with the full matrix and its transpose each iteration, unlike RK and ARK, which access one row; CG's asymptotic rate can be pessimistic because its practical performance depends on the eigenvalue distribution.Source: §5.3 · pp. 12–13
6. Computational Results
Computational tests compare RK, ARK variants, and SARK on dense and sparse data and against CG on ill-conditioned problems. The results show that the best method depends on conditioning and sparsity, and that CG's early speed can give way to ARK at high precision.
6.1. Comparison between RK and ARK for Dense Data.
- ARK(0) needs no additional knowledge of A and guarantees sublinear convergence, but is less competitive than other ARK variants while competing with RK on ill-conditioned cases.Source: §6 · p. 13, §6.1 · p. 14
- ARK(λmin) and ARK(auto) converge much faster than RK in iterations and operations except on very well-conditioned problems; auto matches λmin after estimation.Source: §6.1 · p. 14, Figure 2 · p. 15, Figure 3 · p. 16
6.2. Comparison among RK, ARK, and SARK for Sparse Data.
- At δ=0.8, ARK is more operation-efficient than SARK and both beat RK; at δ=0.08 SARK wins, while at δ=0.01 RK dominates both.Across all three sparsity levels, ARK/SARK require fewer iterations than RK.Source: §6.2 · p. 14, Figure 4 · p. 17
6.3. Comparison among RK, ARK, and CG.
- CG converges rapidly early then slows, while randomized methods are consistent, stable, and well predicted by analysis; CG's full-matrix sweep gives a global view of the data.Source: §6.3 · p. 18
- As α increases, CG's asymptotic convergence slows after leading eigenspaces and RK fares worse relative to CG; ARK remains comparable.Source: §6.3 · p. 18
Appendix A. Proof of Theorem 5.1
The proof reduces arbitrary initial points to zero and establishes Theorem 5.1 through conditional-expectation bounds and recursive control of auxiliary sequences.
Appendix A. Proof of Theorem 5.1
- Shifting the system by Ax0 reduces analysis from any starting point to x0 = 0 while translating the iterate sequence accordingly.The proof says solving Ax = b is equivalent to solving Ax = b − Ax0 from the zero initial point.Source: Appendix A · p. 22
- The scalar sequence γ_k is increasing, bounded below by 1/m and above by 1/λ; since λ ≤ m, α_k and β_k lie in [0, 1] for all k.Source: Appendix A · p. 22
- The proof conditions expectations on previously sampled row indices and uses uniform row sampling under the normalized-row assumption.The history I(k) contains the indices through iteration k, and the next iterates are determined by that history.Source: Appendix A · pp. 21, 23
- Convexity and two technical lemmas bound the terms in the one-step estimate, which is then combined into a recursive inequality.The proof handles the three terms in (A.6) separately before substituting the bounds into that estimate.Source: Appendix A · pp. 23–24
- The increasing auxiliary sequences A_k and B_k are bounded recursively, following the accelerated coordinate descent proof strategy in [11].These bounds are used to estimate the convergence rate.Source: Appendix A · pp. 25–26