A Weighted Randomized Kaczmarz Method for Solving Linear Systems

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.