NP-Hardness and Inapproximability of Sparse PCA
Not on the map. Why?
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.
Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Feb 2015.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2022: 2; 2023: 2; 2024: 1; 2025: 1; 2026: 2.
8 papers.
- 2022Hardness and Algorithms for Robust and Sparse Optimizationcited by 8
- 2023Variable Selection for Kernel Two-Sample Testscited by 7
- 2022Sparse PCA on fixed-rank matricescited by 5
- 2024Efficient Sparse PCA via Block-Diagonalizationcited by 4
- 2023Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squarescited by 1
- 2025A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxationcited by 0
- 2026A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCAcited by 0
- 2026Combinatorial Sparse PCA Beyond the Spiked Identity Modelcited by 0
- 2026Combinatorial Sparse PCA Beyond the Spiked Identity Model3 Mar 2026
- 2026A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA1 Mar 2026
- 2025A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation12 Jul 2025
- 2024Efficient Sparse PCA via Block-Diagonalization18 Oct 2024
- 2023Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares8 Jun 2023
- 2023Variable Selection for Kernel Two-Sample Tests15 Feb 2023
- 2022Hardness and Algorithms for Robust and Sparse Optimization29 Jun 2022
- 2022Sparse PCA on fixed-rank matrices7 Jan 2022