Iterative Thresholding Algorithm for Sparse Inverse Covariance Estimation

Abstract

The L1-regularized maximum likelihood estimation problem has recently become a topic of great interest within the machine learning, statistics, and optimization communities as a method for producing sparse inverse covariance estimators. In this paper, a proximal gradient method (G-ISTA) for performing L1-regularized covariance matrix estimation is presented. Although numerous algorithms have been proposed for solving this problem, this simple proximal gradient method is found to have attractive theoretical and numerical properties. G-ISTA has a linear rate of convergence, resulting in an O(log e) iteration complexity to reach a tolerance of e. This paper gives eigenvalue bounds for the G-ISTA iterates, providing a closed-form linear convergence rate. The rate is shown to be closely related to the condition number of the optimal point. Numerical convergence results and timing comparisons for the proposed method are presented. G-ISTA is shown to perform very well, especially when the optimal point is well-conditioned.

25 pages, 1 figure, 4 tables. Conference paper

Cited by in corpus (25)

• Embarrassingly Shallow Autoencoders for Sparse Data
• BDgraph: An R Package for Bayesian Structure Learning in Graphical Models
• Composite Self-Concordant Minimization
• Statistical paleoclimate reconstructions via Markov random fields
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
• A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions
• G-AMA: Sparse Gaussian graphical model estimation via alternating minimization
• A Scalable Algorithm for Gaussian Graphical Models with Change-Points
• Learning linear structural equation models in polynomial time and sample complexity
• Distributionally Robust Formulation and Model Selection for the Graphical Lasso
• Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion
• Structure Learning of Gaussian Markov Random Fields with False Discovery Rate Control
• GLAD: Learning Sparse Graph Recovery
• Methods for Recovering Conditional Independence Graphs: A Survey
• SG-PALM: a Fast Physically Interpretable Tensor Graphical Model
• A Novel Approach to Sparse Inverse Covariance Estimation Using Transform Domain Updates and Exponentially Adaptive Thresholding
• Gaussian graphical models with graph constraints for magnetic moment interaction in high entropy alloys
• Exact Hybrid Covariance Thresholding for Joint Graphical Lasso
• Learning to Learn Graph Topologies
• Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles
• Efficient proximal gradient algorithms for joint graphical lasso
• Differentially Private Precision Matrix Estimation
• Estimating Multiple Precision Matrices with Cluster Fusion Regularization
• Distributed Estimation of Sparse Inverse Covariances