[2603.02607] Combinatorial Sparse PCA Beyond the Spiked Identity Model

Statistics > Machine Learning arXiv:2603.02607 (stat) [Submitted on 3 Mar 2026] Title:Combinatorial Sparse PCA Beyond the Spiked Identity Model Authors:Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Peiyuan Zhang View a PDF of the paper titled Combinatorial Sparse PCA Beyond the Spiked Identity Model, by Syamantak Kumar and 3 other authors View PDF HTML (experimental) 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^\top$ 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 \cdot \mathrm{polylog}(d)$ samples and $d^2 \cdot \mathrm{poly}(s, \log(d))$ time, by providing a global convergence guarantee on a variant of the tru...