# Randomized Kaczmarz converges along small singular vectors

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

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

- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Side Effects of Learning from Low-dimensional Data Embedded in a Euclidean Space](https://mlsanity.com/paper/2203.00614/) (2022)
- [Randomized Kaczmarz with geometrically smoothed momentum](https://mlsanity.com/paper/2401.09415/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [An optimal scheduled learning rate for a randomized Kaczmarz algorithm](https://mlsanity.com/paper/2202.12224/) (2022)
- [Where Have All the Kaczmarz Iterates Gone?](https://mlsanity.com/paper/2510.08563/) (2025)
- [From Order to Distribution: An Exact Operator Framework for Forgetting in Continual Learning](https://mlsanity.com/paper/2604.13460/) (2026)
- [Complex Stochastic Gradient Descent and Directional Bias in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2604.23017/) (2026)

## Abstract (arXiv)

Randomized Kaczmarz is a simple iterative method for finding solutions of linear systems Ax = b. We point out that the arising sequence (xk)k=1∞ tends to converge to the solution x in an interesting way: generically, as k rightarrow ∞, xk - x tends to the singular vector of A corresponding to the smallest singular value. This has interesting consequences: in particular, the error analysis of Strohmer & Vershynin is optimal. It also quantifies the `pre-convergence' phenomenon where the method initially seems to converge faster. This fact also allows for a fast computation of vectors x for which the Rayleigh quotient |Ax|/|x| is small: solve Ax = 0 via Randomized Kaczmarz.