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

** Rahul Mazumder, Trevor Hastie**; 13(27):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.

© JMLR 2012. (edit, beta) |