Learning Sparse Gaussian Markov Networks Using a Greedy Coordinate Ascent Approach

Abstract

In this paper, we introduce a simple but efficient greedy algorithm, called SINCO , for the Sparse INverse COvariance selection problem, which is equivalent to learning a sparse Gaussian Markov Network, and empirically investigate the structure-recovery properties of the algorithm. Our approach is based on a coordinate ascent method which naturally preserves the sparsity of the network structure. We show that SINCO is often comparable to, and, in various cases, outperforms commonly used approaches such as glasso [7] and COVSEL [1], in terms of both structure-reconstruction error (particularly, false positive error) and computational time. Moreover, our method has the advantage of being easily parallelizable. Finally, we show that SINCO’s greedy nature allows reproduction of the regularization path behavior by applying the method to one (sufficiently small) instance of the regularization parameter λ only; thus, SINCO can obtain a desired number of network links directly, without having to tune the λ parameter. We evaluate our method empirically on various simulated networks and real-life data from biological and neuroimaging applications.