Randomized iterative methods for linear systems
From MaRDI portal
iterative methodslinear systemsstochastic methodsrandomized coordinate descentrandomized Kaczmarzrandom pursuitrandomized fixed pointrandomized Newton
Quadratic programming (90C20) Complexity and performance of numerical algorithms (65Y20) Random matrices (algebraic aspects) (15B52) Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Linear equations (linear algebraic aspects) (15A06) Iterative numerical methods for linear systems (65F10)
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
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 781821 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A Stochastic Approximation Method
- A randomized Kaczmarz algorithm with exponential convergence
- 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
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Gaussian Markov Random Fields
- Inexact Newton Methods
- Inexact interior-point method
- 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 Kaczmarz solver for noisy linear systems
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized extended Kaczmarz for solving least squares
- 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)- A fast Bregman projection method for linearly constrained optimization problems
- Convergence analysis of two-level methods with general coarse solvers
- A Spectrally Damped Tensor Randomized Kaczmarz Method for Doubly Noisy Tensor Systems
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Accelerating Linear System Solutions Using Randomization Techniques
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- On a nonlinear fast deterministic block Kaczmarz method for solving nonlinear equations
- Randomized Kaczmarz with averaging
- Convergence of a randomized Douglas-Rachford method for linear system
- On optimal probabilities in stochastic coordinate descent methods
- The method of randomized Bregman projections for stochastic feasibility problems
- The row-oriented form of the regularized Kaczmarz's method
- Об одной вычислительной реализации блочного метода Гаусса-Зейделя для нормальных систем уравнений
- Randomized extended average block Kaczmarz for solving least squares
- Rejoinder: ``Nonparametric regression using deep neural networks with ReLU activation function
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Greedy randomized sampling nonlinear Kaczmarz methods
- A Randomized Solver for Linear Systems with Exponential Convergence
- Surrounding the solution of a linear system of equations from all sides
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Solving, tracking and stopping streaming linear inverse problems
- Hessian averaging in stochastic Newton methods achieves superlinear convergence
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A guide to stochastic optimisation for large-scale inverse problems
- On Motzkin's method for inconsistent linear systems
- Linearly convergent adjoint free solution of least squares problems by random descent
- scientific article; zbMATH DE number 7626747 (Why is no real title available?)
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- Projected randomized Kaczmarz methods
- Minimal error momentum Bregman-Kaczmarz
- On adaptive stochastic heavy ball momentum for solving linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Accelerated double-sketching subspace Newton
- Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming
- On convergence of a sketch-and-project method for the matrix equation AXB = C
- Mathematical analysis of a randomized method for fractional Carathéodory type equation with time-irregular coefficients
- Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
- A weighted randomized Kaczmarz method for solving linear systems
- Sampled limited memory methods for massive linear inverse problems
- On the greedy coordinate descent methods for solving large linear least-squares problems
- Randomized Kaczmarz Converges Along Small Singular Vectors
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Greedy capped nonlinear Kaczmarz methods
- Randomized numerical linear algebra: Foundations and algorithms
- Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition
- A probabilistic generative model for semi-supervised training of coarse-grained surrogates and enforcing physical constraints through virtual observables
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Average block column action methods for solving least squares problems
- PLSS: A Projected Linear Systems Solver
- scientific article; zbMATH DE number 7733450 (Why is no real title available?)
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- The equivalence of the randomized extended Gauss-Seidel and randomized extended Kaczmarz methods
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Randomized Block Adaptive Linear System Solvers
- On greedy randomized Kaczmarz method for solving large sparse linear systems
- Randomized method of successive approximations for solving systems of linear algebraic equations
- Generalized Gearhart-Koshy acceleration for the Kaczmarz method
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Randomized projection methods for convex feasibility: conditioning and convergence rates
- Selectable Set Randomized Kaczmarz
- On randomized multiple row-action methods for linear feasibility problems
- Stochastic reformulations of linear systems: algorithms and convergence theory
- A new randomized Gauss-Seidel method for solving linear least-squares problems
- The sparse Kaczmarz method with surrogate hyperplane for the regularized basis pursuit problem
- Adaptive Bregman-Kaczmarz: an approach to solve linear inverse problems with independent noise exactly
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- A residual-based surrogate hyperplane extended Kaczmarz algorithm for large least squares problems
- FastAGMGar: an aggregation-based algebraic multigrid method
- Bregman methods for large-scale optimization with applications in imaging
- Randomized methods for linear constraints: convergence rates and conditioning
- Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation
- Probabilistic linear solvers: a unifying view
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- On adaptive block coordinate descent methods for ridge regression
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- scientific article; zbMATH DE number 6402625 (Why is no real title available?)
- Subspace Iteration Randomization and Singular Value Problems
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Frontal slice approaches for tensor linear systems
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Sketched Newton-Raphson
- Randomized Kaczmarz algorithm with averaging and block projection
- Block regularization Kaczmarz method
- On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
- A literature survey of matrix methods for data science
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- Faster randomized block Kaczmarz algorithms
- On greedy multi-step inertial randomized Kaczmarz method for solving linear systems
- Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- A randomised iterative method for solving factorised linear systems
- Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory
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)
