  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$, 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. Assuming
the rows to be normalized, $\|a_i\|_{\ell^2}=1$, Strohmer \& Vershynin
established that if the order of equations is chosen at random, $\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. We empirically observe that the method
computes approximations of small singular vectors of $A$ as a byproduct.
