Stochastic Matrix-Free Equilibration

We present a novel method for approximately equilibrating a matrix using only multiplication by the matrix and its transpose. Our method is based on convex optimization and projected stochastic gradient descent, using an unbiased estimate of a gradient obtained by a randomized method. Our method pro...

Full description

Saved in:
Bibliographic Details
Published in:Journal of optimization theory and applications 2017-02, Vol.172 (2), p.436-454
Main Authors: Diamond, Steven, Boyd, Stephen
Format: Article
Language:English
Subjects:
Algorithms
Applications of Mathematics
Balancing
Calculus of Variations and Optimal Control
Optimization
Computational geometry
Convex analysis
Descent
Engineering
Estimates
Heuristic
Joints
Mathematical analysis
Mathematics
Mathematics and Statistics
Methods
Norms
Operations Research/Decision Theory
Optimization
Stochastic models
Stochasticity
Studies
Theory of Computation
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a novel method for approximately equilibrating a matrix using only multiplication by the matrix and its transpose. Our method is based on convex optimization and projected stochastic gradient descent, using an unbiased estimate of a gradient obtained by a randomized method. Our method provably converges in expectation and empirically gets good results with a small number of iterations. We show how the method can be applied as a preconditioner for matrix-free iterative algorithms, substantially reducing the iterations required to reach a given level of precision. We also derive a novel connection between equilibration and condition number, showing that equilibration minimizes an upper bound on the condition number over all choices of row and column scalings.
ISSN:0022-3239
1573-2878
DOI:10.1007/s10957-016-0990-2