A Randomized Kaczmarz Algorithm with Exponential Convergence

By Thomas Strohmer, Roman Vershynin. 2007

1,013 citations recorded by the source corpus.

The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

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

In Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “The main algorithm in this literature is the celebrated randomized Kaczmarz (RK) method [21, 56] which can be seen as special case of SGD for solving least square problems [37].”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “For example, Strohmer and Vershynin [59] show that the randomized Kaczmarz method with a particular sampling scheme achieves a linear convergence rate for the problem of solving consistent linear systems.”
Federated Optimization in Heterogeneous Networks (2018, methodology): “ local functions, while also taking into account practical systems constraints. Our dissimilarity characterization is inspired by the randomized Kaczmarz method for solving linear system of equations [16, 31], a similar assumption of which has been used to analyze variants of SGD in other settings [”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, positive): “Inspired by the analysis of Strohmer and Vershynin and Bach and Moulines, we prove convergence results for stochastic gradient descent as well as for SGD variants where gradient estimates are chosen based on a weighted sampling distribution , highlighting the role of importance sampling in SGD.”
Coordinate descent algorithms (2015, methodology): “…with respect to i k , we have By taking expectations of both sides with respect to all random variables i 0 , i 1 , . . . , and proceeding recursively, we obtain (This analysis is slightly generalized from Strohmer and Vershynin [53] to allow for nonunique solutions of Aw = b ; see also [24].)”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “ly, we noticed that [18] Deanna Needell et. al. considered importance sampling for stochastic gradient descent, where they suggested similar or the same sampling distributions. Strohmer and Vershynin [19] proposed a variant of the Kaczmarz method (an iterative method for solving systems of linear eq”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “This includes randomized Kaczmarz [Strohmer and Vershynin, 2009], randomized coordinate descent [Nesterov, 2012], and stochastic gradient methods [Needell et al., 2014].”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, methodology): “Strohmer and Vershynin [19] have recently proposed a randomized Karczmarz method for solving overdetermined consistent systems of linear equations and proved that the method enjoys global linear convergence whose rate can be expressed in terms of the condition number of the underlying matrix.”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “A randomized version of the classical Kaczmarz method was studied in a seminal paper by Strohmer and Vershynin [25].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A randomized version of the classical Kaczmarz method was studied in a seminal paper by Strohmer and Vershynin [170].”
Parallel coordinate descent methods for big data optimization (2012, methodology): “Stochastic/randomized CDMs, that is, methods where the coordinate to be updated is chosen randomly, were rst analyzed for quadratic objectives [17, 2], later independently generalized to L1-regularized problems [16] and smooth block-structured problems [7], and nally uni ed and re ned in [12, 13].”
Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms (2015, methodology): “ar equations using stochastic gradient algorithms. Using SGA to solve linear equations can be seen as a relaxation of the well known randomized Kaczmarz algorithm. For some recent reference, see e.g. Strohmer and Vershynin (2009); Needell et al. (2014). Introducingthe relaxation, the Kaczmarz iterat”
Batched Stochastic Gradient Descent with Weighted Sampling (2016, methodology): “Such theoretical guarantees were shown for the case of solving least squares problems where stochastic gradient descent coincides with the randomized Kaczmarz method in [12].”
Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms (2016, methodology): “This is exactly the rate of convergence given by Strohmer and Vershynin in [36] for the randomized Kaczmarz method.”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, methodology): “342 [30] Thomas Strohmer and Roman Vershynin.”