Approximating Sparse PCA from Incomplete Data ∗ Petros Drineas † Malik Magdon-Ismail

We study how well one can recover sparse principal components of a data matrix using a sketch formed from a few of its elements. We show that for a wide class of optimization problems, if the sketch is close (in the spectral norm) to the original data matrix, then one can recover a near optimal solution to the optimization problem by using the sketch.