Randomized methods for linear constraints: convergence rates and conditioning
From MaRDI portal
Abstract: We study randomized variants of two classical algorithms: coordinate descent for systems of linear equations and iterated projections for systems of linear inequalities. Expanding on a recent randomized iterated projection algorithm of Strohmer and Vershynin for systems of linear equations, we show that, under appropriate probability distributions, the linear rates of convergence (in expectation) can be bounded in terms of natural linear-algebraic condition numbers for the problems. We relate these condition measures to distances to ill-posedness, and discuss generalizations to convex systems under metric regularity assumptions.
Recommendations
Cited in
(only showing first 100 items - show all)- Metric subregularity and the proximal point method
- Linear convergence of the randomized sparse Kaczmarz method
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- A geometric probability randomized Kaczmarz method for large scale linear systems
- On Motzkin's method for inconsistent linear systems
- New characterizations of Hoffman constants for systems of linear constraints
- 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
- 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
- On the convergence of a randomized block coordinate descent algorithm for a matrix least squares problem
- Gauss-Seidel method with oblique direction
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- On relaxed greedy randomized iterative methods for the solution of factorized linear systems
- Cyclic coordinate descent in the Hölder smooth setting
- Quantum relaxed row and column iteration methods based on block-encoding
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- 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
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- 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
- A real-time iterative projection scheme for solving the common fixed point problem and its applications
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
- A note on convergence rate of randomized Kaczmarz method
- Optimization for deep learning: an overview
- Worst-case complexity of cyclic coordinate descent: O(n^2) gap with randomized version
- On convergence rate of the randomized Gauss-Seidel method
- 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 refinement of an iterative orthogonal projection method
- On the error estimate of the randomized double block Kaczmarz method
- Projected randomized Kaczmarz methods
- Variant of greedy randomized Kaczmarz for ridge regression
- Randomized and fault-tolerant method of subspace corrections
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- Coincidence points in generalized metric spaces
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Coordinate descent algorithms
- Hildreth's algorithm with applications to soft constraints for user interface layout
- Linear convergence of first order methods for non-strongly convex optimization
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Parallel coordinate descent methods for big data optimization
- Randomized Kaczmarz with averaging
- On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
- On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems
- The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- On the von Neumann and Frank-Wolfe algorithms with away steps
- Stochastic first-order methods with random constraint projection
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Random convex programs with L₁-regularization: sparsity and generalization
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- Constrained optimization of the randomized iterative method
- Inexact coordinate descent: complexity and preconditioning
- Stochastic iterative projection methods for large linear systems
- Iterative Methods for Solving Factorized Linear Systems
- A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments
- Accelerated, parallel, and proximal coordinate descent
- An accelerated randomized Kaczmarz algorithm
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Randomized iterative methods for linear systems
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Random linear programs with many variables and few constraints
- Greedy and randomized versions of the multiplicative Schwarz method
- A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- A stochastic Kaczmarz algorithm for network tomography
- Optimization methods for large-scale machine learning
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- Two-subspace projection method for coherent overdetermined systems
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized Post-optimization for t-Restrictions
- On the complexity analysis of randomized block-coordinate descent methods
- A weighted randomized Kaczmarz method for solving linear systems
- 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
- On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems
- Effects of depth, width, and initialization: a convergence analysis of layer-wise training for deep linear neural networks
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- A fast block coordinate descent method for solving linear least-squares problems
- On convergence of the partially randomized extended Kaczmarz method
- Adaptively sketched Bregman projection methods for linear systems
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- On the efficiency of random permutation for ADMM and coordinate descent
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Randomized extended average block Kaczmarz for solving least squares
- A smooth inexact penalty reformulation of convex problems with linear constraints
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
This page was built for publication: Randomized methods for linear constraints: convergence rates and conditioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169111)
