Randomized Extended Kaczmarz for Solving Least-Squares
arXiv:1205.5770 · doi:10.1137/120889897
Abstract
We present a randomized iterative algorithm that exponentially converges in expectation to the minimum Euclidean norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the square condition number of the system multiplied by the number of non-zeros entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.
19 Pages, 5 figures; code is available at https://github.com/zouzias/REK
Cited by in corpus (17)
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
- Randomized Iterative Methods for Linear Systems
- Distributed Algorithms for Computation of Centrality Measures in Complex Networks
- Preasymptotic Convergence of Randomized Kaczmarz Method
- Accelerated Sampling Kaczmarz Motzkin Algorithm for The Linear Feasibility Problem
- A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
- A deterministic Kaczmarz algorithm for solving linear systems
- On the Polyak momentum variants of the greedy deterministic single and multiple row-action methods
- On Block Accelerations of Quantile Randomized Kaczmarz for Corrupted Systems of Linear Equations
- Sampled Limited Memory Methods for Massive Linear Inverse Problems
- An accelerated randomized Bregman-Kaczmarz method for strongly convex linearly constraint optimization
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- On global randomized block Kaczmarz algorithm for solving large-scale matrix equations
- On the extended randomized multiple row method for solving linear least-squares problems
- A Weighted Randomized Sparse Kaczmarz Method for Solving Linear Systems
- Linear Discriminant Analysis with the Randomized Kaczmarz Method
- Stochastic Iterative Methods for Online Rank Aggregation from Pairwise Comparisons