An accelerated randomized Kaczmarz algorithm
Citations Over TimeTop 10% of 2015 papers
Abstract
The randomized Kaczmarz ($\rm {RK}$) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$. This paper proposes an accelerated randomized Kaczmarz ($\rm {ARK}$) algorithm with better convergence than the standard $\rm {RK}$ algorithm on ill-conditioned problems. The per-iteration cost of $\rm {RK}$ and $\rm {ARK}$ are similar if $A$ is dense, but $\rm {RK}$ is much more able to exploit sparsity in $A$ than is $\rm {ARK}$. To deal with the sparse case, an efficient implementation for $\rm {ARK}$, called $\rm {SARK}$, is proposed. A comparison of convergence rates and average per-iteration complexities among $\rm {RK}$, $\rm {ARK}$, and $\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.
Related Papers
- → On Almost α(Λ, sp)-continuous Multifunctions(2022)5 cited
- → Prim�rzerlegung in Steinschen Algebren(1964)32 cited
- → �ber unirationale Scharen auf algebraischen Mannigfaltigkeiten(1966)4 cited
- → Produkttreue Klassen universeller Algebren(1969)1 cited
- → Algebraic Set Operations, Multifunctions, and Indefinite Integrals(1996)