# Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2018.

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

- [Methods for Recovering Conditional Independence Graphs: A Survey](https://mlsanity.com/paper/2211.06829/) (2022)
- [Learning Graph Structure from Convolutional Mixtures](https://mlsanity.com/paper/2205.09575/) (2022)
- [Low-Rank Covariance Completion for Graph Quilting with Applications to Functional Connectivity](https://mlsanity.com/paper/2209.08273/) (2022)
- [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)

The sparse inverse covariance estimation problem is commonly solved using an ℓ1-regularized Gaussian maximum likelihood estimator known as "graphical lasso", but its computational cost becomes prohibitive for large data sets. A recent line of results showed--under mild assumptions--that the graphical lasso estimator can be retrieved by soft-thresholding the sample covariance matrix and solving a maximum determinant matrix completion (MDMC) problem. This paper proves an extension of this result, and describes a Newton-CG algorithm to efficiently solve the MDMC problem. Assuming that the thresholded sample covariance matrix is sparse with a sparse Cholesky factorization, we prove that the algorithm converges to an ε-accurate solution in O(nlog(1/ε)) time and O(n) memory. The algorithm is highly efficient in practice: we solve the associated MDMC problems with as many as 200,000 variables to 7-9 digits of accuracy in less than an hour on a standard laptop computer running MATLAB.