  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 Nystrom 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.
