Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
From MaRDI portal
(Redirected from Publication:639988)
Abstract: The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax=b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson-Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.
Recommendations
Cites work
- scientific article; zbMATH DE number 4001918 (Why is no real title available?)
- scientific article; zbMATH DE number 687994 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- A Levinson-Galerkin algorithm for regularized trigonometric approximation
- A Randomized Solver for Linear Systems with Exponential Convergence
- A randomized Kaczmarz algorithm with exponential convergence
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Analysis of Projection Methods for Solving Linear Systems with Multiple Right-Hand Sides
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Extensions of Lipschitz mappings into a Hilbert space
- Johnson-Lindenstrauss lemma for circulant matrices
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- On the rate of convergence of the alternating projection method in finite dimensional spaces
- Randomized Kaczmarz solver for noisy linear systems
- Relative-Error $CUR$ Matrix Decompositions
- Sampling algorithms for \(l_2\) regression and applications
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- The rate of convergence for the method of alternating projections. II
Cited in
(64)- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Randomized Kaczmarz with averaging
- A geometric probability randomized Kaczmarz method for large scale linear systems
- An accelerated randomized Kaczmarz algorithm
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Greedy randomized sampling nonlinear Kaczmarz methods
- Surrounding the solution of a linear system of equations from all sides
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- On Motzkin's method for inconsistent linear systems
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- Projected randomized Kaczmarz methods
- A weighted randomized Kaczmarz method for solving linear systems
- Sampled limited memory methods for massive linear inverse problems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates
- Kaczmarz algorithm and frames
- PLSS: A Projected Linear Systems Solver
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Sequential approximation of functions in Sobolev spaces using random samples
- Selectable Set Randomized Kaczmarz
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Greedy and randomized versions of the multiplicative Schwarz method
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- Sequential function approximation with noisy data
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation \(A X B = C\)
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Faster randomized block Kaczmarz algorithms
- A randomized tensor quadrature method for high dimensional polynomial approximation
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- A randomized algorithm for multivariate function approximation
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- A biased Kaczmarz algorithm for clustered equations
- On the generally randomized extended Gauss-Seidel method
- On the regularization effect of stochastic gradient descent applied to least-squares
- Single projection Kaczmarz extended algorithms
- Convergence analysis of inexact randomized iterative methods
- An accelerated randomized Kaczmarz method via low-rank approximation
- Randomized block Kaczmarz method with projection for solving least squares
- A Kaczmarz algorithm for sequences of projections, infinite products, and applications to frames in IFS \(L^2\) spaces
- The randomized circumcentered-reflection iteration method for solving consistent linear equations
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Randomized and fault-tolerant method of subspace corrections
- Sparse sampling Kaczmarz–Motzkin method with linear convergence
- Sequential function approximation on arbitrarily distributed point sets
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized block subsampling Kaczmarz-Motzkin method
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
- Developing Kaczmarz method for solving Sylvester matrix equations
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
This page was built for publication: Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q639988)
