High dimensional covariance estimation by minimizing l1-penalized log-determinant divergence

Pradeep Ravikumar, Martin Wainwright, Bin Yu, Garvesh Raskutti

Abstract:   Given i.i.d. observations of a random vector X ∈ R^p, we study the problem of estimating both its covariance matrix Σ∗, and its inverse covariance or concentration matrix Θ∗ = (Σ∗)^−1. When X is multivariate Gaussian, the non-zero structure of Θ∗ is specified by the graph of an associated Gaussian Markov random field; and a popular estimator for such sparse Θ∗ is the l1-regularized Gaussian MLE. This estimator is sensible even for for non-Gaussian X, since it corresponds to minimizing an l1-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 l∞-operator norm of the true covariance matrix Σ∗; and (b) the l_∞ operator norm of the sub-matrix Γ∗SS, 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{|hat Σ_ij −Σ∗_ij|>δ},wherehatΣ_n is the sample covariance based on n samples. Our first result establishes consistency of our estimate hatΘ 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(√s). In our second result, we show that with probability converging to one, the estimate hatΘ 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.

Download: pdf


  • High dimensional covariance estimation by minimizing l1-penalized log-determinant divergence (pdf, software)
    P. Ravikumar, M. Wainwright, B. Yu, G. Raskutti.
    Electronic Journal of Statistics (EJS) 5, pp. 935-980, 2011.