Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
From MaRDI portal
Publication:639988
DOI10.1007/S11075-011-9451-ZzbMATH Open1230.65051arXiv1008.4397OpenAlexW2036835849WikidataQ124810364 ScholiaQ124810364MaRDI QIDQ639988FDOQ639988
Authors: Y. C. Eldar, D. Needell 
Publication date: 11 October 2011
Published in: Numerical Algorithms (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1008.4397
Recommendations
Kaczmarz methodconvergencenumerical examplessignal processingcomputer tomographyrandomized Kaczmarz methodJohnson-Lindenstrauss technique
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Biomedical imaging and signal processing (92C55)
Cites Work
- A randomized Kaczmarz algorithm with exponential convergence
- The rate of convergence for the method of alternating projections. II
- Title not available (Why is that?)
- Extensions of Lipschitz mappings into a Hilbert space
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Sampling algorithms for \(l_2\) regression and applications
- Relative-Error $CUR$ Matrix Decompositions
- Title not available (Why is that?)
- On the rate of convergence of the alternating projection method in finite dimensional spaces
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- Title not available (Why is that?)
- Randomized Kaczmarz solver for noisy linear systems
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- A Randomized Solver for Linear Systems with Exponential Convergence
- Johnson-Lindenstrauss lemma for circulant matrices
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Analysis of Projection Methods for Solving Linear Systems with Multiple Right-Hand Sides
- A Levinson-Galerkin algorithm for regularized trigonometric approximation
Cited In (64)
- Greedy randomized sampling nonlinear Kaczmarz methods
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- PLSS: A Projected Linear Systems Solver
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Selectable Set Randomized Kaczmarz
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- 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
- The randomized circumcentered-reflection iteration method for solving consistent linear equations
- Randomized Kaczmarz with averaging
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- A geometric probability randomized Kaczmarz method for large scale linear systems
- An accelerated randomized Kaczmarz algorithm
- 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
- 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
- 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
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Sequential function approximation with noisy data
- Greedy and randomized versions of the multiplicative Schwarz method
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Regularized Kaczmarz Algorithms for Tensor Recovery
- 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
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Faster randomized block Kaczmarz algorithms
- A randomized tensor quadrature method for high dimensional polynomial approximation
- A randomized algorithm for multivariate function approximation
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- 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
- Convergence analysis of inexact randomized iterative methods
- Single projection Kaczmarz extended algorithms
- 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
- 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
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Sequential function approximation on arbitrarily distributed point sets
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Randomized block subsampling Kaczmarz-Motzkin method
- 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
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
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)
