Timezone: »
Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retain a sketch of the psd matrix. This paper develops a new algorithm for fixed-rank psd approximation from a sketch. The approach combines the Nyström approximation with a novel mechanism for rank truncation. Theoretical analysis establishes that the proposed method can achieve any prescribed relative error in the Schatten 1-norm and that it exploits the spectral decay of the input matrix. Computer experiments show that the proposed method dominates alternative techniques for fixed-rank psd matrix approximation across a wide range of examples.
Author Information
Joel A Tropp (Caltech)
Joel A. Tropp is Professor of Applied & Computational Mathematics at California Institute of Technology. He earned the Ph.D. degree in Computational Applied Mathematics from the University of Texas at Austin in 2004. Prof. Tropp’s work lies at the interface of applied mathematics, electrical engineering, computer science, and statistics. The bulk of this research concerns the theoretical and computational aspects of sparse approximation, compressive sampling, and randomized linear algebra. He has also worked extensively on the properties of structured random matrices. Prof. Tropp has received several major awards for young researchers, including the 2007 ONR Young Investigator Award and the 2008 Presidential Early Career Award for Scientists and Engineers. He is also winner of the 32nd annual award for Excellence in Teaching from the Associated Students of the California Institute of Technology.
Alp Yurtsever (EPFL)
Madeleine Udell (Cornell)
Volkan Cevher (EPFL)
More from the Same Authors
-
2020 Poster: On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems »
Panayotis Mertikopoulos · Nadav Hallak · Ali Kavis · Volkan Cevher -
2020 Poster: Robust Reinforcement Learning via Adversarial training with Langevin Dynamics »
Parameswaran Kamalaruban · Yu-Ting Huang · Ya-Ping Hsieh · Paul Rolland · Cheng Shi · Volkan Cevher -
2019 Poster: An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints »
Mehmet Fatih Sahin · Armin eftekhari · Ahmet Alacaoglu · Fabian Latorre · Volkan Cevher -
2019 Poster: Stochastic Frank-Wolfe for Composite Convex Minimization »
Francesco Locatello · Alp Yurtsever · Olivier Fercoq · Volkan Cevher -
2019 Poster: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Poster: Fast and Provable ADMM for Learning with Generative Priors »
Fabian Latorre · Armin eftekhari · Volkan Cevher -
2019 Spotlight: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Spotlight: Fast and Provable ADMM for Learning with Generative Priors »
Fabian Latorre · Armin eftekhari · Volkan Cevher -
2018 Poster: Online Adaptive Methods, Universality and Acceleration »
Kfir Y. Levy · Alp Yurtsever · Volkan Cevher -
2018 Poster: Mirrored Langevin Dynamics »
Ya-Ping Hsieh · Ali Kavis · Paul Rolland · Volkan Cevher -
2018 Spotlight: Mirrored Langevin Dynamics »
Ya-Ping Hsieh · Ali Kavis · Paul Rolland · Volkan Cevher -
2018 Poster: Adversarially Robust Optimization with Gaussian Processes »
Ilija Bogunovic · Jonathan Scarlett · Stefanie Jegelka · Volkan Cevher -
2018 Spotlight: Adversarially Robust Optimization with Gaussian Processes »
Ilija Bogunovic · Jonathan Scarlett · Stefanie Jegelka · Volkan Cevher -
2017 Poster: Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach »
Slobodan Mitrovic · Ilija Bogunovic · Ashkan Norouzi-Fard · Jakub M Tarnawski · Volkan Cevher -
2017 Poster: Phase Transitions in the Pooled Data Problem »
Jonathan Scarlett · Volkan Cevher -
2017 Poster: Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization »
Ahmet Alacaoglu · Quoc Tran Dinh · Olivier Fercoq · Volkan Cevher -
2016 Poster: An Efficient Streaming Algorithm for the Submodular Cover Problem »
Ashkan Norouzi-Fard · Abbas Bazzi · Ilija Bogunovic · Marwa El Halabi · Ya-Ping Hsieh · Volkan Cevher -
2016 Poster: Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation »
Ilija Bogunovic · Jonathan Scarlett · Andreas Krause · Volkan Cevher -
2016 Poster: Stochastic Three-Composite Convex Minimization »
Alp Yurtsever · Bang Cong Vu · Volkan Cevher -
2015 Poster: Preconditioned Spectral Descent for Deep Learning »
David Carlson · Edo Collins · Ya-Ping Hsieh · Lawrence Carin · Volkan Cevher -
2015 Poster: A Universal Primal-Dual Convex Optimization Framework »
Alp Yurtsever · Quoc Tran Dinh · Volkan Cevher -
2014 Workshop: Discrete Optimization in Machine Learning »
Jeffrey A Bilmes · Andreas Krause · Stefanie Jegelka · S Thomas McCormick · Sebastian Nowozin · Yaron Singer · Dhruv Batra · Volkan Cevher -
2014 Poster: Constrained convex minimization via model-based excessive gap »
Quoc Tran-Dinh · Volkan Cevher -
2014 Poster: Time--Data Tradeoffs by Aggressive Smoothing »
John J Bruer · Joel A Tropp · Volkan Cevher · Stephen Becker -
2013 Poster: High-Dimensional Gaussian Process Bandits »
Josip Djolonga · Andreas Krause · Volkan Cevher -
2012 Poster: Factoring nonnegative matrices with linear programs »
Benjamin Recht · Christopher Re · Joel A Tropp · Victor Bittorf -
2012 Poster: Active Learning of Multi-Index Function Models »
Hemant Tyagi · Volkan Cevher -
2012 Spotlight: Factoring nonnegative matrices with linear programs »
Benjamin Recht · Christopher Re · Joel A Tropp · Victor Bittorf -
2012 Tutorial: User-Friendly Tools for Studying Random Matrices »
Joel A Tropp -
2010 Poster: Practical Large-Scale Optimization for Max-norm Regularization »
Jason D Lee · Benjamin Recht · Russ Salakhutdinov · Nati Srebro · Joel A Tropp -
2009 Workshop: Manifolds, sparsity, and structured models: When can low-dimensional geometry really help? »
Richard Baraniuk · Volkan Cevher · Mark A Davenport · Piotr Indyk · Bruno Olshausen · Michael B Wakin -
2009 Poster: Learning with Compressible Priors »
Volkan Cevher -
2008 Poster: Sparse Signal Recovery Using Markov Random Fields »
Volkan Cevher · Marco F Duarte · Chinmay Hegde · Richard Baraniuk -
2008 Spotlight: Sparse Signal Recovery Using Markov Random Fields »
Volkan Cevher · Marco F Duarte · Chinmay Hegde · Richard Baraniuk