High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods

Abstract

In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two novel greedy approaches to solving this problem. The first estimates the non-zero covariates of the overall inverse covariance matrix using a series of global forward and backward greedy steps. The second estimates the neighborhood of each node in the graph separately, again using greedy forward and backward steps, and combines the intermediate neighborhoods to form an overall estimate. The principal contribution of this paper is a rigorous analysis of the sparsistency, or consistency in recovering the sparsity pattern of the inverse covariance matrix. Surprisingly, we show that both the local and global greedy methods learn the full structure of the model with high probability given just $O(d\log (p))$ samples, which is a \emph{significant} improvement over state of the art ${\ell }_1$-regularized Gaussian MLE (Graphical Lasso) that requires $O(d^2\log (p))$ samples. Moreover, the restricted eigenvalue and smoothness conditions imposed by our greedy methods are much weaker than the strong irrepresentable conditions required by the ${\ell }_1$-regularization based methods. We corroborate our results with extensive simulations and examples, comparing our local and global greedy methods to the ${\ell }_1$-regularized Gaussian MLE as well as the Neighborhood Greedy method to that of nodewise ${\ell }_1$-regularized linear regression (Neighborhood Lasso).

Accepted to AI STAT 2012 for Oral Presentation

References in corpus (2)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• On Learning Discrete Graphical Models Using Greedy Methods

Cited by in corpus (13)

• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint
• Graph Estimation From Multi-attribute Data
• Marginal Likelihoods for Distributed Parameter Estimation of Gaussian Graphical Models
• Local and Global Inference for High Dimensional Nonparanormal Graphical Models
• Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• A Junction Tree Framework for Undirected Graphical Model Selection
• Efficient Neighborhood Selection for Gaussian Graphical Models
• Partial Gaussian Graphical Model Estimation
• A Stepwise Approach for High-Dimensional Gaussian Graphical Models
• Estimation of Shortest Path Covariance Matrices
• Meta Learning for Support Recovery in High-dimensional Precision Matrix Estimation