# On the Worst-Case Approximability of Sparse PCA

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2015.

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

- [Sparse PCA on fixed-rank matrices](https://mlsanity.com/paper/2201.02487/) (2022)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation](https://mlsanity.com/paper/2506.08670/) (2025)
- [A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA](https://mlsanity.com/paper/2603.01144/) (2026)

## Abstract (arXiv)

It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximately? Our contributions include: 1) a simple and efficient algorithm that achieves an n-1/3-approximation; 2) NP-hardness of approximation to within (1-varepsilon), for some small constant varepsilon > 0; 3) SSE-hardness of approximation to within any constant factor; and 4) an expexpleft(Omegaleft(√log log nright)right) ("quasi-quasi-polynomial") gap for the standard semidefinite program.