Combinatorial Sparse PCA Beyond the Spiked Identity Model

arXiv:2603.02607v2 Announce Type: replace-cross Abstract: 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 in R^d 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 = I_d + gamma vv^op for some gamma > 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 s^2 dot polylog(d) samples and d^2 dot 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.

Source: arXiv cs.LG | 2026-06-23