An accelerated randomized Kaczmarz algorithm

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

Ji Liu, Stephen J. Wright

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

convergencenumerical exampleslinear equationsnormal equationsill-conditioned problemconjugate gradientrandomized Kaczmarz algorithmconsistent linear systemsNesterov 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 (37)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Introductory lectures on convex optimization. A basic course.
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• Fundamentals of Computerized Tomography
• Randomized Extended Kaczmarz for Solving Least Squares
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems

This page was built for publication: An accelerated randomized Kaczmarz algorithm