# A Weighted Randomized Kaczmarz Method for Solving Linear Systems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2020.

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

- [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)

## Abstract (arXiv)

The Kaczmarz method for solving a linear system Ax = b interprets such a system as a collection of equations leftlangle ai, xrightrangle = bi, where ai is the i-th row of A, then picks such an equation and corrects xk+1 = xk + λ ai where λ is chosen so that the i-th equation is satisfied. Convergence rates are difficult to establish. Assuming the rows to be normalized, |ai|ℓ2=1, Strohmer & Vershynin established that if the order of equations is chosen at random, mathbbE~ |xk - x|ℓ2 converges exponentially. We prove that if the i-th row is selected with likelihood proportional to left|leftlangle ai, xk rightrangle - biright|p, where 0<p<∞, then mathbbE~|xk - x|ℓ2 converges faster than the purely random method. As p rightarrow ∞, the method de-randomizes and explains, among other things, why the maximal correction method works well. We empirically observe that the method computes approximations of small singular vectors of A as a byproduct.