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 ann 1=3 -approximation; 2. NP-hardness of approximation to within (1 "), for some small constant" > 0; 3. SSE-hardness of approximation to within any constant factor; and 4. an exp exp p log logn (“quasi-quasi-polynomial”) gap for the standard semidefinite program.
['Siu On Chan', 'Dimitris Papailliopoulos', 'Aviad Rubinstein']
On the Approximability of Sparse PCA