AN ACCELERATED RANDOMIZED KACZMARZ ALGORITHM

作者：Liu Ji^*; Wright Stephen J

来源：Mathematics of Computation, 2015, 85(297): 153-178.

DOI：10.1090/mcom/2971

• Linear equations
• randomized methods
• Nesterov acceleration

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.

• 出版日期2015-1