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 $\\mathbf{\Sigma}$, whose top eigenvector $\\mathbf{v} \in \\mathbb{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 $\\mathbf{\Sigma} \propto \\mathbf{I}_d + \gamma \\mathbf{v}\\mathbf{v}^\top$ for some $\gamma > 0$), whereas SDP-based algorithms require no additional assumptions on $\\mathbf{\Sigma}$. We demonstrate explicit counterexample covariances $\\mathbf{\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 $\\mathbf{\Sigma}$ using $\\mathsf{poly}(s, \log(d))$ samples and $d^2 \cdot \\mathsf{poly}(s, \log(d))$ time, by providing a global convergence guarantee on the truncated power method of Yuan and Zhang (JMLR, 2013). We provide a natural generalization of our method to recovering $k$ sparse principal components. Finally, we evaluate our method on synthetic and real-world sparse PCA datasets.

Sparse PCA is a fundamental method for finding a small subset of variables that explain the dominant direction of variation in high-dimensional data. Many existing fast algorithms for sparse PCA are designed for the classical _spiked identity_ model, where the covariance matrix has the special form _identity plus a sparse spike_. In this work, we study a more general and robust setting: the covariance matrix is arbitrary, except that its leading eigenvector is sparse and separated from the rest of the spectrum. We show that several standard lightweight combinatorial methods, including diagonal thresholding, covariance thresholding, and greedy correlation-based methods, can fail in this more general model. This suggests that their success is partly tied to the special structure of the spiked identity model rather than to sparsity alone. Our main contribution is a provable, SDP-free algorithm for sparse PCA under general covariance structure. The method is a restarted truncated power method: it initializes the truncated power iteration from every coordinate basis vector, repeatedly applies the empirical covariance matrix, keeps only the largest coordinates, and finally selects the iterate with the largest empirical variance. We prove a global convergence guarantee showing that, when the top eigenvector is $s$-sparse and has a constant eigengap, the algorithm recovers a highly correlated sparse vector using $n = \widetilde{O}(s^3)$ samples and runs in time $O(nd^2 \log s)$. Thus, the algorithm achieves the efficiency of combinatorial methods, roughly $d^2 \cdot \operatorname{poly}(s,\log d)$ time, while applying beyond the spiked identity model to general covariances, where previously known provable methods with comparable sample complexity relied on substantially heavier SDP machinery. We also study the extension to sparse subspace recovery. We show that a natural deflation-based reduction from sparse $k$-PCA to repeated sparse $1$-PCA is not automatically valid in the general covariance model: even after projecting out a sparse vector well-aligned with the top component, the residual matrix can have a dense leading eigenvector. This identifies a structural barrier for standard deflation approaches. Empirically, our restarted truncated power method is robust on both synthetic and real-world sparse PCA instances, including counterexamples where simpler combinatorial heuristics fail.