Randomized Kaczmarz solver for noisy linear systems

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.

Cited by in corpus (19)

• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Randomized Extended Kaczmarz for Solving Least-Squares
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Randomized Iterative Methods for Linear Systems
• On the Randomized Kaczmarz Algorithm
• A literature survey of matrix methods for data science
• Accelerated Sampling Kaczmarz Motzkin Algorithm for The Linear Feasibility Problem
• A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions
• On the exponential convergence of the Kaczmarz algorithm
• On Block Accelerations of Quantile Randomized Kaczmarz for Corrupted Systems of Linear Equations
• On the fast convergence of minibatch heavy ball momentum
• Sampled Limited Memory Methods for Massive Linear Inverse Problems
• Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
• Linear Discriminant Analysis with the Randomized Kaczmarz Method
• Convergence Analysis of Nonlinear Kaczmarz Method for Systems of Nonlinear Equations with Component-wise Convex Mapping
• A Weighted Randomized Sparse Kaczmarz Method for Solving Linear Systems
• Stochastic Iterative Methods for Online Rank Aggregation from Pairwise Comparisons
• Approximating mixed Hölder functions using random samples
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices