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 $\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