# Sparse PCA via Covariance Thresholding

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2013.

## Built on by (most cited first, 22 of 22)

- [An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings](https://mlsanity.com/paper/2205.06308/) (2022)
- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [Sparse Covariance Neural Networks](https://mlsanity.com/paper/2410.01669/) (2024)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data](https://mlsanity.com/paper/2409.03335/) (2024)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Computational bottlenecks for denoising diffusions](https://mlsanity.com/paper/2503.08028/) (2025)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Learning with Covariance Matrices: Principal Component Analysis Meets Learning with Graphs](https://mlsanity.com/paper/2609.10490/) (2026)
- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)
- [Theoretical Guarantees for Sparse Principal Component Analysis based on the Elastic Net](https://mlsanity.com/paper/2212.14194/) (2022)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)
- [Efficient Covariance Estimation for Sparsified Functional Data](https://mlsanity.com/paper/2511.18237/) (2025)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)
- [Recovery thresholds for hidden weighted sparse graphs](https://mlsanity.com/paper/2606.14335/) (2026)
- [Video-based detection of cessation of breathing in pre-term infants using machine learning](https://mlsanity.com/paper/2607.05230/) (2026)
- [Joint Precision Neural Networks: Task-Aware Dependency and Predictive Learning](https://mlsanity.com/paper/2610.06023/) (2026)

## Abstract (arXiv)

In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension n× p and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components v1,dots,vr has at most s0 non-zero entries. We are particularly interested in the high dimensional regime wherein p is comparable to, or even much larger than n. In an influential paper, citejohnstone2004sparse introduced a simple algorithm that estimates the support of the principal vectors v1,dots,vr by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if s0≤ K1√n/log p, and to fail with high probability if s0≥ K2 √n/log p for two constants 0<K1,K2<∞. Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees. Here we analyze a covariance thresholding algorithm that was recently proposed by citeKrauthgamerSPCA. On the basis of numerical simulations (for the rank-one case), these authors conjectured that covariance thresholding correctly recover the support with high probability for s0≤ K√n (assuming n of the same order as p). We prove this conjecture, and in fact establish a more general guarantee including higher-rank as well as n much smaller than p. Recent lower bounds citeberthet2013computational, ma2015sum suggest that no polynomial time algorithm can do significantly better. The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before.