Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
Joel A Tropp, Alp Yurtsever, Madeleine Udell, Volkan Cevher
Abstract
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.
BibTeX
@inproceedings{NIPS2017_4558dbb6,
author = {Tropp, Joel A and Yurtsever, Alp and Udell, Madeleine and Cevher, Volkan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/4558dbb6f6f8bb2e16d03b85bde76e2c-Paper.pdf},
volume = {30},
year = {2017}
}