On the Approximability of Sparse PCA
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: \beginenumerate \it{em} a simple and efficient algorithm that achieves an n^-1/3-approximation; \it{em} NP-hardness of approximation to within (1-\varepsilon), for some small constant \varepsilon > 0; \it{em} SSE-hardness of approximation to within \em any constant factor; and \it{em} an \exp\exp\left(Ω\left(\sqrt\log \log n\right)\right) (“quasi-quasi-polynomial”) gap for the standard semidefinite program. \endenumerate
Cite
Text
Chan et al. "On the Approximability of Sparse PCA." Annual Conference on Computational Learning Theory, 2016.Markdown
[Chan et al. "On the Approximability of Sparse PCA." Annual Conference on Computational Learning Theory, 2016.](https://mlanthology.org/colt/2016/chan2016colt-approximability/)BibTeX
@inproceedings{chan2016colt-approximability,
title = {{On the Approximability of Sparse PCA}},
author = {Chan, Siu On and Papailliopoulos, Dimitris and Rubinstein, Aviad},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2016},
pages = {623-646},
url = {https://mlanthology.org/colt/2016/chan2016colt-approximability/}
}