New Insights and Faster Computations for the Graphical Lasso

Daniela Witten, Jerome H. Friedman, Noah Simon

Journal of Computational and Graphical Statistics · 2011 · 345 citations · 12 references

Concepts

TL;DR

Graphical lasso estimates the inverse covariance matrix of a high‑dimensional Gaussian model by maximizing an ℓ1‑penalized log‑likelihood. The authors propose a simple necessary and sufficient condition to identify the connected components of the graphical lasso solution. The condition determines whether the estimated inverse covariance matrix is block‑diagonal and, if so, delineates the blocks. Using the condition allows one to run standard graphical lasso on each block separately, yielding drastic speed gains, and shows that the set of connected nodes at a given tuning parameter is a superset of that at any larger parameter. Supplementary material is available online.

Abstract

We consider the graphical lasso formulation for estimating a Gaussian graphical model in the high-dimensional setting. This approach entails estimating the inverse covariance matrix under a multivariate normal model by maximizing the ℓ1-penalized log-likelihood. We present a very simple necessary and sufficient condition that can be used to identify the connected components in the graphical lasso solution. The condition can be employed to determine whether the estimated inverse covariance matrix will be block diagonal, and if so, then to identify the blocks. This in turn can lead to drastic speed improvements, since one can simply apply a standard graphical lasso algorithm to each block separately. Moreover, the necessary and sufficient condition provides insight into the graphical lasso solution: the set of connected nodes at any given tuning parameter value is a superset of the set of connected nodes at any larger tuning parameter value. This article has supplementary material online.

References

12