Source-linked AI summary
Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma
Yonina C. Eldar, Deanna Needell
TL;DR
Randomized Kaczmarz converges exponentially in expectation, but the paper seeks faster convergence through better projection choices. It uses Johnson–Lindenstrauss dimension reduction to select among candidate projections, and reports faster convergence with larger projection dimensions at increased per-iteration cost.
Problem
The convergence rate of Kaczmarz depends on row ordering, motivating a row-selection strategy that can improve convergence.
Source: §1 · pp. 1–2Method
The method uses low-dimensional Johnson–Lindenstrauss approximations to choose a strong projection from randomly selected candidate rows.
Source: §1.2 · p. 3, §2.1 · p. 4Results
Higher projection dimensions produce quicker convergence, while increasing computation per iteration.
Source: §4 · p. 11Takeaways & Limitations
With d = O(log n), the modified method’s worst-case runtime is O(n^2 log n), the standard randomized method’s runtime up to a logarithmic factor.
Source: §1.2 · p. 3Initialization may be expensive, so the method is advantageous when the same matrix A is reused across multiple problem instances.
Source: §2.1 · p. 5
Abstract
from arXiv · showhide
The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax=b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson-Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.
1 Introduction
Randomized Kaczmarz addresses row-order sensitivity in the classical projection method, whose convergence guarantees were difficult to obtain. The paper proposes choosing a strong projection from a random candidate set using low-dimensional approximations.
1 Introduction
- Classical Kaczmarz iteratively projects an estimate onto the hyperplanes defined by the rows of a consistent system Ax = b.The method is presented as computationally feasible for very large systems, but its convergence rate depends on row ordering.Source: §1 · pp. 1–2
- Random row selection improves on ordering sensitivity, while earlier theory established convergence guarantees only recently.Prior work also analyzed noisy, potentially inconsistent systems; this paper leaves detailed noisy-case analysis for future work.Source: §1 · pp. 1–2, §1.1 · pp. 2–3, §1.2 · p. 3
1.1 Randomized Kaczmarz
- Randomized Kaczmarz selects rows with probability proportional to their Euclidean norms, giving expected exponential convergence with an efficient, though not generally optimal, selection rule.For well-conditioned matrices, the cited analysis gives O(n) iterations and O(n^2) total runtime, and reports fewer computations than conjugate gradient for Gaussian A when m > 3n.Source: §1.1 · p. 2
1.2 Modified approach
- The modified method approximates candidate projections in a lower-dimensional space and selects the one maximizing the update norm; its analysis here is limited to noiseless systems.The paper expects faster convergence while retaining a worst-case rate at least as fast as standard randomized Kaczmarz, with a runtime tradeoff controlled by dimension d.Source: §1.2 · p. 3
2 Implementation and Runtime
The implementation uses Johnson–Lindenstrauss projections to approximate candidate-row geometry, enabling more projection choices per iteration. Its runtime depends on projection dimension, while preprocessing can be substantial but reusable across problems sharing a matrix.
2 Implementation and Runtime
- Johnson–Lindenstrauss projection reduces the cost of evaluating candidate rows by approximately preserving geometry, including inner products and row norms, in a lower-dimensional space.The lemma permits dimension logarithmic in the number of points; random projections and fast-multiply transforms are discussed as constructions.Source: §2 · pp. 3–4
2.1 Implementation
- RKJL projects rows offline, projects the current estimate each iteration, and selects from sampled rows using projected calculations; it also exactly checks selected rows to guard against approximation error.The algorithm is named Randomized Kaczmarz via Johnson-Lindenstrauss (RKJL).Source: §2.1 · pp. 4–5
- Initialization can be expensive, but its one-time cost is advantageous when the same matrix A is reused across multiple problem instances.The paper gives wave-scattering and structural mechanics as examples of such settings.Source: §2.1 · p. 5
2.2 Runtime
- With d = O(log n), RKJL has O(n^2 log n) runtime, the standard randomized method’s runtime up to a logarithmic factor.The per-iteration cost is O(nd); preprocessing can cost O(n^3d) when m ≥ n^2, or O(mnd) when Φ is applied to all rows.Source: §2.2 · p. 6
- Unlike submatrix-selection approaches that may require reselection when a subsystem cannot be solved, RKJL is guaranteed to converge, with likely improved expected convergence.The choice between approaches depends on the application, and combining them may be beneficial in some cases.Source: §2.2 · p. 6
3 Analytical Justification
The analysis shows that RKJL is at least as fast as standard randomized Kaczmarz and can converge strictly faster when its projected geometry supports better row choices. Its guarantees are developed under simplifying assumptions, with the Johnson–Lindenstrauss projection approximating the geometry used for selection.
3 Analytical Justification
- With d = O(log n), the projection approximately preserves the geometry needed to estimate row inner products and norms for RKJL.The analysis assumes a real-valued homogeneous system, unit-norm rows, and an initial estimate of norm at most 1; the authors note these assumptions simplify the analysis.Source: §3 · p. 6
- When the JL error is small, RKJL’s selection values approximate the desired inner products and help it choose a better projection; error can dominate once the estimate is already near the solution.The authors explain that improvements may no longer be expected at that stage because the estimate is already approximately the solution.Source: §3 · p. 7
- RKJL converges at least as fast as standard randomized Kaczmarz, and is strictly faster unless the selected rows have equal inner products with the current estimate.The theorem’s lower bound addresses the worst case; the remarks report substantial improvements in numerical experiments.Source: §3 · pp. 7, 9
- The analysis allows unequal row norms, with different selection probabilities, and the authors report similar experimental results for equal- and unequal-norm rows.They also describe a case where large, highly correlated rows may be repeatedly selected by standard RK, while RKJL may avoid them when their contribution is minimal.Source: §3 · p. 9
- The row-selection strategy is not generally optimal: many large-norm rows and few small-norm, uncorrelated rows can make both RK and RKJL perform poorly.The authors note that row normalization may help avoid such difficulties when using RKJL.Source: §3 · pp. 9–10
4 Numerical Results
The numerical experiments compare an idealized best-of-n row selection with standard randomized Kaczmarz, then test the Johnson–Lindenstrauss-based method across projection dimensions. The reported convergence improves in both settings, with larger d helping in the projected simulations.
4 Numerical Results
- In the 60,000 × 1,000 Bernoulli homogeneous-system experiment, the best-of-n-row variant converged significantly faster than standard RK.This comparison omits the Johnson–Lindenstrauss projection and is computationally infeasible.Source: Figure 1 · p. 10, §4 · p. 10
- Because larger d increases per-iteration computation and its precise convergence effect lacks theoretical guarantees, the authors say the comparison should be empirical.Source: §4 · p. 11
- For very large systems, d = O(log n) is expected to yield convergence resembling the idealized Figure 1 result.Source: §4 · p. 11
- With the Johnson–Lindenstrauss projection, larger d produced quicker convergence in simulations with m = 60000 and n = 1000.Larger d corresponds to lower δ.Source: Figure 2 · p. 11, §4 · p. 11