Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods

DOI10.1137/15M1014425zbMath1327.65112arXiv1503.08235MaRDI QIDQ3456873

Anna Ma, Aaditya Ramdas, Deanna Needell

Publication date: 9 December 2015

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

iterative methodoverdetermined systemrandom samplingrandomized algorithmsunderdetermined systemlinear least squares

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) 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, A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems, Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection, Randomized Iterative Methods for Linear Systems, On greedy randomized average block Kaczmarz method for solving large linear systems, On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation \(A X B = C\), On convergence rate of the randomized Kaczmarz method, On Relaxed Greedy Randomized Augmented Kaczmarz Methods for Solving Large Sparse Inconsistent Linear Systems, On Convergence of the Partially Randomized Extended Kaczmarz Method, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration, Randomized Kaczmarz methods for tensor complementarity problems, Single projection Kaczmarz extended algorithms, Randomized Kaczmarz with averaging, Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems, A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval, Convergence rates for Kaczmarz-type algorithms, 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, Approximate Solutions of Linear Systems at a Universal Rate, On adaptive block coordinate descent methods for ridge regression, Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory, Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems, On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations, On multi-step randomized extended Kaczmarz method for solving large sparse 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 randomised iterative method for solving factorised linear systems, On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems, A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems, The standard forms and convergence theory of the Kaczmarz-Tanabe type methods for solving linear systems, Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems, On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems, The extensions of convergence rates of Kaczmarz-type methods, On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems, A note on convergence rate of randomized Kaczmarz method, On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations, On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems, 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, Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression, Randomized block subsampling Kaczmarz-Motzkin method, A new greedy Kaczmarz algorithm for the solution of very large linear systems, On convergence rate of the randomized Gauss-Seidel method, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Randomized Extended Average Block Kaczmarz for Solving Least Squares, An extended row and column method for solving linear systems on a quantum computer, A doubly stochastic block Gauss-Seidel algorithm for solving linear equations, A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems, A geometric probability randomized Kaczmarz method for large scale linear systems, On Motzkin's method for inconsistent linear systems, A new randomized Gauss-Seidel method for solving linear least-squares problems, Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods, The Kaczmarz algorithm, row action methods, and statistical learning algorithms, On the error estimate of the randomized double block Kaczmarz method, 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, On the generally randomized extended Gauss-Seidel method, Gauss-Seidel method with oblique direction, Variant of greedy randomized Kaczmarz for ridge regression, On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems, Randomized Kaczmarz Converges Along Small Singular Vectors, On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Surrounding the solution of a linear system of equations from all sides, An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems, On Adaptive Sketch-and-Project for Solving Linear Systems, On relaxed greedy randomized iterative methods for the solution of factorized linear systems, Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin, Convergence Analysis of Inexact Randomized Iterative Methods, Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method, Iterative Methods for Solving Factorized Linear Systems, Regularized Kaczmarz Algorithms for Tensor Recovery, On Greedy Randomized Augmented Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems, A Partially Greedy Randomized Extended Gauss-Seidel Method for Solving Large Linear Systems, Randomized Kaczmarz for tensor linear systems, On a fast deterministic block Kaczmarz method for solving large-scale linear systems

Uses Software

• Regularization tools

Cites Work

• Unnamed Item
• Two-subspace projection method for coherent overdetermined systems
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• On Kaczmarz's projection iteration as a direct solver for linear least squares problems
• Block-iterative methods for consistent and inconsistent linear equations
• On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
• 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
• Strong underrelaxation in Kaczmarz's method for inconsistent systems
• Regularization tools: A Matlab package for analysis and solution of discrete ill-posed problems
• Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
• Almost sure convergence of the Kaczmarz algorithm with random measurements
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Projection method for solving a singular system of linear equations and its applications
• The Mathematics of Computerized Tomography
• 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
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Two Algorithms Related to the Method of Steepest Descent
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm