# Do semidefinite relaxations solve sparse PCA up to the information limit?

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2013.

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

- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data](https://mlsanity.com/paper/2409.03335/) (2024)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)
- [Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms](https://mlsanity.com/paper/2202.04061/) (2022)
- [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)

## Abstract (arXiv)

Estimating the leading principal components of data, assuming they are sparse, is a central task in modern high-dimensional statistics. Many algorithms were developed for this sparse PCA problem, from simple diagonal thresholding to sophisticated semidefinite programming (SDP) methods. A key theoretical question is under what conditions can such algorithms recover the sparse principal components? We study this question for a single-spike model with an ℓ0-sparse eigenvector, in the asymptotic regime as dimension p and sample size n both tend to infinity. Amini and Wainwright [Ann. Statist. 37 (2009) 2877-2921] proved that for sparsity levels k≥Omega(n/log p), no algorithm, efficient or not, can reliably recover the sparse eigenvector. In contrast, for k≤ O(√n/log p), diagonal thresholding is consistent. It was further conjectured that an SDP approach may close this gap between computational and information limits. We prove that when k≥Omega(√n), the proposed SDP approach, at least in its standard usage, cannot recover the sparse spike. In fact, we conjecture that in the single-spike model, no computationally-efficient algorithm can recover a spike of ℓ0-sparsity k≥Omega(√n). Finally, we present empirical results suggesting that up to sparsity levels k=O(√n), recovery is possible by a simple covariance thresholding algorithm.