NP-hardness and inapproximability of sparse PCA

We give a reduction from clique to establish that sparse Principal Components Analysis (sparse PCA) is NP-hard. Using our reduction, we exclude a fully polynomial time approximation scheme (FPTAS) for sparse PCA (unless P=NP). Under stronger average case complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.