{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,19]],"date-time":"2026-10-19T10:58:46Z","timestamp":1792407526720,"version":"4.4.0"},"reference-count":33,"publisher":"Institute of Mathematical Statistics","issue":"none","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Statist."],"published-print":{"date-parts":[[2011,1,1]]},"abstract":"<jats:p>Given i.i.d. observations of a random vector X\u2208\u211dp, we study the problem of estimating both its covariance matrix \u03a3*, and its inverse covariance or concentration matrix \u0398*=(\u03a3*)\u22121. When X is multivariate Gaussian, the non-zero structure of \u0398* is specified by the graph of an associated Gaussian Markov random field; and a popular estimator for such sparse \u0398* is the \u21131-regularized Gaussian MLE. This estimator is sensible even for for non-Gaussian X, since it corresponds to minimizing an \u21131-penalized log-determinant Bregman divergence. We analyze its performance under high-dimensional scaling, in which the number of nodes in the graph p, the number of edges s, and the maximum node degree d, are allowed to grow as a function of the sample size n. In addition to the parameters (p,s,d), our analysis identifies other key quantities that control rates: (a) the \u2113\u221e-operator norm of the true covariance matrix \u03a3*; and (b) the \u2113\u221e operator norm of the sub-matrix \u0393*SS, where S indexes the graph edges, and \u0393*=(\u0398*)\u22121\u2297(\u0398*)\u22121; and (c) a mutual incoherence or irrepresentability measure on the matrix \u0393* and (d) the rate of decay 1\/f(n,\u03b4) on the probabilities {|\u03a3\u0302nij\u2212\u03a3*ij|&gt;\u03b4}, where \u03a3\u0302n is the sample covariance based on n samples. Our first result establishes consistency of our estimate \u0398\u0302 in the elementwise maximum-norm. This in turn allows us to derive convergence rates in Frobenius and spectral norms, with improvements upon existing results for graphs with maximum node degrees $d=o(\\sqrt{s})$. In our second result, we show that with probability converging to one, the estimate \u0398\u0302 correctly specifies the zero pattern of the concentration matrix \u0398*. We illustrate our theoretical results via simulations for various graphs and problem parameters, showing good correspondences between the theoretical predictions and behavior in simulations.<\/jats:p>","DOI":"10.1214\/11-ejs631","type":"journal-article","created":{"date-parts":[[2011,9,15]],"date-time":"2011-09-15T13:32:27Z","timestamp":1316093547000},"page":"935-980","source":"Crossref","is-referenced-by-count":457,"title":["High-dimensional covariance estimation by minimizing \u21131-penalized log-determinant divergence"],"prefix":"10.1214","volume":"5","author":[{"given":"Pradeep","family":"Ravikumar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Wainwright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Garvesh","family":"Raskutti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] P. J. Bickel and E. Levina. Covariance regularization by thresholding., <i>Ann. Statist.<\/i>, 36(6) :2577\u20132604, 2008.","DOI":"10.1214\/08-AOS600"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] P. J. Bickel and E. Levina. Regularized estimation of large covariance matrices., <i>Ann. Statist.<\/i>, 36(1):199\u2013227, 2008.","DOI":"10.1214\/009053607000000758"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] S. Boyd and L. Vandenberghe., <i>Convex optimization<\/i>. Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] L. M. Bregman. The relaxation method for finding the common point of convex sets and its application to the solution of problems in convex programming., <i>USSR Computational Mathematics and Mathematical Physics<\/i>, 7:191\u2013204, 1967.","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] L. D. Brown., <i>Fundamentals of statistical exponential families<\/i>. Institute of Mathematical Statistics, Hayward, CA, 1986.","DOI":"10.1214\/lnms\/1215466757"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] V. V. Buldygin and Y. V. Kozachenko., <i>Metric characterization of random variables and random processes<\/i>. American Mathematical Society, Providence, RI, 2000.","DOI":"10.1090\/mmono\/188"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] T. T. Cai, C.-H. Zhang, and H. H. Zhou. Optimal rates of convergence for covariance matrix estimation., <i>Annals of Statistics<\/i>, 2010. To appear.","DOI":"10.1214\/09-AOS752"},{"key":"8","unstructured":"[8] Y. Censor and S. A. Zenios., <i>Parallel Optimization: Theory, Algorithms, and Applications<\/i>. Numerical Mathematics and Scientific Computation. Oxford University Press, 1988."},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] A. d\u2019Aspr\u00e9mont, O. Banerjee, and L. El Ghaoui. First-order methods for sparse covariance selection., <i>SIAM J. Matrix Anal. Appl.<\/i>, 30(1):56\u201366, 2008.","DOI":"10.1137\/060670985"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] N. El Karoui. Operator norm consistent estimation of large dimensional sparse covariance matrices., <i>Ann. Statist.<\/i>, To appear, 2008.","DOI":"10.1214\/07-AOS559"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical Lasso., <i>Biostat.<\/i>, 9(3):432\u2013441, 2007.","DOI":"10.1093\/biostatistics\/kxm045"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] R. Furrer and T. Bengtsson. Estimation of high-dimensional prior and posterior covariance matrices in kalman filter variants., <i>J. Multivar. Anal.<\/i>, 98(2):227\u2013255, 2007.","DOI":"10.1016\/j.jmva.2006.08.003"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] C. Giraud. Estimation of gaussian graph by model selection., <i>Electronic Journal of Statistics<\/i>, 2:542\u2013563, 2008.","DOI":"10.1214\/08-EJS228"},{"key":"14","unstructured":"[14] R. A. Horn and C. R. Johnson., <i>Matrix Analysis<\/i>. Cambridge University Press, Cambridge, 1985."},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] J. Z. Huang, N. Liu, M. Pourahmadi, and L. Liu. Covariance matrix selection and estimation via penalised normal likelihood., <i>Biometrika<\/i>, 93(1):85\u201398, 2006.","DOI":"10.1093\/biomet\/93.1.85"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] I. M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis., <i>Ann. Statist.<\/i>, 29(2):295\u2013327, 2001.","DOI":"10.1214\/aos\/1009210544"},{"key":"17","unstructured":"[17] I. M. Johnstone and A. Y. Lu. Sparse principal components analysis., <i>Unpublished Manuscript<\/i>, 2004."},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] C. Lam and J. Fan. Sparsistency and rates of convergence in large covariance matrix estimation., <i>Annals of Statistics<\/i>, 37 :4254\u20134278, 2009.","DOI":"10.1214\/09-AOS720"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] O. Ledoit and M. Wolf. A well-conditioned estimator for large-dimensional covariance matrices., <i>J. Multivar. Anal.<\/i>, 88:365\u2013411, 2003.","DOI":"10.1016\/S0047-259X(03)00096-4"},{"key":"20","unstructured":"[20] M. Ledoux., <i>The Concentration of Measure Phenomenon<\/i>. Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001."},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] N. Meinshausen. A note on the Lasso for graphical Gaussian model selection., <i>Statistics and Probability Letters<\/i>, 78(7): 880\u2013884, 2008.","DOI":"10.1016\/j.spl.2007.09.014"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] N. Meinshausen and P. B\u00fchlmann. High-dimensional graphs and variable selection with the Lasso., <i>Ann. Statist.<\/i>, 34(3) :1436\u20131462, 2006.","DOI":"10.1214\/009053606000000281"},{"key":"23","unstructured":"[23] J. M. Ortega and W. G. Rheinboldt., <i>Iterative Solution of Nonlinear Equations in Several Variables<\/i>. Academic Press, NY, 1970."},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] V. V. Petrov., <i>Limit Theorems Of Probability Theory: Sequences Of Independent Random Variables<\/i>. Oxford University Press, Oxford, UK, 1995.","DOI":"10.1093\/oso\/9780198534990.003.0002"},{"key":"25","unstructured":"[25] P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation: Convergence rates of, <i>\u2113<\/i><sub>1<\/sub>-regularized log-determinant divergence. Technical report, Department of Statistics, UC Berkeley, September 2008."},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] H. P. Rosenthal. On the subspaces of, <i>l<\/i><sup><i>p<\/i><\/sup> (<i>p<\/i><i>&gt;<\/i>2) spanned by sequences of independent random variables. <i>Israel J. Math<\/i>, 8 :1546\u20131570, 1970.","DOI":"10.1007\/BF02771562"},{"key":"27","doi-asserted-by":"publisher","unstructured":"[27] A. J. Rothman, P. J. Bickel, E. Levina, and J. Zhu. Sparse permutation invariant covariance estimation., <i>Electron. J. Statist.<\/i>, 2:494\u2013515, 2008.","DOI":"10.1214\/08-EJS176"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] J. A. Tropp. Just relax: Convex programming methods for identifying sparse signals., <i>IEEE Trans. Info. Theory<\/i>, 51(3): 1030\u20131051, 2006.","DOI":"10.1109\/TIT.2005.864420"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[29] M. J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using, <i>\u2113<\/i><sub>1<\/sub>-constrained quadratic programming (Lasso). <i>IEEE Trans. Information Theory<\/i>, 55 :2183\u20132202, May 2009.","DOI":"10.1109\/TIT.2009.2016018"},{"key":"30","doi-asserted-by":"publisher","unstructured":"[30] W. B. Wu and M. Pourahmadi. Nonparametric estimation of large covariance matrices of longitudinal data., <i>Biometrika<\/i>, 90(4):831\u2013844, 2003.","DOI":"10.1093\/biomet\/90.4.831"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[31] M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphical model., <i>Biometrika<\/i>, 94(1):19\u201335, 2007.","DOI":"10.1093\/biomet\/asm018"},{"key":"32","unstructured":"[32] P. Zhao and B. Yu. On model selection consistency of Lasso., <i>Journal of Machine Learning Research<\/i>, 7 :2541\u20132567, 2006."},{"key":"33","unstructured":"[33] S. Zhou, J. Lafferty, and L. Wasserman. Time-varying undirected graphs. In, <i>21st Annual Conference on Learning Theory (COLT)<\/i>, Helsinki, Finland, July 2008."}],"container-title":["Electronic Journal of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.ejs\/1316092865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T21:32:18Z","timestamp":1791581538000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/electronic-journal-of-statistics\/volume-5\/issue-none\/High-dimensional-covariance-estimation-by-minimizing-%E2%84%931-penalized-log-determinant\/10.1214\/11-EJS631.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":33,"journal-issue":{"issue":"none","published-online":{"date-parts":[[2011,1,1]]}},"URL":"https:\/\/doi.org\/10.1214\/11-ejs631","relation":{},"ISSN":["1935-7524","1935-7524"],"issn-type":[{"value":"1935-7524","type":"print"},{"value":"1935-7524","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}