Sparse PCA via covariance thresholding

MaRDI QIDQ2834462zbMATH OpenFDO

Authors Yash Deshpande, Andrea Montanari

Publication date 22 November 2016

Published in Journal of Machine Learning Research (JMLR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.5179, http://jmlr.csail.mit.edu/papers/v17/15-160.html

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25)

Abstract: In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension $nimesp$ 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}sqrtn/logp$, and to fail with high probability if $s_{0}ge{K}_{2}sqrtn/logp$ 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}leKsqrtn$ (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.

Recommendations

• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Sparse principal component analysis and iterative thresholding
• Minimax sparse principal subspace estimation in high dimensions
• Sparse PCA on fixed-rank matrices
• Minimax bounds for sparse PCA with noisy high-dimensional data

Cited in

(25)

• The spectral norm of random inner-product kernel matrices
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Sparse power factorization: balancing peakiness and sample complexity
• Precise statistical analysis of classification accuracies for adversarial training
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Fundamental limits of exact support recovery in high dimensions
• Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting
• Sparse principal component analysis with missing observations
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Minimax sparse principal subspace estimation in high dimensions
• Sparse PCA on fixed-rank matrices
• Sparse principal component analysis and iterative thresholding
• Minimax bounds for sparse PCA with noisy high-dimensional data
• Optimal detection of sparse principal components in high dimension
• Sparse Variable PCA Using Geodesic Steepest Descent
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Recovering PCA and sparse PCA via hybrid-(_1,_2) sparse sampling of data elements
• Solving sparse principal component analysis with global support
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Covariance structure estimation with Laplace approximation
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Extremal eigenvalues of random kernel matrices with polynomial scaling
• Comparative study by adding bootstrapping stage in construction of biological networks
• Sparse higher-order partial least squares for simultaneous variable selection, dimension reduction and tensor denoising
• Sparse PCA: a new scalable estimator based on integer programming

This page was built for publication: Sparse PCA via covariance thresholding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2834462)