Sparse PCA via Covariance Thresholding

Abstract

In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension $n\times p$ and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_r$ has at most $s_0$ non-zero entries. We are particularly interested in the high dimensional regime wherein $p$ is comparable to, or even much larger than $n$. In an influential paper, \cite{johnstone2004sparse} introduced a simple algorithm that estimates the support of the principal vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_r$ by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if $s_0\le K_1\sqrt{n/\log p}$, and to fail with high probability if $s_0\ge K_2\sqrt{n/\log p}$ for two constants $0<K_1,K_2<\infty$. 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 \cite{KrauthgamerSPCA}. On the basis of numerical simulations (for the rank-one case), these authors conjectured that covariance thresholding correctly recover the support with high probability for $s_0\le K\sqrt{n}$ (assuming $n$ of the same order as $p$). We prove this conjecture, and in fact establish a more general guarantee including higher-rank as well as $n$ much smaller than $p$. Recent lower bounds \cite{berthet2013computational, ma2015sum} suggest that no polynomial time algorithm can 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.

40 pages, 3 figures, preprint

References in corpus (5)

• Sparse Principal Components Analysis
• Computational barriers in minimax submatrix detection
• Computational Lower Bounds for Sparse PCA
• Sum-of-Squares Lower Bounds for Sparse PCA
• The Spectral Norm of Random Inner-Product Kernel Matrices

Cited by in corpus (11)

• Mean-field message-passing equations in the Hopfield model and its generalizations
• Sum-of-Squares Lower Bounds for Sparse PCA
• Sparse and Functional Principal Components Analysis
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Subexponential-Time Algorithms for Sparse PCA
• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data