# NP-Hardness and Inapproximability of Sparse PCA

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2015.

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

- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Variable Selection for Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.07415/) (2023)
- [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)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)
- [A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA](https://mlsanity.com/paper/2603.01144/) (2026)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)

## Abstract (arXiv)

We give a reduction from sc clique to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.