Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
Provides theoretical convergence guarantees for randomized linear solvers, relevant to optimization and numerical linear algebra communities.
The paper analyzes randomized coordinate descent and iterated projection methods for linear systems, proving linear convergence rates in expectation bounded by natural condition numbers, and links these to distances to ill-posedness.
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.