A weighted randomized Kaczmarz method for solving linear systems

Abstract:

The Kaczmarz method for solving a linear system $Ax = b$ interprets such a system as a collection of equations $\left \langle a_i, x\right \rangle = b_i$, where $a_i$ is the $i$-th row of $A$. It then picks such an equation and corrects $x_{k+1} = x_k + \lambda a_i$ where $\lambda$ is chosen so that the $i$-th equation is satisfied. Convergence rates are difficult to establish. Strohmer & Vershynin established that if the order of equations is chosen randomly (with likelihood proportional to the size of $\|a_i\|^2_{\ell ^2}$), then $\mathbb {E}~ \|x_k - x\|_{\ell ^2}$ converges exponentially. We prove that if the $i$-th row is selected with likelihood proportional to $\left |\left \langle a_i, x_k \right \rangle - b_i\right |^{p}$, where $0<p<\infty$, then $\mathbb {E}~\|x_k - x\|_{\ell ^2}$ converges faster than the purely random method. As $p \rightarrow \infty$, the method de-randomizes and explains, among other things, why the maximal correction method works well.