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

Abstract

We consider the sparse inverse covariance regularization problem or <i>graphical lasso</i> with regularization parameter λ. Suppose the sample <i>covariance graph</i> formed by thresholding the entries of the sample covariance matrix at λ is decomposed into connected components. We show that the <i>vertex-partition</i> induced by the connected components of the thresholded sample covariance graph (at λ) is <i>exactly</i> equal to that induced by the connected components of the estimated concentration graph, obtained by solving the graphical lasso problem for the <i>same</i> λ. 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.