## Exact Covariance Thresholding into Connected Components for Large-Scale Graphical Lasso

** Rahul Mazumder, Trevor Hastie**; 13(Mar):781−794, 2012.

### Abstract

We consider the sparse inverse covariance regularization problem or*graphical lasso*with regularization parameter

*λ*. Suppose the sample

*covariance graph*formed by thresholding the entries of the sample covariance matrix at

*λ*is decomposed into connected components. We show that the

*vertex-partition*induced by the connected components of the thresholded sample covariance graph (at

*λ*) is

*exactly*equal to that induced by the connected components of the estimated concentration graph, obtained by solving the graphical lasso problem for the

*same*

*λ*. This characterizes a very interesting property of a path of graphical lasso solutions. Furthermore, this simple rule, when used as a wrapper around existing algorithms for the graphical lasso, leads to enormous performance gains. For a range of values of

*λ*, our proposal splits a large graphical lasso problem into smaller tractable problems, making it possible to solve an otherwise infeasible large-scale problem. We illustrate the graceful scalability of our proposal via synthetic and real-life microarray examples.

[abs][pdf]