Randomized Kaczmarz solver for noisy linear systems
From MaRDI portal
Publication:981677
DOI10.1007/S10543-010-0265-5zbMATH Open1195.65038arXiv0902.0958OpenAlexW3126008680MaRDI QIDQ981677FDOQ981677
Authors: D. Needell 
Publication date: 2 July 2010
Published in: BIT (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0902.0958
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
iterative algorithmKaczmarz methodnumerical examplesrandomized algorithmssystems of linear equationsalgebraic reconstruction technique
Iterative numerical methods for linear systems (65F10) Random operators and equations (aspects of stochastic analysis) (60H25)
Cites Work
- Matrix Analysis
- A randomized Kaczmarz algorithm with exponential convergence
- The rate of convergence for the method of alternating projections. II
- Title not available (Why is that?)
- Condition numbers and equilibration of matrices
- On the rate of convergence of the alternating projection method in finite dimensional spaces
- A Randomized Solver for Linear Systems with Exponential Convergence
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin
- Upper bounds for nearly optimal diagonal scaling of matrices
- Comments on the randomized Kaczmarz method
Cited In (only showing first 100 items - show all)
- The row-oriented form of the regularized Kaczmarz's method
- Randomized Kaczmarz with averaging
- Randomized extended average block Kaczmarz for solving least squares
- A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
- An accelerated randomized Kaczmarz algorithm
- A weighted randomized sparse Kaczmarz method for solving linear systems
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- On Motzkin's method for inconsistent linear systems
- A refinement of an iterative orthogonal projection method
- Projected randomized Kaczmarz methods
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- A weighted randomized Kaczmarz method for solving linear systems
- A fast block coordinate descent method for solving linear least-squares 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 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
- Stochastic reformulations of linear systems: algorithms and convergence theory
- 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
- Randomized subspace actions and fusion frames
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- A randomized tensor quadrature method for high dimensional polynomial approximation
- A randomised iterative method for solving factorised linear systems
- The extensions of convergence rates of Kaczmarz-type methods
- A randomized algorithm for multivariate function approximation
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- Approximate Solutions of Linear Systems at a Universal Rate
- On block Gaussian sketching for the Kaczmarz method
- On the generally randomized extended Gauss-Seidel method
- Nonlinear Kaczmarz algorithms and their convergence
- On the regularization effect of stochastic gradient descent applied to least-squares
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
- Convergence analysis of inexact randomized iterative methods
- Single projection Kaczmarz extended algorithms
- Two-subspace projection method for coherent overdetermined systems
- An accelerated randomized Kaczmarz method via low-rank approximation
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- Randomized block Kaczmarz method with projection for solving least squares
- On convergence of the partially randomized extended Kaczmarz method
- Iterative Methods for Solving Factorized Linear Systems
- Randomized iterative methods for linear systems
- 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
- Hildreth's algorithm with applications to soft constraints for user interface layout
- Rates of convergence of randomized Kaczmarz algorithms in Hilbert spaces
- Block Kaczmarz method with inequalities
- On relaxed greedy randomized iterative methods for the solution of factorized linear systems
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Sequential function approximation on arbitrarily distributed point sets
- On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems
- Batched Stochastic Gradient Descent with Weighted Sampling
- A new greedy Kaczmarz algorithm for the solution of very 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
- Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Randomized Kaczmarz for tensor linear systems
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Linear convergence of the randomized sparse Kaczmarz method
- Choosing relaxation parameter in randomized Kaczmarz method
- Randomized Kaczmarz in adversarial distributed setting
- Effects of depth, width, and initialization: a convergence analysis of layer-wise training for deep linear neural networks
- Faster randomized block sparse Kaczmarz by averaging
- Surrounding the solution of a linear system of equations from all sides
- Maximal residual extended Kaczmarz and Gauss-Seidel methods-convergence properties and applications
- Title not available (Why is that?)
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- On adaptive stochastic heavy ball momentum for solving linear systems
- Accelerating Sparse Recovery by Reducing Chatter
- Sampled limited memory methods for massive linear inverse problems
- Quantile-based iterative methods for corrupted systems of linear equations
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Average block column action methods for solving least squares problems
- 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
- High-dimensional limit of one-pass SGD on least squares
- Constrained ERM learning of canonical correlation analysis: a least squares perspective
- Quantile-based Random Kaczmarz for corrupted linear systems of equations
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems
- 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
- On adaptive block coordinate descent methods for ridge regression
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- The greedy randomized extended Kaczmarz algorithm for noisy linear systems
- Randomized Kaczmarz algorithm with averaging and block projection
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)
