# Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions

arXiv: https://arxiv.org/abs/1708.09479 · HTML: https://mlsanity.com/paper/1708.09479/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2017.

## Built on by (most cited first, 12 of 12)

- [Explaining the Uncertain: Stochastic Shapley Values for Gaussian Process Models](https://mlsanity.com/paper/2305.15167/) (2023)
- [Learning Graphical Factor Models with Riemannian Optimization](https://mlsanity.com/paper/2210.11950/) (2022)
- [Score Matching With Missing Data](https://mlsanity.com/paper/2506.00557/) (2025)
- [Learning Large-Scale MTP2 Gaussian Graphical Models via Bridge-Block Decomposition](https://mlsanity.com/paper/2309.13405/) (2023)
- [Fairness-Aware Estimation of Graphical Models](https://mlsanity.com/paper/2408.17396/) (2024)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees](https://mlsanity.com/paper/2102.03585/) (2021)
- [Thresholded Graphical Lasso Adjusts for Latent Variables: Application to Functional Neural Connectivity](https://mlsanity.com/paper/2104.06389/) (2021)
- [Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles](https://mlsanity.com/paper/2110.12067/) (2021)
- [Efficient Inference of Spatially-varying Gaussian Markov Random Fields with Applications in Gene Regulatory Networks](https://mlsanity.com/paper/2206.10174/) (2022)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [A Computationally Efficient Sparsified Online Newton Method](https://mlsanity.com/paper/2311.10085/) (2023)

## Abstract (arXiv)

Graphical Lasso (GL) is a popular method for learning the structure of an undirected graphical model, which is based on an l1 regularization technique. The objective of this paper is to compare the computationally-heavy GL technique with a numerically-cheap heuristic method that is based on simply thresholding the sample covariance matrix. To this end, two notions of sign-consistent and inverse-consistent matrices are developed, and then it is shown that the thresholding and GL methods are equivalent if: (i) the thresholded sample covariance matrix is both sign-consistent and inverse-consistent, and (ii) the gap between the largest thresholded and the smallest un-thresholded entries of the sample covariance matrix is not too small. By building upon this result, it is proved that the GL method---as a conic optimization problem---has an explicit closed-form solution if the thresholded sample covariance matrix has an acyclic structure. This result is then generalized to arbitrary sparse support graphs, where a formula is found to obtain an approximate solution of GL. Furthermore, it is shown that the approximation error of the derived explicit formula decreases exponentially fast with respect to the length of the minimum-length cycle of the sparsity graph. The developed results are demonstrated on synthetic data, functional MRI data, traffic flows for transportation networks, and massive randomly generated data sets. We show that the proposed method can obtain an accurate approximation of the GL for instances with the sizes as large as 80,000× 80,000 (more than 3.2 billion variables) in less than 30 minutes on a standard laptop computer running MATLAB, while other state-of-the-art methods do not converge within 4 hours.