Randomized Kaczmarz solver for noisy linear systems

By Deanna Needell. 2009

307 citations recorded by the source corpus.

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 Ax≈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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/957025c0b5caf3e9518784604058494994c7367c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Subsequently, the method was extended and improved upon in several ways [26]–[29].”
Rows vs. Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression (2015, result): “This result was extended to the inconsistent case [16], derived via a probabilistic almost-sure convergence perspective [2], accelerated in multiple ways [5, 4, 22, 19, 18], and generalized to other settings [13, 23, 17].”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “The randomized Kaczmarz method, its variants have received considerable attention recently [31, 65, 32, 43], and several connections to existing methods were made.”
Randomized Extended Kaczmarz for Solving Least Squares (2012, methodology): “In this setting, it turns out that the randomized Kaczmarz algorithm computes an estimate vector that is within a ﬁxed distance from the solution; the distance is proportional to the norm of the “noise vector” multiplied by κ 2 F ( A ) [Nee10].”
How catastrophic can catastrophic forgetting be in linear regression? (2022, background): “There is also a randomized variant [44, 68, 75], related to our random task ordering in Section 6, which often achieves faster convergence both empirically and theoretically [69].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “Subsequently, the method was extended and improved upon in several ways [123, 204, 103, 135].”
Batched Stochastic Gradient Descent with Weighted Sampling (2016, methodology): “This method was extended to handle noisy linear systems in [13].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, unknown): “The randomizedKaczmarz method[36, 6, 14, 20, 38, 7, 37, 12, 41, 21] for solving the least squares problem (5.”
Almost Sure Convergence of the Kaczmarz Algorithm with Random Measurements (2012, background): “The work in [12] shows that the algorithm is robust against noise in the measurements yn.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “For more papers related to Kaczmarz method (randomized, greedy, cyclic update rules) we refer the interested reader to [23, 28, 38, 5, 37, 39, 9, 33, 34, 13, 31, 59, 35, 50].”
Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method (2012, methodology): “ten about randomized versions of the Kaczmarz scheme and related topics. In particular, Needell demonstrates that the randomized Kaczmarz method converges, even when the linear system is inconsistent [Nee10]. Zouzias and Freris [ZF12] exhibit a randomized procedure, based on ideas from [Pop98], that”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “This result sparked renewed interest in design of randomized methods for solving linear systems [132, 134, 49, 120, 216, 135, 175, 114].”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, background): “This result sparked renewed interest in design of randomized methods for solving linear systems [56, 57, 18, 51, 93, 58, 74, 41].”