An accelerated randomized Kaczmarz algorithm
Ji Liu, Stephen J. Wright · Mathematics of Computation · 2015
The randomized Kaczmarz ( R K \rm {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 \rm {ARK} ) algorithm with better convergence than the standard R K \rm {RK} algorithm on ill-conditioned problems. The per-iteration cost of R K \rm {RK} and A R K \rm {ARK} are similar if A A is dense, but R K \rm {RK} is much more able to exploit sparsity in A A than is A R K \rm {ARK} . To deal with the sparse case, an efficient implementation for A R K \rm {ARK} , called S A R K \rm {SARK} , is proposed. A comparison of convergence rates and average per-iteration complexities among R K \rm {RK} , A