2008/11/21 by Pradeep Ravikumar, Martin J. Wainwright, Ravikumar, Pradeep +5 · 10 citations
Mathematics · Physics and Astronomy · #Advanced Statistical Methods and Models #Statistical Methods and Inference #Statistical Mechanics and Entropy
paper · pdf · doi:10.48550/arxiv.0811.3628
Given i.i.d. observations of a random vector X ∈ ℝp, we study the problem of estimating both its covariance matrix Σ^*, and its inverse covariance or concentration matrix Θ^* = (Σ^*)-1. We estimate Θ^* by minimizing an ℓ1-penalized log-determinant Bregman divergence; in the multivariate Gaussian case, this approach corresponds to ℓ1-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 Γ^* = (Θ^*)-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 \|Σnij- Σ^*ij| > δ\, where Σn 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 Θ^*.