High-dimensional analysis of semidefinite relaxations for sparse principal components

In problem of sparse principal components analysis (SPCA), the goal is to use n i.i.d. samples to estimate the leading eigenvector(s) of a p times p covariance matrix, which are known a priori to be sparse, say with at most k non-zero entries. This paper studies SPCA in the high-dimensional regime, where the model dimension p, sparsity index k, and sample size n all tend to infinity simultaneously. We first analyze a simple and computationally inexpensive diagonal cut-off method, and establish a threshold of the order thetas
_diag
= n/[k
²
log(p-k)] separating success from failure. We then analyze a more complex semidefinite programming (SDP) relaxation due to dpsilaAspremont et al., and prove that it succeeds once the sample size is of the order thetas
_sdp
= n/[k log(p - k)]. Our results thus highlight an interesting tradeoff between statistical and computational efficiency in high-dimensional estimation problems.