Randomized Kaczmarz solver for noisy linear systems
From MaRDI portal
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)- Hildreth's algorithm with applications to soft constraints for user interface layout
- On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations
- 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
- Sequential function approximation on arbitrarily distributed point sets
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Batched Stochastic Gradient Descent with Weighted Sampling
- A randomized block extended Kaczmarz method with hybrid partitions for solving large inconsistent linear systems
- Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems
- 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
- A two-dimensional randomized extended Gauss-Seidel algorithm for solving least squares problems
- Randomized Kaczmarz for tensor linear systems
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Linear convergence of the randomized sparse Kaczmarz method
- 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
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)
