An accelerated randomized Kaczmarz algorithm

DOI10.1090/mcom/2971zbMath1327.65065arXiv1310.2887OpenAlexW2963903233MaRDI QIDQ3450034

Publication date: 2 November 2015

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.2887

zbMATH Keywords

convergence numerical examples linear equations normal equations ill-conditioned problem conjugate gradient randomized Kaczmarz algorithm consistent linear systems Nesterov acceleration

Mathematics Subject Classification ID

Ill-posedness and regularization problems in numerical linear algebra (65F22) Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20)

Related Items

An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm, Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection, Orthogonal projectors and systems of linear algebraic equations, An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization, Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration, Adaptively sketched Bregman projection methods for linear systems, Rates of convergence of randomized Kaczmarz algorithms in Hilbert spaces, Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems, Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems, On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations, On convergence rates of Kaczmarz-type methods with different selection rules of working rows, A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems, Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency, Sequential function approximation with noisy data, A Randomized Tensor Quadrature Method for High Dimensional Polynomial Approximation, Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory, On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations, Sequential function approximation on arbitrarily distributed point sets, Splitting-based randomized iterative methods for solving indefinite least squares problem, The randomized Kaczmarz algorithm with the probability distribution depending on the angle, A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility, Randomized block subsampling Kaczmarz-Motzkin method, Randomized Extended Average Block Kaczmarz for Solving Least Squares, A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates, A geometric probability randomized Kaczmarz method for large scale linear systems, Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods, Faster Randomized Block Kaczmarz Algorithms, A weighted randomized Kaczmarz method for solving linear systems, Sequential approximation of functions in Sobolev spaces using random samples, On the regularization effect of stochastic gradient descent applied to least-squares, Randomized Kaczmarz Converges Along Small Singular Vectors, Stochastic subspace correction methods and fault tolerance, Randomized and fault-tolerant method of subspace corrections, Surrounding the solution of a linear system of equations from all sides, A Randomized Algorithm for Multivariate Function Approximation

Cites Work