Randomized Kaczmarz with averaging

DOI10.1007/s10543-020-00824-1zbMath1460.15005arXiv2002.04126OpenAlexW3048811459MaRDI QIDQ2660609

Thomas K. Tu, Denali Molitor, Jacob D. Moorman, Deanna Needell

Publication date: 31 March 2021

Published in: BIT (Search for Journal in Brave)

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

zbMATH Keywords

parallel methodsinconsistent linear systemsrandomized Kaczmarz methodalgebraic reconstruction technique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Parallel algorithms in computer science (68W10) Iterative numerical methods for linear systems (65F10) Random matrices (algebraic aspects) (15B52) Complexity and performance of numerical algorithms (65Y20) Randomized algorithms (68W20) Linear equations (linear algebraic aspects) (15A06)

Related Items

A Deterministic Kaczmarz Algorithm for Solving Linear Systems, An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm, On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations, Randomized Kaczmarz methods for tensor complementarity problems, Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems, On adaptive block coordinate descent methods for ridge regression, Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems, Faster randomized block sparse Kaczmarz by averaging, Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems, 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, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, A weighted randomized Kaczmarz method for solving linear systems, On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems, Randomized double and triple Kaczmarz for solving extended normal equations, On the regularization effect of stochastic gradient descent applied to least-squares, Surrounding the solution of a linear system of equations from all sides, Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method, Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems

Uses Software

• HOGWILD

Cites Work

• Unnamed Item
• Unnamed Item
• Two-subspace projection method for coherent overdetermined systems
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Block-iterative methods for consistent and inconsistent linear equations
• On the acceleration of Kaczmarz's method for inconsistent linear systems
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• The angles between the null spaces of X rays
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Block-iterative projection methods for parallel computation of solutions to convex feasibility problems
• Almost sure convergence of the Kaczmarz algorithm with random measurements
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Randomized Extended Kaczmarz for Solving Least Squares
• Block Stochastic Gradient Iteration for Convex and Nonconvex Optimization
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• Randomized Iterative Methods for Linear Systems
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Batched Stochastic Gradient Descent with Weighted Sampling
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
• Faster Randomized Block Kaczmarz Algorithms
• Component-Averaged Row Projections: A Robust, Block-Parallel Scheme for Sparse Linear Systems
• A Stochastic Approximation Method
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm