Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage

By Alp Yurtsever, Madeleine Udell, Joel A. Tropp, Volkan Cevher. 2017

100 citations recorded by the source corpus.

This paper considers a fundamental class of convex matrix optimization problems with low-rank solutions. We show it is possible to solve these problem using far less memory than the natural size of the decision variable when the problem data has a concise representation. Our proposed method, SketchyCGM, is the first algorithm to offer provable convergence to an optimal point with an optimal memory footprint. SketchyCGM modifies a standard convex optimization method - the conditional gradient method - to work on a sketched version of the decision variable, and can recover the solution from this sketch. In contrast to recent work on non-convex methods for this problem class, SketchyCGM is a convex method; and our convergence guarantees do not rely on statistical assumptions.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, background): “If the target matrices are known to be exactly low-ranked (instead of just low stable rank), Yurtsever et al. (2017) show that it is sometimes possible to converge to the optima using low rank approximations of the gradients without the need for error feedback.”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “These approaches include gauge duality methods [22], [23] and sketching methods [24].”