An accelerated randomized Kaczmarz algorithm

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