DO SEMIDEFINITE RELAXATIONS SOLVE SPARSE PCA UP TO THE INFORMATION LIMIT?

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