{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T03:11:00Z","timestamp":1792120260605,"version":"4.4.0"},"reference-count":41,"publisher":"Institute of Mathematical Statistics","issue":"5B","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2009,10,1]]},"abstract":"<jats:p>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 \u201clarge p, small n\u201d 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 \u03b8dia(n, p, k)=n\/[k2log(p\u2212k)]; and (b) a more sophisticated semidefinite programming (SDP) relaxation, which succeeds once the rescaled sample size \u03b8sdp(n, p, k)=n\/[klog(p\u2212k)] 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 \u03b8sdp(n, p, k) is below a threshold. Our results thus highlight an interesting trade-off between computational and statistical efficiency in high-dimensional inference.<\/jats:p>","DOI":"10.1214\/08-aos664","type":"journal-article","created":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T09:23:06Z","timestamp":1247822586000},"page":"2877-2921","source":"Crossref","is-referenced-by-count":114,"title":["High-dimensional analysis of semidefinite relaxations for sparse principal components"],"prefix":"10.1214","volume":"37","author":[{"given":"Arash A.","family":"Amini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Wainwright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] Geman, S. (1980). A limit theorem for the norm of random matrices. <i>Ann. Probab.<\/i> <b>8<\/b> 252\u2013261.","DOI":"10.1214\/aop\/1176994775"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] Baik, J. and Silverstein, J. W. (2006). Eigenvalues of large sample covariance matrices of spiked populations models. <i>J. Multivariate Anal.<\/i> <b>97<\/b> 1382\u20131408.","DOI":"10.1016\/j.jmva.2005.08.003"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] Bickel, P. and Levina, E. (2008). Regularized estimation of large covariance matrices. <i>Ann. Statist.<\/i> <b>36<\/b> 199\u2013227.","DOI":"10.1214\/009053607000000758"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] Birg\u00e9, L. (2001). An alternative point of view on Lepski\u2019s method. In <i>State of the Art in Probability and Statistics. IMS Lecture Notes<\/i> <b>37<\/b> 113\u2013133.","DOI":"10.1214\/lnms\/1215090065"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] Candes, E. and Tao, T. (2006). The Dantzig selector: Statistical estimation when <i>p<\/i> is much larger than <i>n<\/i>. <i>Ann. Statist.<\/i> <b>35<\/b> 2313\u20132351.","DOI":"10.1214\/009053606000001523"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] d\u2019Aspremont, A., Bannerjee, O. and El Ghaoui, L. (2007). First order methods for sparse covariance selection. <i>SIAM J. Matrix Anal. Appl.<\/i> <b>30<\/b> 56\u201366.","DOI":"10.1137\/060670985"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] d\u2019Aspremont, A., El Ghaoui, L., Jordan, M. I. and Lanckriet, G. R. G. (2007). A direct formulation for sparse PCA using semidefinite programming. <i>SIAM Rev.<\/i> <b>49<\/b> 434\u2013448.","DOI":"10.1137\/050645506"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] Davidson, K. R. and Szarek, S. J. (2001). Local operator theory, random matrices, and Banach spaces. In <i>Handbook of Banach Spaces<\/i> <b>1<\/b> 317\u2013336. Elsevier, Amsterdam, NL.","DOI":"10.1016\/S1874-5849(01)80010-3"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] Donoho, D. (2006). Compressed sensing. <i>IEEE Trans. Info. Theory<\/i> <b>52<\/b> 1289\u20131306.","DOI":"10.1109\/TIT.2006.871582"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] El Karoui, N. (2008). Operator norm consistent estimation of large-dimensional sparse covariance matrices. <i>Ann. Statist.<\/i> <b>36<\/b> 2717\u20132756.","DOI":"10.1214\/07-AOS559"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] Has\u2019minskii, R. Z. (1978). A lower bound on the risks of nonparametric estimates of densities in the uniform metric. <i>Theory Probab. Appl.<\/i> <b>23<\/b> 794\u2013798.","DOI":"10.1137\/1123095"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Hiriart-Urruty, J. and Lemar\u00e9chal, C. (1993). <i>Convex Analysis and Minimization Algorithms<\/i> <b>1<\/b>. Springer, New York.","DOI":"10.1007\/978-3-662-02796-7_1"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] Johnstone, I. M. (2001). Chi-square oracle inequalities. In <i>State of the Art in Probability and Statistics IMS Lecture Notes<\/i> <b>37<\/b> (M. de Gunst, C. Klaassen and A. van der Vaart, eds.) 399\u2013418. Institute of Mathematical Statistics.","DOI":"10.1214\/lnms\/1215090080"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. <i>Ann. Statist.<\/i> <b>29<\/b> 295\u2013327.","DOI":"10.1214\/aos\/1009210544"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] Jolliffe, I. T., Trendafilov, N. T. and Uddin, M. (2003). A modified principal component technique based on the LASSO. <i>J. Comput. Graph. Statist.<\/i> <b>12<\/b> 531\u2013547.","DOI":"10.1198\/1061860032148"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] Laurent, B. and Massart, P. (1998). Adaptive estimation of a quadratic functional by model selection. <i>Ann. Statist.<\/i> <b>28<\/b> 1303\u20131338.","DOI":"10.1214\/aos\/1015957395"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Meinshausen, N. and B\u00fchlmann, P. (2006). High-dimensional graphs and variable selection with the Lasso. <i>Ann. Statist.<\/i> <b>34<\/b> 1436\u20131462.","DOI":"10.1214\/009053606000000281"},{"key":"31","unstructured":"[31] Paul, D. (2007). Asymptotics of sample eigenstructure for a large-dimensional spiked covariance model. <i>Statist. Sinica<\/i> <b>17<\/b> 1617\u20131642."},{"key":"35","doi-asserted-by":"publisher","unstructured":"[35] Tropp, J. (2006). Just relax: Convex programming methods for identifying sparse signals in noise. <i>IEEE Trans. Inform. Theory<\/i> <b>52<\/b> 1030\u20131051.","DOI":"10.1109\/TIT.2005.864420"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[38] Yang, Y. and Barron, A. (1999). Information-theoretic determination of minimax rates of convergence. <i>Ann. Statist.<\/i> <b>27<\/b> 1564\u20131599.","DOI":"10.1214\/aos\/1017939142"},{"key":"39","doi-asserted-by":"publisher","unstructured":"[39] Yuan, M. and Lin, Y. (2007). Model selection and estimation in the Gaussian graphical model. <i>Biometrika<\/i> <b>94<\/b> 19\u201335.","DOI":"10.1093\/biomet\/asm018"},{"key":"40","doi-asserted-by":"publisher","unstructured":"[40] Zhang, Z., Zha, H. and Simon, H. (2002). Low-rank approximations with sparse factors I: Basic algorithms and error analysis. <i>SIAM J. Matrix Anal. Appl.<\/i> <b>23<\/b> 706\u2013727.","DOI":"10.1137\/S0895479899359631"},{"key":"41","doi-asserted-by":"publisher","unstructured":"[41] Zou, H., Hastie, T. and Tibshirani, R. (2006). Sparse principal component analysis. <i>J. Comput. Graph. Statist.<\/i> <b>15<\/b> 262\u2013286.","DOI":"10.1198\/106186006X113430"},{"key":"7","unstructured":"[7] Cover, T. M. and Thomas, J. A. (1991). <i>Elements of Information Theory<\/i>. Wiley, New York."},{"key":"1","unstructured":"[1] Anderson, T. W. (1984). <i>An Introduction to Multivariate Statistical Analysis<\/i>. Wiley, New York."},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] Buldygin, V. V. and Kozachenko, Y. V. (2000). <i>Metric Characterization of Random Variables and Random Processes<\/i>. Amer. Math. Soc., Providence, RI.","DOI":"10.1090\/mmono\/188"},{"key":"14","unstructured":"[14] Gradshteyn, I. S. and Ryzhik, I. M. (2000). <i>Tables of Integrals<\/i>, <i>Series<\/i>, <i>and Products<\/i>. Academic Press, New York, NY."},{"key":"15","unstructured":"[15] Grimmett, G. R. and Stirzaker, D. R. (1992). <i>Probability and Random Processes<\/i>. Oxford Science Publications, Clarendon Press, Oxford."},{"key":"18","unstructured":"[18] Horn, R. A. and Johnson, C. R. (1986). <i>Matrix Analysis<\/i>. Cambridge Univ. Press, New York, NY."},{"key":"21","unstructured":"[21] Johnstone, I. M. and Lu, A. (2004). Sparse principal components. Technical report, Stanford Univ."},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] Jolliffe, I. T. (2004). <i>Principal Component Analysis<\/i>. Springer, New York.","DOI":"10.1002\/0470013192.bsa501"},{"key":"25","unstructured":"[25] Ledoux, M. (2001). <i>The Concentration of Measure Phenomenon<\/i>. Amer. Math. Soc., Providence, RI."},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] Ledoux, M. and Talagrand, M. (1991). <i>Probability in Banach Spaces<\/i>: <i>Isoperimetry and Processes<\/i>. Springer, New York.","DOI":"10.1007\/978-3-642-20212-4"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Matousek, J. (2002). <i>Lectures on Discrete Geometry<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"29","unstructured":"[29] Moghaddam, B., Weiss, Y. and Avidan, S. (2005). Spectral bounds for sparse PCA: Exact and greedy algorithms. In <i>Neural Information Processing Systems<\/i> (<i>NIPS<\/i>). Vancouver, Canada."},{"key":"30","unstructured":"[30] Paul, D. (2005). Nonparametric estimation of principal components. Ph.D. thesis, Stanford Univ."},{"key":"32","unstructured":"[32] Paul, D. and Johnstone, I. (2008). Augmented sparse principal component analysis for high-dimensional data. Technical report, UC Davis."},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] Rockafellar, G. (1970). <i>Convex Analysis<\/i>. Princeton Univ. Press, Princeton.","DOI":"10.1515\/9781400873173"},{"key":"34","unstructured":"[34] Stewart, G. W. and Sun, J. G. (1990). <i>Matrix Perturbation Theory<\/i>. Academic Press, New York."},{"key":"36","unstructured":"[36] Wainwright, M. J. (2006). Sharp thresholds for high-dimensional and noisy recovery of sparsity using the Lasso. In <i>IEEE Trans. Inform. Theory<\/i>. Technical Report 709, Dept. Statistics, UC Berkeley."},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] Wainwright, M. J. (2007). Information-theoretic bounds for sparsity recovery in the high-dimensional and noisy setting. In <i>Int. Symposium on Information Theory<\/i>. Technical Report 725, Dept. Statistics, UC Berkeley.","DOI":"10.1109\/ISIT.2007.4557348"}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1247836672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T22:35:05Z","timestamp":1791585305000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-37\/issue-5B\/High-dimensional-analysis-of-semidefinite-relaxations-for-sparse-principal-components\/10.1214\/08-AOS664.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,1]]},"references-count":41,"journal-issue":{"issue":"5B","published-online":{"date-parts":[[2009,10,1]]}},"URL":"https:\/\/doi.org\/10.1214\/08-aos664","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,1]]}}}