Sparse Inverse Covariance Estimation via an Adaptive Gradient-Based Method

2011/06/25 by Suvrit Sra, Sra, Suvrit, Kim, Dongmin
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (stat.ML) #Medical Image Segmentation Techniques #Robotics and Sensor-Based Localization #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1106.5175

openalex publication_date 2011/06/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We study the problem of estimating from data, a sparse approximation to the inverse covariance matrix. Estimating a sparsity constrained inverse covariance matrix is a key component in Gaussian graphical model learning, but one that is numerically very challenging. We address this challenge by developing a new adaptive gradient-based method that carefully combines gradient information with an adaptive step-scaling strategy, which results in a scalable, highly competitive method. Our algorithm, like its predecessors, maximizes an ℓ₁-norm penalized log-likelihood and has the same per iteration arithmetic complexity as the best methods in its class. Our experiments reveal that our approach outperforms state-of-the-art competitors, often significantly so, for large problems.

Citations

• Smooth minimization of non-smooth functions

Related

• Adaptive First-Order Methods for General Sparse Inverse Covariance Selection
• G-AMA: Sparse Gaussian graphical model estimation via alternating minimization
• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods
• A Novel Approach to Sparse Inverse Covariance Estimation Using Transform Domain Updates and Exponentially Adaptive Thresholding