Large-scale sparse inverse covariance estimation via thresholding and max-det matrix completion

Richard Y. Zhang, Salar Fattahi, Somayeh Sojoudi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The sparse inverse covariance estimation problem is commonly solved using an l1-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 e-accurate solution in O(n log(l/ϵ)) 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.

Original languageEnglish (US)
Title of host publication35th International Conference on Machine Learning, ICML 2018
EditorsAndreas Krause, Jennifer Dy
PublisherInternational Machine Learning Society (IMLS)
Pages9178-9200
Number of pages23
ISBN (Electronic)9781510867963
StatePublished - Jan 1 2018
Externally publishedYes
Event35th International Conference on Machine Learning, ICML 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

Name35th International Conference on Machine Learning, ICML 2018
Volume13

Other

Other35th International Conference on Machine Learning, ICML 2018
Country/TerritorySweden
CityStockholm
Period7/10/187/15/18

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Fingerprint

Dive into the research topics of 'Large-scale sparse inverse covariance estimation via thresholding and max-det matrix completion'. Together they form a unique fingerprint.

Cite this