Projected Subgradient Methods for Learning Sparse Gaussians

Abstract

Gaussian Markov random fields (GMRFs) are useful in a broad range of applications. In this paper we tackle the problem of learning a sparse GMRF in a high-dimensional space. Our approach uses the l1-norm as a regularization on the inverse covariance matrix. We utilize a novel projected gradient method, which is faster than previous methods in practice and equal to the best performing of these in asymptotic complexity. We also extend the l1-regularized objective to the problem of sparsifying entire blocks within the inverse covariance matrix. Our methods generalize fairly easily to this case, while other methods do not. We demonstrate that our extensions give better generalization performance on two real domains--biological network analysis and a 2D-shape modeling image task.

Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

References in corpus (1)

• High-Dimensional Graphical Model Selection Using ${\ell }_1$-Regularized Logistic Regression

Cited by in corpus (8)

• Brain covariance selection: better individual functional connectivity models using population prior
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• Markov models for fMRI correlation structure: is brain functional connectivity small world, or decomposable into networks?
• Group Sparse Priors for Covariance Estimation
• A Graphical Model Formulation of Collaborative Filtering Neighbourhood Methods with Fast Maximum Entropy Training
• Improved Estimation of High-dimensional Ising Models
• Learning a Common Substructure of Multiple Graphical Gaussian Models
• Sparse Inverse Covariance Estimation via an Adaptive Gradient-Based Method