Approximating Sparse PCA from Incomplete Data
We study how well one can recover sparse principal components of a data matrix using a sketch formed from a few of its elements. We show that for a wide class of optimization problems, if the sketch is close (in the spectral norm) to the original data matrix, then one can recover a near optimal solution to the optimization problem by using the sketch. In particular, we use this approach to obtain sparse principal components and show that for m data points in n dimensions, O( −2k max{m, n}) elements gives an -additive approximation to the sparse PCA problem (k is the stable rank of the data matrix). We demonstrate our algorithms extensively on image, text, biological and financial data. The results show that not only are we able to recover the sparse PCAs from the incomplete data, but by using our sparse sketch, the running time drops by a factor of five or more.
Summary: This papers provides an algorithm to recover sparse eigenvectors of covariance matrix (those principal components that have sparse weights in the span of data points) usinga small ( or corrupted) subsample from the data. Thealgorithm is based on sampling elements from covariance matrix to build its "sketch" and performing sparse PCA on that sketch. The authors show that under reasonable stability assumptions and a specified sampling procedure: Greedy Sparse Sampling that sets small elements to zero and Hybrid (l1,l2) Sampling that selects larger elements with higher probability, sparse PCA on a "sketch" matrix approached sparse PCA on the original covariance matrix.The theoretical guarantees (for Hybrid (l1,l2) Sampling) are given in Theorem 4, which says that for a sufficiently large sample the sketch of covariance matrix is close to the original matrix on the order of \epsilon*||A||_2, where ||A||_2 is the 2-norm of original covariance matrix and \epsilon is the accuracy parameter of the algorithm.Quality & clarity: Overall this paper is of good quality, the theoretical analysis of the stability of "sketch" matrix relative to original covariance matrix in Theorems 2 and 4 is rigorous.The empirical results on four major datasets are clearly illustrated as well as the experimental setting is clear to the reader.Originality: I think this paper lacks a certain degree of theoretical originality, the concentration bounds that they show are quite straightforward to derive, for instance the concentration on the difference of true covariance and its approximation ||A-\tilde{A}||_{2}. Though from empirical point of view it is original since sparse PCA is inherently NP-hard problem and solving it through corrupted or small sample is an original approach.Significance: I believe the suggested algorithm is significant, especially for the real assets where instances have missing features. But not only for that - in any application where sparse PCA is required, but too long to solve due to NP-hardness,we can just use sub sampling suggested in this paper for a fast approximation of sparse PCA. However, there are still some flaky details: definition of sparse principal components is a heuristic in this paper, if we employ a different heuristic, do the results get worse? The authors report 5x improvement in the computational time, but that foes not mean much, it is more relevant to know ho does the runtime scale with input size? Also, for the real applications with corrupted data you do not get to sample from the original covariance matrix, the sample is already given to you - can stability be guaranteed for that case?