Exact Covariance Thresholding into Connected Components for Large-Scale Graphical Lasso.
We consider the sparse inverse covariance regularization problem orgraphical lassowith regularization parameter λ. Suppose the samplecovariance graphformed by thresholding the entries of the sample covariance matrix at λ is decomposed into connected components. We show that thevertex-partitioninduced by the connected components of the thresholded sample covariance graph (at λ) isexactlyequal to that induced by the connected components of the estimated concentration graph, obtained by solving the graphical lasso problem for thesameλ. 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.
Department of Statistics Stanford University Stanford, CA 94305.
Rahul
R
Mazumder
Department of Statistics Stanford University Stanford, CA 94305.
Trevor
T
Hastie
Gaussian graphical models; concentration graph; graph connected components; graphical lasso; large scale covariance estimation; sparse inverse covariance selection; sparsity