Sparse PCA via covariance thresholding

Abstract:
In sparse principal components analysis (PCA), the task is to infer a sparse, low-rank matrix from noisy observations. Johnstone and Lu proposed the popular “spiked covariance” model, wherein the population distribution is equivariant with the exception of a single direction, called the spike. Assuming that the spike direction is sparse in some basis, they also proposed a simple scheme to estimate its support based on the diagonal entries of the sample covariance. Indeed, later information-theoretic analysis demonstrated that the diagonal thresholding scheme was far from informationally optimal.

Despite considerable work over the past ten years, there is no computationally efficient method that improved over the diagonal thresholding scheme of Johnstone and Lu. We analyze a simple “covariance thresholding” algorithm and show that it outperforms the diagonal thresholding scheme. While our result also does not saturate the information theoretic threshold, recent computational hardness results indicate that it cannot be significantly improved.

The core technical analysis involves new results on sparse covariance estimation and spectral norms of kernel random matrices.

(Joint work with Andrea Montanari)

Speaker Bio:
Yash Deshpande received a B.Tech in Electrical Engineering from the Indian Institute of Technology, Bombay in 2011, and an MS and Ph.D in Electrical Engineering in 2016 from Stanford University. He is presently the Schramm postdoctoral scholar at Microsoft Research, New England and MIT Mathematics. His research interests are in statistical inference, graphical models, message passing algorithms and applied probability.