Combinatorial Sparse PCA Beyond the Spiked Identity Model

Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance Sigma, whose top eigenvector v ∈ Rd is s-sparse. Existing sparse PCA algorithms can be broadly categorized into (1) combinatorial algorithms (e.g., diagonal or elementwise covariance thresholding) and (2) SDP-based algorithms. While combinatorial algorithms are much simpler, they are typically only analyzed under the spiked identity model (where Sigma = Id + γ vv^top for some γ > 0), whereas SDP-based algorithms require no additional assumptions on Sigma. We demonstrate explicit counterexample covariances Sigma against the success of standard combinatorial algorithms for sparse PCA, when moving beyond the spiked identity model. In light of this discrepancy, we give the first combinatorial method for sparse PCA that provably succeeds for general Sigma using s2 · polylog(d) samples and d2 · poly(s, log(d)) time, by providing a global convergence guarantee on a variant of the truncated power method of Yuan and Zhang (2013). We provide a natural generalization of our method to recovering a vector in a sparse leading eigenspace. Finally, we evaluate our method on synthetic and real-world sparse PCA datasets.