Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma

DOI10.1007/s11075-011-9451-zzbMath1230.65051arXiv1008.4397WikidataQ124810364 ScholiaQ124810364MaRDI QIDQ639988

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

convergence; numerical examples; computer tomography; signal processing; Kaczmarz method; randomized Kaczmarz method; Johnson-Lindenstrauss technique

Mathematics Subject Classification ID

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