Abstract

In sparse principal component analysis we are given noisy observations of a lowrank matrix of dimension n × p and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here that the principal components have at most non-zero entries respectively, and study the high-dimensional regime in which p is of the same order as n. In an influential paper, Johnstone and Lu [JL04] introduced a simple algorithm that estimates the support of the principal vectors by the largest entries in the diagonal of the empirical covariance. p This method can be shown to succeed with highpprobability if and to fail with high probability if for two constants Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees. Here we analyze a covariance thresholding algorithm that was recently proposed by Krauthgamer, Nadler and Vilenchik [KNV13]. We confirm empirical evidence presented by these authors and rigorously ? prove that the algorithm succeeds with high probability for k of order Recent conditional lower bounds [BR13] suggest that it might be impossible to do significantly better. The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before.