Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

2008/06/18 by D. Leventhal, Leventhal, D., Adrian S. Lewis +1 · 9 citations
Engineering · Mathematics · #15A12 #15A39 #65F10 #90C25 #Advanced Optimization Algorithms Research #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.0806.3015

openalex publication_date 2008/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The Approximation of One Matrix by Another of Lower Rank
• Local convergence for alternating and averaged nonconvex projections

Cited by

• Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
• Beyond Expectation: Concentration Inequalities for Randomized Iterative Methods
• Accelerated Evolving Set Processes for Local PageRank Computation
• Random Nonlinear Fusion Frames from Averaged Operator Iterations
• Sample Abundance for Signal Processing: A Brief Introduction
• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
• Connecting randomized iterative methods with Krylov subspaces
• Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
• Linearly Convergent First-Order Algorithms for Semi-definite Programming

Related

• On pseudoinverse-free randomized methods for linear systems: Unified framework and acceleration
• Randomized projection methods for convex feasibility problems: conditioning and convergence rates
• Faster Convergence of a Randomized Coordinate Descent Method for Linearly Constrained Optimization Problems
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence\n Theory