An accelerated randomized Kaczmarz algorithm

The randomized Kaczmarz ($\rm {RK}$) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$. This paper proposes an accelerated randomized Kaczmarz ($\rm {ARK}$) algorithm with better convergence than the standard $\rm {RK}$ algorithm on ill-conditioned problems. The per-iteration cost of $\rm {RK}$ and $\rm {ARK}$ are similar if $A$ is dense, but $\rm {RK}$ is much more able to exploit sparsity in $A$ than is $\rm {ARK}$. To deal with the sparse case, an efficient implementation for $\rm {ARK}$, called $\rm {SARK}$, is proposed. A comparison of convergence rates and average per-iteration complexities among $\rm {RK}$, $\rm {ARK}$, and $\rm {SARK}$ is given, taking into account different levels of sparseness and conditioning. Comparisons with the leading deterministic algorithm -- conjugate gradient applied to the normal equations -- are also given. Finally, the analysis is validated via computational testing.