Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950812 | Information Processing Letters | 2017 | 4 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Malik Magdon-Ismail,