Do semidefinite relaxations solve sparse PCA up to the information limit?

Abstract

Estimating the leading principal components of data, assuming they are sparse, is a central task in modern high-dimensional statistics. Many algorithms were developed for this sparse PCA problem, from simple diagonal thresholding to sophisticated semidefinite programming (SDP) methods. A key theoretical question is under what conditions can such algorithms recover the sparse principal components? We study this question for a single-spike model with an ${\ell }_0$-sparse eigenvector, in the asymptotic regime as dimension $p$ and sample size $n$ both tend to infinity. Amini and Wainwright [Ann. Statist. 37 (2009) 2877-2921] proved that for sparsity levels $k\ge \Omega (n/\log p)$, no algorithm, efficient or not, can reliably recover the sparse eigenvector. In contrast, for $k\le O(\sqrt{n/\log p})$, diagonal thresholding is consistent. It was further conjectured that an SDP approach may close this gap between computational and information limits. We prove that when $k\ge \Omega (\sqrt{n})$, the proposed SDP approach, at least in its standard usage, cannot recover the sparse spike. In fact, we conjecture that in the single-spike model, no computationally-efficient algorithm can recover a spike of ${\ell }_0$-sparsity $k\ge \Omega (\sqrt{n})$. Finally, we present empirical results suggesting that up to sparsity levels $k=O(\sqrt{n})$, recovery is possible by a simple covariance thresholding algorithm.

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

References in corpus (9)

• Regularized estimation of large covariance matrices
• Sparse PCA: Optimal rates and adaptive estimation
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Minimax sparse principal subspace estimation in high dimensions
• Statistical and computational trade-offs in estimation of sparse principal components
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Sparsistency and agnostic inference in sparse PCA

Cited by in corpus (3)

• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Finding a sparse vector in a subspace: Linear sparsity using alternating directions