A Caltech Library Service

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

Yurtsever, Alp and Udell, Madeleine and Tropp, Joel A. and Cevher, Volkan (2017) Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modifies a standard convex optimization scheme, the conditional gradient method, to store only a small randomized sketch of the matrix variable. After the optimization terminates, the algorithm extracts a low-rank approximation of the solution from the sketch. In contrast to nonconvex heuristics, the guarantees for SketchyCGM do not rely on statistical models for the problem data. Numerical work demonstrates the benefits of SketchyCGM over heuristics.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Udell, Madeleine0000-0002-3985-915X
Tropp, Joel A.0000-0003-1024-1791
Additional Information:© 2017 by the author(s). Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS) 2017, Fort Lauderdale, Florida, USA. JMLR: W&CP volume 54.
Record Number:CaltechAUTHORS:20180828-145534045
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89263
Deposited By: Tony Diaz
Deposited On:28 Aug 2018 22:31
Last Modified:28 Aug 2018 22:31

Repository Staff Only: item control page