2010/08/25 by Yonina C. Eldar, Eldar, Yonina C., Deanna Needell +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1008.4397
openalex publication_date 2010/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Kaczmarz method is an algorithm for finding the solution to an\noverdetermined consistent system of linear equations Ax=b by iteratively\nprojecting onto the solution spaces. The randomized version put forth by\nStrohmer and Vershynin yields provably exponential convergence in expectation,\nwhich for highly overdetermined systems even outperforms the conjugate gradient\nmethod. In this article we present a modified version of the randomized\nKaczmarz method which at each iteration selects the optimal projection from a\nrandomly chosen set, which in most cases significantly improves the convergence\nrate. We utilize a Johnson-Lindenstrauss dimension reduction technique to keep\nthe runtime on the same order as the original randomized version, adding only\nextra preprocessing time. We present a series of empirical studies which\ndemonstrate the remarkable acceleration in convergence to the solution using\nthis modified approach.\n