QUIC: quadratic approximation for sparse inverse covariance estimation. The ℓ 1 -regularized Gaussian maximum likelihood estimator (MLE) has been shown to have strong statistical guarantees in recovering a sparse inverse covariance matrix, or alternatively the underlying graph structure of a Gaussian Markov Random Field, from very limited samples. We propose a novel algorithm for solving the resulting optimization problem which is a regularized log-determinant program. In contrast to recent state-of-the-art methods that largely use first order gradient information, our algorithm is based on Newton’s method and employs a quadratic approximation, but with some modifications that leverage the structure of the sparse Gaussian MLE problem. We show that our method is superlinearly convergent, and present experimental results using synthetic and real-world application data that demonstrate the considerable improvements in performance of our method when compared to previous methods.

References in zbMATH (referenced in 20 articles )

Showing results 1 to 20 of 20.
Sorted by year (citations)

  1. Ghose, Amur; Jaini, Priyank; Poupart, Pascal: Learning directed acyclic graph SPNs in sub-quadratic time (2020)
  2. Nakagaki, Takashi; Fukuda, Mituhiro; Kim, Sunyoung; Yamashita, Makoto: A dual spectral projected gradient method for log-determinant semidefinite problems (2020)
  3. Wang, Cheng; Jiang, Binyan: An efficient ADMM algorithm for high dimensional precision matrix estimation via penalized quadratic loss (2020)
  4. Wu, Yichong; Li, Tiejun; Liu, Xiaoping; Chen, Luonan: Differential network inference via the fused D-trace loss with cross variables (2020)
  5. Zhang, Yangjing; Zhang, Ning; Sun, Defeng; Toh, Kim-Chuan: A proximal point dual Newton algorithm for solving group graphical Lasso problems (2020)
  6. Ağraz, Melih; Purutçuoğlu, Vilda: Extended Lasso-type MARS (LMARS) model in the description of biological network (2019)
  7. Bollhöfer, Matthias; Eftekhari, Aryan; Scheidegger, Simon; Schenk, Olaf: Large-scale sparse inverse covariance matrix estimation (2019)
  8. Das, Anup; Sexton, Daniel; Lainscsek, Claudia; Cash, Sydney S.; Sejnowski, Terrence J.: Characterizing brain connectivity from human electrocorticography recordings with unobserved inputs during epileptic seizures (2019)
  9. Litvinenko, Alexander; Sun, Ying; Genton, Marc G.; Keyes, David E.: Likelihood approximation with hierarchical matrices for large spatial datasets (2019)
  10. Sanguinetti, Guido (ed.); Huynh-Thu, Vân Anh (ed.): Gene regulatory networks. Methods and protocols (2019)
  11. Bottou, Léon; Curtis, Frank E.; Nocedal, Jorge: Optimization methods for large-scale machine learning (2018)
  12. Devijver, Emilie; Gallopin, Mélina: Block-diagonal covariance selection for high-dimensional Gaussian graphical models (2018)
  13. Boutsidis, Christos; Drineas, Petros; Kambadur, Prabhanjan; Kontopoulou, Eugenia-Maria; Zouzias, Anastasios: A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix (2017)
  14. Das, Anup; Sampson, Aaron L.; Lainscsek, Claudia; Muller, Lyle; Lin, Wutu; Doyle, John C.; Cash, Sydney S.; Halgren, Eric; Sejnowski, Terrence J.: Interpretation of the precision matrix and its application in estimating sparse brain connectivity during sleep spindles from human electrocorticography recordings (2017)
  15. Han, Insu; Malioutov, Dmitry; Avron, Haim; Shin, Jinwoo: Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations (2017)
  16. Cai, T. Tony; Ren, Zhao; Zhou, Harrison H.: Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation (2016)
  17. Tarr, G.; Müller, S.; Weber, N. C.: Robust estimation of precision matrices under cellwise contamination (2016)
  18. Treister, Eran; Turek, Javier S.; Yavneh, Irad: A multilevel framework for sparse optimization with application to inverse covariance estimation and logistic regression (2016)
  19. Zhang, Liangliang; Yang, Longqi; Hu, Guyu; Pan, Zhisong; Li, Zhen: Link prediction via sparse Gaussian graphical model (2016)
  20. Hsieh, Cho-Jui; Sustik, Mátyás A.; Dhillon, Inderjit S.; Ravikumar, Pradeep: QUIC: quadratic approximation for sparse inverse covariance estimation (2014)