2013/10/10 by Ji Liu, Stephen J. Wright, Liu, Ji +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1310.2887
openalex publication_date 2013/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.