An accelerated randomized Kaczmarz algorithm

Source abstract

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 R K \rm {ARK} , and S A R K \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.