High-dimensional covariance estimation by minimizing ${\ell }_1$-penalized log-determinant divergence

Abstract

Given i.i.d. observations of a random vector $X\in {\mathbb{R}}^p$, we study the problem of estimating both its covariance matrix ${\Sigma }^{\ast }$, and its inverse covariance or concentration matrix {${\Theta }^{\ast }=({\Sigma }^{\ast }{)}^{-1}$.} We estimate ${\Theta }^{\ast }$ by minimizing an ${\ell }_1$-penalized log-determinant Bregman divergence; in the multivariate Gaussian case, this approach corresponds to ${\ell }_1$-penalized maximum likelihood, and the structure of ${\Theta }^{\ast }$ 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 ${\Sigma }^{\ast }$; and (b) the ${\ell }_{\infty }$ operator norm of the sub-matrix ${\Gamma }_{SS}^{\ast }$, where $S$ indexes the graph edges, and ${\Gamma }^{\ast }=({\Theta }^{\ast }{)}^{-1}\otimes ({\Theta }^{\ast }{)}^{-1}$; and (c) a mutual incoherence or irrepresentability measure on the matrix ${\Gamma }^{\ast }$ and (d) the rate of decay $1/f(n,\delta )$ on the probabilities $\{|{\hat{\Sigma }}_{ij}^n-{\Sigma }_{ij}^{\ast }|>\delta \}$, where ${\hat{\Sigma }}^n$ is the sample covariance based on $n$ samples. Our first result establishes consistency of our estimate $\hat{\Theta }$ 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(\sqrt{s})$. In our second result, we show that with probability converging to one, the estimate $\hat{\Theta }$ correctly specifies the zero pattern of the concentration matrix ${\Theta }^{\ast }$.

35 pages, 9 figures

References in corpus (1)

• Sparse Principal Components Analysis

Cited by in corpus (14)

• Latent variable graphical model selection via convex optimization
• Strong oracle optimality of folded concave penalized estimation
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Covariance Estimation in High Dimensions via Kronecker Product Expansions
• Missing values: sparse inverse covariance estimation and an extension to sparse regression
• High-dimensional covariance estimation based on Gaussian graphical models
• Convergence Properties of Kronecker Graphical Lasso Algorithms
• Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
• Learning the Dependence Graph of Time Series with Latent Factors
• Estimating heterogeneous graphical models for discrete data with an application to roll call voting
• Interpreting Latent Variables in Factor Models via Convex Optimization
• Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection
• Bayesian Regularization for Graphical Models with Unequal Shrinkage
• A Direct Estimation Approach to Sparse Linear Discriminant Analysis