# Combinatorial Sparse PCA Beyond the Spiked Identity Model

arXiv: https://arxiv.org/abs/2603.02607 · HTML: https://mlsanity.com/paper/2603.02607/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 60 references that are in the map.
- First posted on arXiv 3 Mar 2026.

## Builds on (most cited first, 27 of 27)

- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain](https://mlsanity.com/paper/1607.03463/) (2016)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Non-Convex Matrix Completion Against a Semi-Random Adversary](https://mlsanity.com/paper/1803.10846/) (2018)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [NP-Hardness and Inapproximability of Sparse PCA](https://mlsanity.com/paper/1502.05675/) (2015)
- [Dueling Optimization with a Monotone Adversary](https://mlsanity.com/paper/2311.11185/) (2023)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Sparse PCA from Sparse Linear Regression](https://mlsanity.com/paper/1811.10106/) (2018)
- [Sparse PCA: a Geometric Approach](https://mlsanity.com/paper/2210.06590/) (2022)
- [Algorithms approaching the threshold for semi-random planted clique](https://mlsanity.com/paper/2212.05619/) (2022)
- [Gradient-based Sparse Principal Component Analysis with Extensions to Online Learning](https://mlsanity.com/paper/1911.08048/) (2019)
- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (2023)
- [Semirandom Planted Clique and the Restricted Isometry Property](https://mlsanity.com/paper/2404.14159/) (2024)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Sparse principal component analysis and its l1-relaxation](https://mlsanity.com/paper/1712.00800/) (2017)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [A New Basis for Sparse Principal Component Analysis](https://mlsanity.com/paper/2007.00596/) (2020)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models](https://mlsanity.com/paper/2412.14315/) (2024)

## Abstract (arXiv)

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.