On the Approximability of Sparse PCA
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.
COLT