Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
From MaRDI portal
Publication:639988
DOI10.1007/s11075-011-9451-zzbMath1230.65051arXiv1008.4397WikidataQ124810364 ScholiaQ124810364MaRDI QIDQ639988
Yonina C. Eldar, Deanna Needell
Publication date: 11 October 2011
Published in: Numerical Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1008.4397
convergence; numerical examples; computer tomography; signal processing; Kaczmarz method; randomized Kaczmarz method; Johnson-Lindenstrauss technique
65F20: Numerical solutions to overdetermined systems, pseudoinverses
92C55: Biomedical imaging and signal processing
94A12: Signal theory (characterization, reconstruction, filtering, etc.)
Related Items
The Kaczmarz algorithm, row action methods, and statistical learning algorithms, A weighted randomized Kaczmarz method for solving linear systems, Convergence analyses based on frequency decomposition for the randomized row iterative method, Randomized Kaczmarz Converges Along Small Singular Vectors, Surrounding the solution of a linear system of equations from all sides, Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin, Sampled limited memory methods for massive linear inverse problems, Faster Randomized Block Kaczmarz Algorithms, Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions, An accelerated randomized Kaczmarz method via low-rank approximation, A Randomized Algorithm for Multivariate Function Approximation, A Randomized Tensor Quadrature Method for High Dimensional Polynomial Approximation, A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility, Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Convergence Analysis of Inexact Randomized Iterative Methods, Regularized Kaczmarz Algorithms for Tensor Recovery, A Deterministic Kaczmarz Algorithm for Solving Linear Systems, An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm, 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, On convergence rates of Kaczmarz-type methods with different selection rules of working rows, Sparse sampling Kaczmarz–Motzkin method with linear convergence, On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations, Single projection Kaczmarz extended algorithms, Greedy and randomized versions of the multiplicative Schwarz method, 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, Sequential function approximation on arbitrarily distributed point sets, A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates, Almost sure convergence of the Kaczmarz algorithm with random measurements, A geometric probability randomized Kaczmarz method for large scale linear systems, On Motzkin's method for inconsistent linear systems, Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods, On the regularization effect of stochastic gradient descent applied to least-squares, On the generally randomized extended Gauss-Seidel method, Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems, Developing Kaczmarz method for solving Sylvester matrix equations, 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, A greedy block Kaczmarz algorithm for solving large-scale 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, Sequential approximation of functions in Sobolev spaces using random samples, Projected randomized Kaczmarz methods, Randomized and fault-tolerant method of subspace corrections, Convergence analysis for Kaczmarz-type methods in a Hilbert space framework, Sequential function approximation with noisy data, Paved with good intentions: analysis of a randomized block Kaczmarz method, Randomized Kaczmarz with averaging, Randomized block subsampling Kaczmarz-Motzkin method, KACZMARZ ALGORITHM AND FRAMES, An accelerated randomized Kaczmarz algorithm, Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods, Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Randomized Kaczmarz solver for noisy linear systems
- A randomized Kaczmarz algorithm with exponential convergence
- The rate of convergence for the method of alternating projections. II
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- On the rate of convergence of the alternating projection method in finite dimensional spaces
- A Levinson--Galerkin Algorithm for Regularized Trigonometric Approximation
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- Johnson-Lindenstrauss lemma for circulant matrices**
- Extensions of Lipschitz mappings into a Hilbert space
- Sampling algorithms for l2 regression and applications
- A Randomized Solver for Linear Systems with Exponential Convergence
- Relative-Error $CUR$ Matrix Decompositions
- Analysis of Projection Methods for Solving Linear Systems with Multiple Right-Hand Sides
- An elementary proof of a theorem of Johnson and Lindenstrauss
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors