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

Given i.i.d. observations of a random vector X ∈ Rᵖ, we study the problem of estimating both its covariance matrix Σ^*, and its inverse covariance or concentration matrix {Θ^* = (Σ^*)⁻¹.} We estimate Θ^* by minimizing an ₁-penalized log-determinant Bregman divergence; in the multivariate Gaussian case, this approach corresponds to ₁-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 estimator 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 covariance matrix Σ^*; and (b) the _∞ operator norm of the sub-matrix Γ^*S S, where S indexes the graph edges, and Γ^* = (Θ^*)⁻¹ ⊗ (Θ^*)⁻¹; and (c) a mutual incoherence or irrepresentability measure on the matrix Γ^* and (d) the rate of decay $1/f(n,δ)$ on the probabilities \|Σⁿᵢⱼ- Σ^*ᵢⱼ| > δ\, where Σⁿ is the sample covariance based on n samples. Our first result establishes consistency of our estimate Θ 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 Θ correctly specifies the zero pattern of the concentration matrix Θ^*.