Computational Lower Bounds for Sparse PCA
This work addresses the trade-off between computational efficiency and statistical power in sparse PCA detection, providing complexity-theoretic lower bounds that are incremental but foundational for understanding computational limits in high-dimensional statistics.
The paper tackles the problem of detecting sparse principal components by proposing a computationally efficient method based on semidefinite programming and proving that no other efficient method can strictly improve its statistical performance, with results conditional on assumptions about the planted clique problem.
In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite programming. We also prove that the statistical performance of this test cannot be strictly improved by any computationally efficient method. Our results can be viewed as complexity theoretic lower bounds conditionally on the assumptions that some instances of the planted clique problem cannot be solved in randomized polynomial time.