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

Rahul Mazumder, Trevor Hastie.

Year: 2012, Volume: 13, Issue: 27, Pages: 781−794

#### 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.