NP-Hardness and Inapproximability of Sparse PCA
arXiv:1502.05675v246 citations
Originality Highly original
AI Analysis
This work addresses the computational complexity of sparse PCA, a fundamental problem in statistics and machine learning, by establishing hardness results that are foundational rather than incremental.
The authors proved that sparse PCA is NP-hard by reducing from the clique problem, and they showed that it cannot have a fully polynomial-time approximation scheme (FPTAS) unless P=NP, with further results excluding constant-factor approximations under weaker assumptions.
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.