Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data Volkan Cevher EPFL
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.
The authors address the problem of fixed-rank approximation of a positive
semidefinite (psd) matrix from streaming data. The authors propose a simple
method based on the Nystrom approximation, in which a sketch is updated as
streaming data comes in, and the rank-r approximation is obtained as the best
rank-r approximation to the full Nystrom approximation. For Gaussian or
uniformly distributed (Haar) orthogonal sketch matrices, the authors prove a
standard  upper bound on the Schatten-1 (aka Nuclear) norm of the approximation error.
Detailed empirical evidence are discussed, which indicate that the proposed
method improves on previously proposed methods for fixed-rank approximation of
psd matrices. 
The paper is very well written and easy to follow. The result appears to be
novel. The proposed method admits a theoretical analysis and seems to perform
well in practice. Implementation details are discussed. This paper whould be a
welcome addition to the steaming PCA literature and is a clear accept in my
opinion. 
Minor comment: 
- The "experimental results" section does not mention which test
matrix ensemble was used, and whether the true underlying rank r was made
available to the algorithms.
- Some readers will be more familiar with the term "nuclear norm" than with the
  term "Schatten-1 norm"
- It would be nice to discuss the increase  in approximation error 
due to streaming, compared with a classical sketch algorithm that is given all
the data in advance.