Exact covariance thresholding into connected components for large-scale Graphical Lasso

Abstract

We consider the sparse inverse covariance regularization problem or graphical lasso with regularization parameter $\rho$. Suppose the co- variance graph formed by thresholding the entries of the sample covariance matrix at $\rho$ is decomposed into connected components. We show that the vertex-partition induced by the thresholded covariance graph is exactly equal to that induced by the estimated concentration graph. This simple rule, when used as a wrapper around existing algorithms, leads to enormous performance gains. For large values of $\rho$, our proposal splits a large graphical lasso problem into smaller tractable problems, making it possible to solve an otherwise infeasible large scale graphical lasso problem.

Report Version 2 (adding more experiments and correcting minor typos)

References in corpus (3)

• High-dimensional covariance estimation based on Gaussian graphical models
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• Sparse Inverse Covariance Estimation via an Adaptive Gradient-Based Method

Cited by in corpus (9)

• The huge Package for High-dimensional Undirected Graph Estimation in R
• A convex pseudo-likelihood framework for high dimensional partial correlation estimation with convergence guarantees
• Feature Graph Learning for 3D Point Cloud Denoising
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• Conic Optimization Theory: Convexification Techniques and Numerical Algorithms
• Joint Association Graph Screening and Decomposition for Large-scale Linear Dynamical Systems
• Sparse Graphical Linear Dynamical Systems
• Factorial graphical lasso for dynamic networks