Mathematics – Statistics Theory
Scientific paper
2008-03-27
Annals of Statistics 2009, Vol. 37, No. 5B, 2877-2921
Mathematics
Statistics Theory
Published in at http://dx.doi.org/10.1214/08-AOS664 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of
Scientific paper
10.1214/08-AOS664
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.
Amini Arash A.
Wainwright Martin J.
No associations
LandOfFree
High-dimensional analysis of semidefinite relaxations for sparse principal components does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with High-dimensional analysis of semidefinite relaxations for sparse principal components, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-dimensional analysis of semidefinite relaxations for sparse principal components will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-173518