Authors

Abstract

The sparse inverse covariance matrix is used to modelconditional dependencies between variables in a graphical model tofit a multivariate Gaussian distribution. Estimating the matrix fromdata is well known to be computationally expensive for large-scaleproblems. Sparsity is employed to handle noise in the data and topromote interpretability of a learning model. Although the use of aconvex $\ell_1$ regularizer to encourage sparsity is commonpractice, the combinatorial $\ell_0$ penalty often has morefavorable statistical properties. In this paper, we directlyconstrain sparsity by specifying a maximally allowable number ofnonzeros, in other words, by imposing an $\ell_0$ constraint. We introduce anefficient approximate Newton algorithm using warm starts for solvingthe nonconvex $\ell_0$-constrained inverse covariance learningproblem. Numerical experiments on standard data sets show that theperformance of the proposed algorithm is competitive withstate-of-the-art methods.