Randomized Kaczmarz Algorithm with Exponential Convergence

Randomized Kaczmarz Algorithm with Exponential Convergence is a stochastic row-action iterative solver introduced by Strohmer and Vershynin (2009) for consistent overdetermined linear systems A x = b (with A in C^{m x n}, m >= n, and rows a_1,...,a_m). At each iteration k, the algorithm updates x_k = x_{k-1} + ((b_{r(i)} - <x_{k-1}, a_{r(i)}>) / ||a_{r(i)}||_2^2) a_{r(i)} by orthogonally projecting x_{k-1} onto the solution hyperplane {z : <a_{r(i)}, z> = b_{r(i)}} of a row r(i) sampled independently with probability proportional to its squared Euclidean norm, P(r(i) = j) = ||a_j||_2^2 / ||A||_F^2 (Algorithm 1). By weighting row selection by ||a_j||_2^2 rather than cycling deterministically or sampling uniformly, Theorem 2 proves that the expected squared error contracts geometrically at every step according to E ||x_k - x||_2^2 <= (1 - kappa(A)^{-2})^k ||x_0 - x||_2^2, where kappa(A) = ||A||_F ||A^{-1}||_2 is the Demmel / scaled condition number (with ||A^{-1}||_2 = 1/sigma_min(A)), a rate that depends solely on kappa(A) and is completely independent of the number of equations m.