Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation

Abstract

The L1-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 other state-of-the-art methods.

References in corpus (2)

• Pathwise coordinate optimization
• Projected Subgradient Methods for Learning Sparse Gaussians

Cited by in corpus (48)

• Learning graphs from data: A signal representation perspective
• On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data
• BDgraph: An R Package for Bayesian Structure Learning in Graphical Models
• Composite Self-Concordant Minimization
• Robust estimation of precision matrices under cellwise contamination
• Dropping Convexity for Faster Semi-definite Optimization
• L0 Sparse Inverse Covariance Estimation
• Statistical paleoclimate reconstructions via Markov random fields
• Learning Laplacian Matrix in Smooth Graph Signal Representations
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Solving the inverse Ising problem by mean-field methods in a clustered phase space with many states
• Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
• An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization
• Two Sample Inference for Populations of Graphical Models with Applications to Functional Connectivity
• Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis
• Robust Gaussian Graphical Modeling with the Trimmed Graphical Lasso
• Proximal Quasi-Newton for Computationally Intensive L1-regularized M-estimators
• A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions
• Compression Optimality of Asymmetric Numeral Systems
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Integrated Principal Components Analysis
• G-AMA: Sparse Gaussian graphical model estimation via alternating minimization
• Fast Low-Rank Matrix Estimation without the Condition Number
• Learning Directed Graphical Models from Gaussian Data
• Learning Clique Forests
• Annealing Gaussian into ReLU: a New Sampling Strategy for Leaky-ReLU RBM
• A Second-Order Method for Convex ${\ell }_1$-Regularized Optimization with Active Set Prediction
• Sparse Median Graphs Estimation in a High Dimensional Semiparametric Model
• Pairwise MRF Calibration by Perturbation of the Bethe Reference Point
• Composite Convex Optimization with Global and Local Inexact Oracles
• Structure Learning of Gaussian Markov Random Fields with False Discovery Rate Control
• An Efficient Linearly Convergent Regularized Proximal Point Algorithm for Fused Multiple Graphical Lasso Problems
• Large-Scale Optimization Algorithms for Sparse Conditional Gaussian Graphical Models
• Randomized block proximal damped Newton method for composite self-concordant minimization
• A Novel Approach to Sparse Inverse Covariance Estimation Using Transform Domain Updates and Exponentially Adaptive Thresholding
• Robust high-dimensional precision matrix estimation
• Robust sparse Gaussian graphical modeling
• A constrained L1 minimization approach for estimating multiple Sparse Gaussian or Nonparanormal Graphical Models
• Learning a Common Substructure of Multiple Graphical Gaussian Models
• Multidimensional mutual information methods for the analysis of covariation in multiple sequence alignments
• Exact Hybrid Covariance Thresholding for Joint Graphical Lasso
• Indirect multivariate response linear regression
• Predicting diverse M-best protein contact maps
• A Discriminative Gaussian Mixture Model with Sparsity
• Gaussian Graphical Model exploration and selection in high dimension low sample size setting
• Distributed Estimation of Sparse Inverse Covariances
• Combining Smoothing Spline with Conditional Gaussian Graphical Model for Density and Graph Estimation
• Estimation Rates for Sparse Linear Cyclic Causal Models