High-dimensional analysis of semidefinite relaxations for sparse principal components

Abstract

Principal component analysis (PCA) is a classical method for dimensionality reduction based on extracting the dominant eigenvectors of the sample covariance matrix. However, PCA is well known to behave poorly in the ``large $p$, small $n$'' setting, in which the problem dimension $p$ is comparable to or larger than the sample size $n$. This paper studies PCA in this high-dimensional regime, but under the additional assumption that the maximal eigenvector is sparse, say, with at most $k$ nonzero components. We consider a spiked covariance model in which a base matrix is perturbed by adding a $k$-sparse maximal eigenvector, and we analyze two computationally tractable methods for recovering the support set of this maximal eigenvector, as follows: (a) a simple diagonal thresholding method, which transitions from success to failure as a function of the rescaled sample size ${\theta }_{\mathrm{dia}}(n,p,k)=n/[k^2\log (p-k)]$; and (b) a more sophisticated semidefinite programming (SDP) relaxation, which succeeds once the rescaled sample size ${\theta }_{\mathrm{sdp}}(n,p,k)=n/[k\log (p-k)]$ is larger than a critical threshold. In addition, we prove that no method, including the best method which has exponential-time complexity, can succeed in recovering the support if the order parameter ${\theta }_{\mathrm{sdp}}(n,p,k)$ is below a threshold. Our results thus highlight an interesting trade-off between computational and statistical efficiency in high-dimensional inference.

Published in at http://dx.doi.org/10.1214/08-AOS664 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• High-dimensional graphs and variable selection with the Lasso
• Regularized estimation of large covariance matrices
• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Augmented sparse principal component analysis for high dimensional data

Cited by in corpus (20)

• Estimation of high-dimensional low-rank matrices
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Computational and Statistical Tradeoffs via Convex Relaxation
• Minimax sparse principal subspace estimation in high dimensions
• On statistics, computation and scalability
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Statistical and computational trade-offs in estimation of sparse principal components
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Phase Transitions in Sparse PCA
• Fundamental limits of detection in the spiked Wigner model
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Minimax estimation in sparse canonical correlation analysis
• Sparsistency and agnostic inference in sparse PCA
• Sampled forms of functional PCA in reproducing kernel Hilbert spaces
• Rate-optimal posterior contraction for sparse PCA
• Estimation of functionals of sparse covariance matrices
• Learning a Factor Model via Regularized PCA
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing