Projected Subgradient Methods for Learning Sparse Gaussians
This work addresses the challenge of efficiently learning sparse graphical models for applications like biological networks and image modeling, though it is incremental as it builds on existing l1-regularization methods with speed improvements and extensions.
The paper tackles the problem of learning sparse Gaussian Markov random fields in high-dimensional spaces using l1-norm regularization on the inverse covariance matrix, resulting in a faster projected gradient method that matches the best asymptotic complexity and shows better generalization performance on biological network analysis and 2D-shape modeling tasks.
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.