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)- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- On greedy randomized coordinate updating iteration methods for solving symmetric eigenvalue problems
- Randomized block proximal damped Newton method for composite self-concordant minimization
- Convergence analysis of two-level methods with general coarse solvers
- Survey of a class of iterative row-action methods: the Kaczmarz method
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- On extended randomized Kaczmarz algorithm for solving Tikhonov regularization problem
- Cyclic coordinate descent in the Hölder smooth setting
- Efficient sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm
- Parallel coordinate descent methods for big data optimization
- Schwarz iterative methods: infinite space splittings
- On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
- Randomized Kaczmarz with averaging
- Inexact coordinate descent: complexity and preconditioning
- Convergence of a randomized Douglas-Rachford method for linear system
- Randomized extended average block Kaczmarz for solving least squares
- A geometric probability randomized Kaczmarz method for large scale linear systems
- Effects of depth, width, and initialization: a convergence analysis of layer-wise training for deep linear neural networks
- An accelerated randomized Kaczmarz algorithm
- On constrained Kaczmarz algorithm with momentum for image reconstruction
- Randomized Kaczmarz in adversarial distributed setting
- Surrounding the solution of a linear system of equations from all sides
- An extended row and column method for solving linear systems on a quantum computer
- On greedy randomized average block Kaczmarz method for solving large linear systems
- A distributed computing method integrating improved gradient projection for solving stochastic traffic equilibrium problem
- Maximal residual extended Kaczmarz and Gauss-Seidel methods-convergence properties and applications
- A modified partially randomized extended Kaczmarz iteration method
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- On Motzkin's method for inconsistent linear systems
- A refinement of an iterative orthogonal projection method
- Linearly convergent adjoint free solution of least squares problems by random descent
- A generic coordinate descent solver for non-smooth convex optimisation
- Randomized Gauss-Seidel iterative algorithms for extreme learning machines
- Projected randomized Kaczmarz methods
- On adaptive stochastic heavy ball momentum for solving linear systems
- A class of coordinate descent methods with angle probability for solving linear systems
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- A weighted randomized Kaczmarz method for solving linear systems
- A fast block coordinate descent method for solving linear least-squares problems
- On the greedy coordinate descent methods for solving large linear least-squares problems
- A block coordinate descent linear least squares solver by quantile statistics
- Randomized Kaczmarz Converges Along Small Singular Vectors
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Randomized numerical linear algebra: Foundations and algorithms
- Randomized progressive iterative approximation for B-spline curve and surface fittings
- 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
- Coincidence points in generalized metric spaces
- Optimization methods for large-scale machine learning
- On the efficiency of random permutation for ADMM and coordinate descent
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
- Modified partially randomized extended Kaczmarz method with residual for solving large sparse linear systems
- Kaczmarz-type methods for solving matrix equations
- The equivalence of the randomized extended Gauss-Seidel and randomized extended Kaczmarz methods
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Randomized projection methods for convex feasibility: conditioning and convergence rates
- On randomized multiple row-action methods for linear feasibility problems
- Stochastic reformulations of linear systems: algorithms and convergence theory
- A smooth inexact penalty reformulation of convex problems with linear constraints
- 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
- Greedy and randomized versions of the multiplicative Schwarz method
- On convergence rates of Kaczmarz-type methods with different selection rules of working rows
- A greedy randomized average block projection method for linear feasibility problems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Accelerated, parallel, and proximal coordinate descent
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- On adaptive block coordinate descent methods for ridge regression
- Linear convergence of first order methods for non-strongly convex optimization
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Random nonlinear fusion frames from averaged operator iterations
- Stochastic first-order methods with random constraint projection
- A stochastic Kaczmarz algorithm for network tomography
- On the complexity analysis of randomized block-coordinate descent methods
- Local linear convergence of proximal coordinate descent algorithm
- Random convex programs with L₁-regularization: sparsity and generalization
- On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- Randomized iterative methods for tensor regression under the t-product
- Faster randomized block Kaczmarz algorithms
- On greedy multi-step inertial randomized Kaczmarz method for solving linear systems
- 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
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
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)
