Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma

DOI10.1007/s11075-011-9451-zzbMath1230.65051arXiv1008.4397OpenAlexW2036835849WikidataQ124810364 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

zbMATH Keywords

convergencenumerical examplescomputer tomographysignal processingKaczmarz methodrandomized Kaczmarz methodJohnson-Lindenstrauss technique

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Biomedical imaging and signal processing (92C55) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

A Deterministic Kaczmarz Algorithm for Solving Linear Systems, An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm, An accelerated randomized Kaczmarz algorithm, Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods, 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, Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study, Single projection Kaczmarz extended algorithms, Randomized Kaczmarz with averaging, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Almost sure convergence of the Kaczmarz algorithm with random measurements, 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, Sequential function approximation with noisy data, Sparse sampling Kaczmarz–Motzkin method with linear convergence, A Randomized Tensor Quadrature Method for High Dimensional Polynomial Approximation, On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations, Sequential function approximation on arbitrarily distributed point sets, Paved with good intentions: analysis of a randomized block Kaczmarz method, A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility, Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression, Randomized block subsampling Kaczmarz-Motzkin method, Greedy and randomized versions of the multiplicative Schwarz method, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Randomized block Kaczmarz method with projection for solving least squares, A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates, A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems, 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, The Kaczmarz algorithm, row action methods, and statistical learning algorithms, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Faster Randomized Block Kaczmarz Algorithms, A weighted randomized Kaczmarz method for solving linear systems, Convergence analyses based on frequency decomposition for the randomized row iterative method, Sequential approximation of functions in Sobolev spaces using random samples, Projected randomized Kaczmarz methods, On the regularization effect of stochastic gradient descent applied to least-squares, On the generally randomized extended Gauss-Seidel method, Randomized Kaczmarz Converges Along Small Singular Vectors, Randomized and fault-tolerant method of subspace corrections, Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions, Surrounding the solution of a linear system of equations from all sides, A Kaczmarz algorithm for sequences of projections, infinite products, and applications to frames in IFS \(L^2\) spaces, Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin, Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems, Sampled limited memory methods for massive linear inverse problems, KACZMARZ ALGORITHM AND FRAMES, Convergence Analysis of Inexact Randomized Iterative Methods, Developing Kaczmarz method for solving Sylvester matrix equations, Regularized Kaczmarz Algorithms for Tensor Recovery, Convergence analysis for Kaczmarz-type methods in a Hilbert space framework, An accelerated randomized Kaczmarz method via low-rank approximation, A Randomized Algorithm for Multivariate Function Approximation

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 l₂ 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