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 27 articles )

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

1 2 next

  1. Bian, Fengmiao; Liang, Jingwei; Zhang, Xiaoqun: A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization (2021)
  2. Phan, Dzung T.; Menickelly, Matt: On the solution of (\ell_0)-constrained sparse inverse covariance estimation problems (2021)
  3. Bertsimas, Dimitris; Lamperski, Jourdain; Pauphilet, Jean: Certifiably optimal sparse inverse covariance estimation (2020)
  4. Ghose, Amur; Jaini, Priyank; Poupart, Pascal: Learning directed acyclic graph SPNs in sub-quadratic time (2020)
  5. Lin, Tiger W.; Chen, Yusi; Bukhari, Qasim; Krishnan, Giri P.; Bazhenov, Maxim; Sejnowski, Terrence J.: Differential covariance: a new method to estimate functional connectivity in fMRI (2020)
  6. Li, Tianxi; Qian, Cheng; Levina, Elizaveta; Zhu, Ji: High-dimensional Gaussian graphical models on network-linked data (2020)
  7. Nakagaki, Takashi; Fukuda, Mituhiro; Kim, Sunyoung; Yamashita, Makoto: A dual spectral projected gradient method for log-determinant semidefinite problems (2020)
  8. Tajbakhsh, Sam Davanloo; Aybat, Necdet Serhat; Del Castillo, Enrique: On the theoretical guarantees for parameter estimation of Gaussian random field models: a sparse precision matrix approach (2020)
  9. Wang, Cheng; Jiang, Binyan: An efficient ADMM algorithm for high dimensional precision matrix estimation via penalized quadratic loss (2020)
  10. Wu, Yichong; Li, Tiejun; Liu, Xiaoping; Chen, Luonan: Differential network inference via the fused D-trace loss with cross variables (2020)
  11. Yu, Hang; Wu, Songwei; Xin, Luyin; Dauwels, Justin: Fast Bayesian inference of sparse networks with automatic sparsity determination (2020)
  12. Zhang, Yangjing; Zhang, Ning; Sun, Defeng; Toh, Kim-Chuan: A proximal point dual Newton algorithm for solving group graphical Lasso problems (2020)
  13. Ağraz, Melih; Purutçuoğlu, Vilda: Extended Lasso-type MARS (LMARS) model in the description of biological network (2019)
  14. Bollhöfer, Matthias; Eftekhari, Aryan; Scheidegger, Simon; Schenk, Olaf: Large-scale sparse inverse covariance matrix estimation (2019)
  15. 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)
  16. Litvinenko, Alexander; Sun, Ying; Genton, Marc G.; Keyes, David E.: Likelihood approximation with hierarchical matrices for large spatial datasets (2019)
  17. Sanguinetti, Guido (ed.); Huynh-Thu, Vân Anh (ed.): Gene regulatory networks. Methods and protocols (2019)
  18. Bottou, Léon; Curtis, Frank E.; Nocedal, Jorge: Optimization methods for large-scale machine learning (2018)
  19. Devijver, Emilie; Gallopin, Mélina: Block-diagonal covariance selection for high-dimensional Gaussian graphical models (2018)
  20. 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)

1 2 next