Abstract

The randomized Kaczmarz (RK) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$ . This paper proposes an accelerated randomized Kaczmarz (ARK) algorithm with better convergence than the standard RK algorithm on ill conditioned problems. The per-iteration cost of RK and ARK are similar if $A$ is dense, but RK is much more able to exploit sparsity in $A$ than is ARK. To deal with the sparse case, an efficient implementation for ARK, called SARK, is proposed. A comparison of convergence rates and average per-iteration complexities among RK, ARK, and 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.