High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence

By Pradeep Ravikumar, Martin J. Wainwright, Garvesh Raskutti, Bin Yu. 2008

914 citations recorded by the source corpus.

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.

Subfields: Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/398ff09f1ef9fdc1d70f59eeb744f06c06998528

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

Regularized rank-based estimation of high-dimensional nonparanormal graphical models (2012, methodology): “However, Liu, Laﬀerty and Wasserman (2009) did not get a satisfactory rate of convergence for the “plug-in” approach, because the rate of convergence can be established for the Gaussian graphical model even when p grows with n almost exponentially fast [Ravikumar et al. (2011)].”
Global Testing and Large-Scale Multiple Testing for High-Dimensional Covariance Structures (2017, neutral): “Ravikumar, P., M. J. Wainwright, G. Raskutti, and B. Yu (2011).”
Sparse envelope model: efficient estimation and response variable selection in multivariate linear regression (2016, neutral): “We relaxed the normality assumption in Rothman et al. (2008) to the sub-Gaussian assumption based on the work in Ravikumar et al. (2011).”
Online linear optimization with the log-determinant regularizer (2017, methodology): “There are many applications of the LogDet divergence such as metric learning [16] and Gaussian graphical models [17].”
Estimating structured high-dimensional covariance and precision matrices: Optimal rates and adaptive estimation (2016, background): “…estimation in Huang et al. (2006), Yuan and Lin (2007), d’Aspremont et al. (2008), Banerjee et al. (2008), Rothman et al. (2008), Lam and Fan (2009), Ravikumar et al. (2011), and Chandrasekaran et al. (2012), regularizing principal components in Johnstone and Lu (2009), Zou et al. (2006), Cai, Ma,…”
Sparse inverse covariance matrix estimation using quadratic approximation (2011, methodology): “For further details on the background and utility of ℓ 1 regularization in the context of GMRFs, we refer the reader to Yuan and Lin [2007], Banerjee et al. [2008], Friedman et al. [2008], Ravikumar et al. [2011], Duchi et al. [2008].”
High-dimensional consistency in score-based and hybrid structure learning (2015, background): “…that are consistent in sparse high-dimensional settings [e.g., Meinshausen and Bühlmann (2006), Banerjee, El Ghaoui and d’Aspremont (2008), Friedman, Hastie and Tibshirani (2008), Ravikumar et al. (2008, 2011), Cai, Liu and Luo (2011), Kalisch and Bühlmann (2007), Ha, Sun and Xie (2016)].”
Handbook of Big Data (2016, neutral): “, 2015) and theoretical (Yuan and Lin, 2007b; Rothman et al., 2008; Ravikumar et al., 2011) perspective.”
Estimating time-varying networks (2008, methodology): “Note that these conditions are the same as for the i.i.d. case analyzed in Ravikumar et al. (2008), when the graph is stable over time, and they are related to conditions proposed in analysis of the linear regression (e.g. Meinshausen and Bühlmann (2006)).”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, methodology): “[45].”
High Dimensional Inverse Covariance Matrix Estimation via Linear Programming (2010, methodology): “In particular, the results from Ravikumar et al. (2008) and Rothman et al. (2008) suggest that, although better thanthe sample covariance matrix, these methods may not perform well whenp is larger than the sample sizen.”
Bayesian model choice and information criteria in sparse generalized linear models (2011, background): “By inequality (86) of Ravikumar et al. (2011), if W1, . . . ,Wn are i.i.d. copies of a random variable W with E[|W |K ] ≤M , then E [∣∣∣∑ i Wi − E[W ] ∣∣∣K] ≤ nK/2 (K/2)K+1 E [|W − E[W ]|K] ≤ nK/2 (K/2)K+1 · 2K ( E[|W |K ] + |E[W ]|K ) ≤ nK/2KK+1M , and therefore, P { 1 n ∑ i Wi > 2M 1/K } ≤ P…”
The Benefits of Learning with Strongly Convex Approximate Inference (2015, background): “Many of these works (e.g., Bickel et al., 2009; Kakade et al., 2010; Ravikumar et al., 2011; Negahban et al., 2012; Bradley & Guestrin, 2012; Meng et al., 2014) rely on a restricted eigenvalue (RE) assumption.”
Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization (2012, background): “The next lemma results from Lemma 1 in [2] and the union bound.”