Randomized Kaczmarz solver for noisy linear systems
From MaRDI portal
(Redirected from Publication:981677)
Abstract: The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system where Ax is approximately b + r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.
Recommendations
- A Randomized Solver for Linear Systems with Exponential Convergence
- Randomized extended Kaczmarz for solving least squares
- A weighted randomized Kaczmarz method for solving linear systems
- Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems
- A randomized Kaczmarz algorithm with exponential convergence
Cites work
- scientific article; zbMATH DE number 4001918 (Why is no real title available?)
- A Randomized Solver for Linear Systems with Exponential Convergence
- A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin
- A randomized Kaczmarz algorithm with exponential convergence
- Comments on the randomized Kaczmarz method
- Condition numbers and equilibration of matrices
- Matrix Analysis
- 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
- The rate of convergence for the method of alternating projections. II
- Upper bounds for nearly optimal diagonal scaling of matrices
Cited in
(only showing first 100 items - show all)- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Choosing relaxation parameter in randomized Kaczmarz method
- Randomized Kaczmarz with averaging
- A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
- The row-oriented form of the regularized Kaczmarz's method
- Randomized extended average block Kaczmarz for solving least squares
- A weighted randomized sparse Kaczmarz method for solving linear systems
- Effects of depth, width, and initialization: a convergence analysis of layer-wise training for deep linear neural networks
- An accelerated randomized Kaczmarz algorithm
- Randomized Kaczmarz in adversarial distributed setting
- Surrounding the solution of a linear system of equations from all sides
- Faster randomized block sparse Kaczmarz by averaging
- Maximal residual extended Kaczmarz and Gauss-Seidel methods-convergence properties and applications
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- On Motzkin's method for inconsistent linear systems
- A refinement of an iterative orthogonal projection method
- scientific article; zbMATH DE number 7306872 (Why is no real title available?)
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- Projected randomized Kaczmarz methods
- On adaptive stochastic heavy ball momentum for solving linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- A weighted randomized Kaczmarz method for solving linear systems
- Accelerating Sparse Recovery by Reducing Chatter
- Sampled limited memory methods for massive linear inverse problems
- A fast block coordinate descent method for solving linear least-squares problems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Quantile-based iterative methods for corrupted systems of linear equations
- A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates
- Kaczmarz algorithm and frames
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Average block column action methods for solving least squares problems
- On Chubanov's Method for Linear Programming
- Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems
- The randomized Kaczmarz method with mismatched adjoint
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Constrained ERM learning of canonical correlation analysis: a least squares perspective
- High-dimensional limit of one-pass SGD on least squares
- Sequential approximation of functions in Sobolev spaces using random samples
- Quantile-based Random Kaczmarz for corrupted linear systems of equations
- Stochastic reformulations of linear systems: algorithms and convergence theory
- 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
- A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems
- 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
- Randomized subspace actions and fusion frames
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- On adaptive block coordinate descent methods for ridge regression
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- The greedy randomized extended Kaczmarz algorithm for noisy linear systems
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Approximating mixed Hölder functions using random samples
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Randomized Kaczmarz algorithm with averaging and block projection
- Convergence of the multiplicative algebraic reconstruction technique for the inconsistent system of equations
- A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
- A literature survey of matrix methods for data science
- A randomized tensor quadrature method for high dimensional polynomial approximation
- The extensions of convergence rates of Kaczmarz-type methods
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- A randomized algorithm for multivariate function approximation
- A randomised iterative method for solving factorised linear systems
- A class of residual-based extended Kaczmarz methods for solving inconsistent linear systems
- Approximate Solutions of Linear Systems at a Universal Rate
- On block Gaussian sketching for the Kaczmarz method
- A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems
- On the generally randomized extended Gauss-Seidel method
- Reflective block Kaczmarz algorithms for least squares
- A real-time iterative projection scheme for solving the common fixed point problem and its applications
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
- Nonlinear Kaczmarz algorithms and their convergence
- On the regularization effect of stochastic gradient descent applied to least-squares
- Single projection Kaczmarz extended algorithms
- Three double multi-step randomized extended Kaczmarz methods for solving large sparse inconsistent linear systems
- Two-subspace projection method for coherent overdetermined systems
- Convergence analysis of inexact randomized iterative methods
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- Pseudo inverse versus iterated projection: novel learning approach and its application on broad learning system
- An accelerated randomized Kaczmarz method via low-rank approximation
- Randomized block Kaczmarz method with projection for solving least squares
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- On convergence of the partially randomized extended Kaczmarz method
- On the adaptive deterministic block Kaczmarz method with momentum for solving large-scale consistent linear systems
- Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems
- Iterative Methods for Solving Factorized Linear Systems
- Randomized iterative methods for linear systems
- Kaczmarz's anomaly: a surprising feature of Kaczmarz's method
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Randomized and fault-tolerant method of subspace corrections
- On the error estimate of the randomized double block Kaczmarz method
- Randomized Kaczmarz with geometrically smoothed momentum
This page was built for publication: Randomized Kaczmarz solver for noisy linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q981677)
