A Weighted Randomized Kaczmarz Method for Solving Linear Systems
share
The Kaczmarz method for solving a linear system Ax = b interprets such a system as a collection of equations ⟨ a_i, x⟩ = b_i, where a_i is the i-th row of A, then picks such an equation and corrects x_k+1 = x_k + λ a_i where λ is chosen so that the i-th equation is satisfied. Convergence rates are difficult to establish. Assuming the rows to be normalized, a_i_ℓ^2=1, Strohmer & Vershynin established that if the order of equations is chosen at random, 𝔼 x_k - x_ℓ^2 converges exponentially. We prove that if the i-th row is selected with likelihood proportional to |⟨ a_i, x_k ⟩ - b_i|^p, where 0<p<∞, then 𝔼 x_k - x_ℓ^2 converges faster than the purely random method. As p →∞, 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.
READ FULL TEXT