Randomized iterative methods for linear systems
From MaRDI portal
iterative methodslinear systemsrandom pursuitrandomized coordinate descentrandomized fixed pointrandomized Kaczmarzrandomized Newtonstochastic methods
Linear equations (linear algebraic aspects) (15A06) Random matrices (algebraic aspects) (15B52) Iterative numerical methods for linear systems (65F10) Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Quadratic programming (90C20)
Abstract: We develop a novel, fundamental and surprisingly simple randomized iterative method for solving consistent linear systems. Our method has six different but equivalent interpretations: sketch-and-project, constrain-and-approximate, random intersect, random linear solve, random update and random fixed point. By varying its two parametersa positive definite matrix (defining geometry), and a random matrix (sampled in an independently and identically distributed fashion in each iteration)we recover a comprehensive array of well-known algorithms as special cases, including the randomized Kaczmarz method, randomized Newton method, randomized coordinate descent method and random Gaussian pursuit. We naturally also obtain variants of all these methods using blocks and importance sampling. However, our method allows for a much wider selection of these two parameters, which leads to a number of new specific methods. We prove exponential convergence of the expected norm of the error in a single theorem, from which existing complexity results for known variants can be obtained. However, we also give an exact formula for the evolution of the expected iterates, which allows us to give lower bounds on the convergence rate.
Recommendations
- Randomized methods for linear constraints: convergence rates and conditioning
- Stochastic iterative projection methods for large linear systems
- Randomized extended Kaczmarz for solving least squares
- On convergence rate of the randomized Kaczmarz method
- A weighted randomized Kaczmarz method for solving linear systems
Cites work
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A randomized Kaczmarz algorithm with exponential convergence
- A Stochastic Approximation Method
- Accelerated, parallel, and proximal coordinate descent
- An inexact accelerated proximal gradient method and a dual Newton-CG method for the maximal entropy problem
- Choosing the Forcing Terms in an Inexact Newton Method
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Convergence analysis of an inexact feasible interior point method for convex quadratic programming
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Faster least squares approximation
- Gaussian Markov Random Fields
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 781821 (Why is no real title available?)
- Inexact interior-point method
- Inexact Newton Methods
- Krylov Subspace Methods
- Methods of conjugate gradients for solving linear systems
- On the Distribution of a Scaled Condition Number
- Optimization of convex functions with random pursuit
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Random gradient-free minimization of convex functions
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- Solution of Sparse Indefinite Systems of Linear Equations
- The Probability That a Numerical Analysis Problem is Difficult
- Variable metric random pursuit
Cited in
(only showing first 100 items - show all)- 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
- Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- A stochastic subspace approach to gradient-free optimization in high dimensions
- On the regularization effect of stochastic gradient descent applied to least-squares
- On the generally randomized extended Gauss-Seidel method
- LSPIA, (stochastic) gradient descent, and parameter correction
- A new randomized vector algorithm for iterative solution of large linear systems
- On relaxed greedy randomized iterative methods for the solution of factorized linear systems
- Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems
- Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method
- Randomized Kaczmarz for tensor linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- A probabilistic generative model for semi-supervised training of coarse-grained surrogates and enforcing physical constraints through virtual observables
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Restarted randomized surrounding methods for solving large linear equations
- On the relaxed greedy deterministic row and column iterative methods
- Rates of convergence of randomized Kaczmarz algorithms in Hilbert spaces
- A sketched finite element method for elliptic models
- Rejoinder: ``Nonparametric regression using deep neural networks with ReLU activation function
- On block Gaussian sketching for the Kaczmarz method
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Projected randomized Kaczmarz methods
- Probabilistic linear solvers: a unifying view
- Variant of greedy randomized Kaczmarz for ridge regression
- Convergence rates for Kaczmarz-type algorithms
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- Randomized Kaczmarz with averaging
- On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- Randomized block subsampling Kaczmarz-Motzkin method
- Constrained optimization of the randomized iterative method
- Stochastic iterative projection methods for large linear systems
- Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems
- On optimal probabilities in stochastic coordinate descent methods
- Randomized methods for linear constraints: convergence rates and conditioning
- Accelerating Linear System Solutions Using Randomization Techniques
- A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments
- A Randomized Solver for Linear Systems with Exponential Convergence
- Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method
- Solving linear systems of equations with randomization, augmentation and aggregation
- scientific article; zbMATH DE number 1788242 (Why is no real title available?)
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- On greedy randomized Kaczmarz method for solving large sparse linear systems
- Randomized method of successive approximations for solving systems of linear algebraic equations
- A weighted randomized Kaczmarz method for solving linear systems
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Block regularization Kaczmarz method
- Об одной вычислительной реализации блочного метода Гаусса-Зейделя для нормальных систем уравнений
- The row-oriented form of the regularized Kaczmarz's method
- Randomized Kaczmarz Converges Along Small Singular Vectors
- 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
- Sampled limited memory methods for massive linear inverse problems
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- scientific article; zbMATH DE number 7626747 (Why is no real title available?)
- Adaptively sketched Bregman projection methods for linear systems
- Stochastic gradient descent for linear inverse problems in Hilbert spaces
- Sketched Newton-Raphson
- 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
- scientific article; zbMATH DE number 6402625 (Why is no real title available?)
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Faster randomized block Kaczmarz algorithms
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Randomized projection methods for convex feasibility: conditioning and convergence rates
- Subspace Iteration Randomization and Singular Value Problems
- Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Convergence analysis of inexact randomized iterative methods
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- Selectable Set Randomized Kaczmarz
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- Randomized numerical linear algebra: Foundations and algorithms
- 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 iteration methods: algorithmic extensions and convergence theory
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- Randomized Block Adaptive Linear System Solvers
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- A randomised iterative method for solving factorised linear systems
- A surrogate hyperplane Kaczmarz method for solving consistent linear equations
- 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
- Linearly convergent adjoint free solution of least squares problems by random descent
- The method of randomized Bregman projections for stochastic feasibility problems
This page was built for publication: Randomized iterative methods for linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3456879)
