Randomized Iterative Methods for Linear Systems

DOI10.1137/15M1025487zbMath1342.65110arXiv1506.03296WikidataQ30053238 ScholiaQ30053238MaRDI QIDQ3456879

Peter Richtárik, Robert M. Gower

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/1506.03296

zbMATH Keywords

linear systemsiterative methodsstochastic methodsrandomized Kaczmarzrandomized coordinate descentrandom pursuitrandomized fixed pointrandomized Newton

Mathematics Subject Classification ID

Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Quadratic programming (90C20) 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 (86)

A probabilistic generative model for semi-supervised training of coarse-grained surrogates and enforcing physical constraints through virtual observables ⋮ A Deterministic Kaczmarz Algorithm for Solving Linear Systems ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems ⋮ On optimal probabilities in stochastic coordinate descent methods ⋮ On greedy randomized average block Kaczmarz method for solving large linear systems ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ On the relaxed greedy deterministic row and column iterative methods ⋮ Adaptively sketched Bregman projection methods for linear systems ⋮ Rates of convergence of randomized Kaczmarz algorithms in Hilbert spaces ⋮ Stochastic gradient descent for linear inverse problems in Hilbert spaces ⋮ Randomized Kaczmarz with averaging ⋮ A sketched finite element method for elliptic models ⋮ Sketched Newton--Raphson ⋮ Convergence rates for Kaczmarz-type algorithms ⋮ RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression ⋮ PLSS: A Projected Linear Systems Solver ⋮ 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 ⋮ Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification ⋮ A literature survey of matrix methods for data science ⋮ 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 ⋮ Randomized Block Adaptive Linear System Solvers ⋮ On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations ⋮ A surrogate hyperplane Kaczmarz method for solving consistent linear equations ⋮ 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 ⋮ Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems ⋮ Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms ⋮ Linearly convergent adjoint free solution of least squares problems by random descent ⋮ On the convergence analysis of asynchronous SGD for solving consistent linear systems ⋮ The method of randomized Bregman projections for stochastic feasibility problems ⋮ Hessian averaging in stochastic Newton methods achieves superlinear convergence ⋮ 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 ⋮ Randomized Kaczmarz algorithm with averaging and block projection ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ Randomized block subsampling Kaczmarz-Motzkin method ⋮ Rejoinder: ``Nonparametric regression using deep neural networks with ReLU activation function ⋮ Unnamed Item ⋮ On block Gaussian sketching for the Kaczmarz method ⋮ Block sampling Kaczmarz-Motzkin methods for consistent linear systems ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments ⋮ A doubly stochastic block Gauss-Seidel algorithm for solving linear equations ⋮ On Motzkin's method for inconsistent linear systems ⋮ Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition ⋮ 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 ⋮ Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views ⋮ Faster Randomized Block Kaczmarz Algorithms ⋮ A weighted randomized Kaczmarz method for solving linear systems ⋮ Stochastic quasi-gradient methods: variance reduction via Jacobian sketching ⋮ Convergence analyses based on frequency decomposition for the randomized row iterative method ⋮ Блочный регуляризованный метод Качмажа ⋮ Об одной вычислительной реализации блочного метода Гаусса-Зейделя для нормальных систем уравнений ⋮ Строчно-ориентированная форма регуляризованного метода Качмажа ⋮ A stochastic subspace approach to gradient-free optimization in high dimensions ⋮ Projected randomized Kaczmarz methods ⋮ On the regularization effect of stochastic gradient descent applied to least-squares ⋮ On the generally randomized extended Gauss-Seidel method ⋮ Variant of greedy randomized Kaczmarz for ridge regression ⋮ Randomized Kaczmarz Converges Along Small Singular Vectors ⋮ LSPIA, (stochastic) gradient descent, and parameter correction ⋮ Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions ⋮ Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates ⋮ 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 ⋮ Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin ⋮ Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems ⋮ Convergence Analysis of Inexact Randomized Iterative Methods ⋮ Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method ⋮ Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems ⋮ A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations ⋮ Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems ⋮ Randomized Kaczmarz for tensor linear systems ⋮ On a fast deterministic block Kaczmarz method for solving large-scale linear systems ⋮ Selectable Set Randomized Kaczmarz ⋮ Generalized Gearhart-Koshy acceleration for the Kaczmarz method

Uses Software

• MatrixMarket
• CVX
• LIBSVM
• GMRFLib

Cites Work

• Unnamed Item
• Unnamed Item
• Variable metric random pursuit
• An inexact accelerated proximal gradient method and a dual Newton-CG method for the maximal entropy problem
• Randomized block Kaczmarz method with projection for solving least squares
• Faster least squares approximation
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Inexact interior-point method
• Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
• Random gradient-free minimization of convex functions
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Coordinate descent with arbitrary sampling I: algorithms and complexity^†
• Optimization of Convex Functions with Random Pursuit
• Randomized Extended Kaczmarz for Solving Least Squares
• Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming
• Krylov Subspace Methods
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Accelerated, Parallel, and Proximal Coordinate Descent
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• The Probability That a Numerical Analysis Problem is Difficult
• Row-Action Methods for Huge and Sparse Systems and Their Applications
• Inexact Newton Methods
• On the Distribution of a Scaled Condition Number
• Solution of Sparse Indefinite Systems of Linear Equations
• Gaussian Markov Random Fields
• Choosing the Forcing Terms in an Inexact Newton Method
• Methods of conjugate gradients for solving linear systems
• A Stochastic Approximation Method

This page was built for publication: Randomized Iterative Methods for Linear Systems