Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being resilient to small perturbations. Despite a long history of prior works, including explicit studies of perturbation resilience, the best known algorithmic guarantees for …