An accelerated randomized Kaczmarz algorithm

DOI10.1090/MCOM/2971MaRDI QIDQ3450034zbMATH OpenOpenAlexFDO

Authors 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

conjugate gradientconsistent linear systemsconvergenceill-conditioned problemlinear equationsNesterov accelerationnormal equationsnumerical examplesrandomized Kaczmarz algorithm

Mathematics Subject Classification ID

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

Abstract: The randomized Kaczmarz ($RK$) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$. This paper proposes an accelerated randomized Kaczmarz ($ARK$) algorithm with better convergence than the standard $RK$ algorithm on ill conditioned problems. The per-iteration cost of $RK$ and $ARK$ are similar if $A$ is dense, but $RK$ is much more able to exploit sparsity in $A$ than is $ARK$. To deal with the sparse case, an efficient implementation for $ARK$, called $SARK$, is proposed. A comparison of convergence rates and average per-iteration complexities among $RK$, $ARK$, and $SARK$ is given, taking into account different levels of sparseness and conditioning. Comparisons with the leading deterministic algorithm --- conjugate gradient applied to the normal equations --- are also given. Finally, the analysis is validated via computational testing.

Recommendations

• An accelerated randomized Kaczmarz method via low-rank approximation
• A randomized Kaczmarz algorithm with exponential convergence
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Faster randomized block Kaczmarz algorithms
• Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory
• scientific article; zbMATH DE number 7708789
• Randomized extended Kaczmarz for solving least squares
• Convergence acceleration of Kaczmarz's method
• On convergence rate of the randomized Kaczmarz method
• Projected randomized Kaczmarz methods

Cites work

• A randomized Kaczmarz algorithm with exponential convergence
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Fundamentals of Computerized Tomography
• scientific article; zbMATH DE number 3856876 (Why is no real title available?)
• scientific article; zbMATH DE number 1271381 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• Randomized extended Kaczmarz for solving least squares
• Randomized Kaczmarz solver for noisy linear systems
• Randomized methods for linear constraints: convergence rates and conditioning

Cited in

(86)

• A randomized Kaczmarz algorithm with exponential convergence
• A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin
• Sequential function approximation on arbitrarily distributed point sets
• 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
• Randomized double and triple Kaczmarz for solving extended normal equations
• Nonlinear Kaczmarz algorithms and their convergence
• On the regularization effect of stochastic gradient descent applied to least-squares
• Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
• Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
• Rates of convergence of randomized Kaczmarz algorithms in Hilbert spaces
• Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
• Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
• Sequential approximation of functions in Sobolev spaces using random samples
• Randomized and fault-tolerant method of subspace corrections
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
• Sequential function approximation with noisy data
• Randomized Kaczmarz with averaging
• Splitting-based randomized iterative methods for solving indefinite least squares problem
• The randomized Kaczmarz algorithm with the probability distribution depending on the angle
• Randomized block subsampling Kaczmarz-Motzkin method
• A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
• An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
• A Kiefer-Wolfowitz algorithm with randomized differences
• Boosted KZ and LLL Algorithms
• The Kaczmarz algorithm, row action methods, and statistical learning algorithms
• A weighted randomized Kaczmarz method for solving linear systems
• Randomized Kaczmarz Converges Along Small Singular Vectors
• Surrounding the solution of a linear system of equations from all sides
• Orthogonal projectors and systems of linear algebraic equations
• Adaptively sketched Bregman projection methods for linear systems
• RidgeSketch: a fast sketching based solver for large scale ridge regression
• Stochastic reformulations of linear systems: algorithms and convergence theory
• Randomized extended average block Kaczmarz for solving least squares
• Faster randomized block Kaczmarz algorithms
• Stochastic subspace correction methods and fault tolerance
• An accelerated randomized Kaczmarz method via low-rank approximation
• A randomized algorithm for multivariate function approximation
• The KaGE RLS algorithm
• A randomized tensor quadrature method for high dimensional polynomial approximation
• A sampling Kaczmarz-Motzkin algorithm for linear feasibility
• A Deterministic Kaczmarz Algorithm for Solving Linear Systems
• An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
• A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
• Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory
• 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
• Faster randomized block sparse Kaczmarz by averaging
• Regularized randomized iterative algorithms for factorized linear systems
• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
• A fast randomized algorithm for computing an approximate null space
• scientific article; zbMATH DE number 7708789 (Why is no real title available?)
• On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
• Randomized Kaczmarz algorithm with averaging and block projection
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
• On adaptive stochastic heavy ball momentum for solving linear systems
• A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
• Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
• The multi-step randomized Kaczmarz algorithms for solving large consistent linear equations
• Reflective block Kaczmarz algorithms for least squares
• The randomized circumcentered-reflection iteration method for solving consistent linear equations
• Randomized Kaczmarz with geometrically smoothed momentum
• Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
• On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
• The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation
• A unified convergence analysis of random sketch methods for rank deficient linear systems
• Fine-grained analysis and faster algorithms for iteratively solving linear systems
• On the fast convergence of minibatch heavy ball momentum
• Randomized iterative methods for generalized absolute value equations: solvability and error bounds
• An accelerated block randomized Kaczmarz method
• Randomized block residual steepest descent method with k-means clustering for large sparse linear systems
• Minimal error momentum Bregman-Kaczmarz
• Convergence analysis of the nonlinear Kaczmarz method for systems of nonlinear equations with componentwise convex mappings and applications to image reconstruction in multispectral CT
• Linear discriminant analysis with the randomized Kaczmarz method
• On randomized explicit block Kaczmarz method for solving large linear systems
• A greedy randomized extended block average Kaczmarz algorithm for solving least squares solutions
• On fast deterministic two-row block Kaczmarz method for solving consistent linear systems
• Deterministic row-action methods for inconsistent linear system: semiconvergence analysis and augmented least-squares solvers
• On a deterministic block Kaczmarz-type method and its acceleration for the solution of large-scale linear systems
• On the alternating randomized row-action methods with the application to data fitting
• Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
• Use of operator defect identities in multi-channel signal plus residual-analysis via iterated products and telescoping energy-residuals: applications to kernels in machine learning
• Volume Sampling and Spectral Equalization in Randomized Alternating Projections

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450034)