# An Accelerated Randomized Kaczmarz Algorithm

arXiv: https://arxiv.org/abs/1310.2887 · HTML: https://mlsanity.com/paper/1310.2887/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2013.

## Built on by (most cited first, 12 of 12)

- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Accelerated SGD for Non-Strongly-Convex Least Squares](https://mlsanity.com/paper/2203.01744/) (2022)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory](https://mlsanity.com/paper/2102.11822/) (2021)
- [Randomized Kaczmarz with geometrically smoothed momentum](https://mlsanity.com/paper/2401.09415/) (2024)
- [An optimal scheduled learning rate for a randomized Kaczmarz algorithm](https://mlsanity.com/paper/2202.12224/) (2022)
- [Linear Discriminant Analysis with the Randomized Kaczmarz Method](https://mlsanity.com/paper/2211.05749/) (2022)
- [Use of operator defect identities in multi-channel signal plus residual-analysis via iterated products and telescoping energy-residuals: Applications to kernels in machine learning](https://mlsanity.com/paper/2601.18080/) (2026)
- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)
- [How AI settled the complexity of the oldest SGD algorithm](https://mlsanity.com/paper/2606.29593/) (2026)

## Abstract (arXiv)

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.