Randomized Extended Kaczmarz for Solving Least Squares

By Anastasios Zouzias, Nikolaos M. Freris. SIAM Journal on Matrix Analysis and Applications, 2012

362 citations recorded by the source corpus.

We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum $\ell_2$-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/4bdfadc1a11870defb4bc8d12dcdf693f20e5011

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 Theory and Mathematics

In Statistics and Probability

Citations in the corpus

An Asynchronous Parallel Randomized Kaczmarz Algorithm (2014, background): “Zouzias and Freris [2012] considered the case of possibly inconsistent (1).”
Rows vs. Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression (2015, methodology): “Connections between the analysis and performance of RK and RGS were recently studied in [14], which also analyzed extended variants to the Kacmarz [28] and Gauss-Siedel method [14] which always converge to the least-squares solution in both the underdetermined and overdetermined cases.”
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].”
Approximate Gradient Coding via Sparse Random Graphs (2017, methodology): “The following lemma is adapted from [26].”
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].”
Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization (2013, methodology): “The Kaczmarz method and its column-based variants [13] are quite suitable for shared-memory numerical computations, and perhaps the techniques used in this paper can be used to analyze an asynchronous variant of the Kaczmarz method.”
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].”
A new perspective on randomized gossip algorithms (2016, methodology): “The RK method was first analyzed in 2009 by Strohmer and Vershynin [13], and since then, there was an explosion of activity in refining, generalizing and extending the results [14, 15, 16, 17, 18].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, methodology): “The randomizedKaczmarz method[36, 6, 14, 20, 38, 7, 37, 12, 41, 21] for solving the least squares problem (5.”
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].”