High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergence

Given i.i.d. observations of a random vector X 2 R p , we study the problem of estimating both its covariance matrix � ∗ , and its inverse covariance or concentration matrix � ∗ = (� ∗ ) −1 . We estimate � ∗ by minimizing an l1-penalized log-determinant Bregman divergence; in the multivariate Gaussian case, this approach corresponds to l1-penalized maximum likelihood, and the structure of � ∗ is specified by the graph of an associated Gaussian Markov random field. We analyze the performance of this estim ator 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 l∞-operator norm of the true covariance matrix � ∗ ; and (b) the l∞ operator norm of the submatrix ∗, where S indexes the graph edges, and ∗ = (� ∗ ) −1 (� ∗ ) −1 ; and (c) a mutual incoherence or irrepresentability measure on the matrix ∗ and (d) the rate of decay 1/f(n, δ) on the probabilities {|b n � ∗| > δ}, where b � n is the sample covariance based on n samples. Our first result establishes consistency of our estimate b � 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( p s). In our second result, we show that with probability converging to one, the estimate b � correctly specifies the zero pattern of the concentration matrix � ∗ . We illustrate our theoretical results via simulations for various graphs and problem parameters, showing good correspondences between the theoretical predictions and behavior in simulations. 1. Introduction. The area of high-dimensional statistics deals with estimation in the “large p, small n” setting, where p and n correspond, respectively, to the dimensionality of the dat a and the sample size. Such high-dimensional problems arise in a variety of applications, among them remote sensing, computational biology and natural language processing, where the model dimension may be comparable or substantially larger than the sample size. It is well-known that such high-dimensional scaling can lead to dramatic breakdowns in many classical procedures. In the absence of additional model assumptions, it is frequently impossible to obtain consistent procedures when p ≫ n. Accordingly, an active line of statistical research is based on imposing various restrictions on the model—-for instance, sparsity, manifold structure, or graphical model structure—-and then studying the scaling behavior of different estimators as a function of sample size n, ambient dimension p and additional parameters related to these structural assu mptions.