Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
From MaRDI portal
Publication:5112239
DOI10.1137/18M1179249zbMath1440.65045arXiv1706.01108OpenAlexW3020708521MaRDI QIDQ5112239
Publication date: 28 May 2020
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.01108
linear systemsiterative methodsstochastic methodsrandomized Kaczmarzrandomized coordinate descentrandom pursuitrandomized fixed pointrandomized Newton
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 (29)
A Deterministic Kaczmarz Algorithm for Solving Linear Systems ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Adaptively sketched Bregman projection methods for linear systems ⋮ Randomized Kaczmarz with averaging ⋮ Sketched Newton--Raphson ⋮ RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression ⋮ PLSS: A Projected Linear Systems Solver ⋮ Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification ⋮ On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations ⋮ Randomized Block Adaptive Linear System Solvers ⋮ Faster randomized block sparse Kaczmarz by averaging ⋮ 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 ⋮ On the convergence analysis of asynchronous SGD for solving consistent linear systems ⋮ The method of randomized Bregman projections for stochastic feasibility problems ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ Randomized Kaczmarz algorithm with averaging and block projection ⋮ Block sampling Kaczmarz-Motzkin methods for consistent linear systems ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ A doubly stochastic block Gauss-Seidel algorithm for solving linear equations ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ Faster Randomized Block Kaczmarz Algorithms ⋮ Stochastic quasi-gradient methods: variance reduction via Jacobian sketching ⋮ An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems ⋮ On Adaptive Sketch-and-Project for Solving Linear Systems ⋮ Convergence Analysis of Inexact Randomized Iterative Methods ⋮ Convergence and Semi-Convergence of a Class of Constrained Block Iterative Methods ⋮ Randomized Kaczmarz for tensor linear systems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel coordinate descent methods for big data optimization
- On optimal probabilities in stochastic coordinate descent methods
- Minimizing finite sums with the stochastic average gradient
- Random algorithms for convex minimization problems
- Randomized Kaczmarz solver for noisy linear systems
- A randomized Kaczmarz algorithm with exponential convergence
- Introductory lectures on convex optimization. A basic course.
- Randomized algorithms for analysis and control of uncertain systems. With applications
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Randomized algorithms for probabilistic robustness with real and complex structured uncertainty
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Distributed Coordinate Descent Method for Learning with Big Data
- Coordinate descent with arbitrary sampling I: algorithms and complexity†
- Optimization of Convex Functions with Random Pursuit
- Randomized Extended Kaczmarz for Solving Least Squares
- LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems
- Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- A fast randomized algorithm for overdetermined linear least-squares regression
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
- Revisiting Asynchronous Linear Solvers
- An Algorithm for Restricted Least Squares Regression
- Accelerated, Parallel, and Proximal Coordinate Descent
- An accelerated randomized Kaczmarz algorithm
- Randomized Iterative Methods for Linear Systems
- Robust Stochastic Approximation Approach to Stochastic Programming
- Monotone Operators and the Proximal Point Algorithm
- Stochastic algorithms for exact and approximate feasibility of robust LMIs
- Semi-stochastic coordinate descent
- Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms
- An improved data stream summary: the count-min sketch and its applications
- Parallel Stochastic Newton Method
- On Projection Algorithms for Solving Convex Feasibility Problems
- Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Understanding Machine Learning
- Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
- Linear Recursive Sequences
- A Stochastic Approximation Method
This page was built for publication: Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
