On the Worst-Case Approximability of Sparse PCA
arXiv:1507.05950
Abstract
It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximately? Our contributions include: 1) a simple and efficient algorithm that achieves an -approximation; 2) NP-hardness of approximation to within , for some small constant ; 3) SSE-hardness of approximation to within any constant factor; and 4) an ("quasi-quasi-polynomial") gap for the standard semidefinite program.
arXiv comment20 pages
References in corpus (7)
- Generalized power method for sparse principal component analysis
- Sparse principal component analysis and iterative thresholding
- Optimal detection of sparse principal components in high dimension
- Truncated Power Method for Sparse Eigenvalue Problems
- Sparse PCA via Bipartite Matchings
- Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
- Computational Complexity of Certifying Restricted Isometry Property