Abstract

We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selection, and it can be expressed as an unconstrained convex optimization problem with a closed-form solution if the underlying graph is chordal. The focus of the paper is on iterative algorithms for covariance selection with nonchordal graphs. We first derive efficient methods for evaluating the gradient and Hessian of the log-likelihood function when the underlying graph is chordal. The algorithms are formulated as simple recursions on a clique tree associated with the graph. We also show that the gradient and Hessian mappings are easily inverted when the underlying graph is chordal. We then exploit these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large nonchordal graphs, by embedding the graph in a chordal graph.

Keywords

Chordal graphMathematicsHessian matrixTreewidthBlock graphMathematical optimizationCombinatoricsDiscrete mathematicsGraphPathwidthLine graphApplied mathematics1-planar graph

Affiliated Institutions

Related Publications

Preconditioning of Truncated-Newton Methods

Stephen G. Nash

In this paper we discuss the use of truncated-Newton methods, a flexible class of iterative methods, in the solution of large-scale unconstrained minimization problems. At each ...

1985 SIAM Journal on Scientific and Statis... 175 citations

Publication Info

Year
2008
Type
article
Volume
23
Issue
4
Pages
501-520
Citations
117
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

117
OpenAlex

Cite This

Joachim Dahl, Lieven Vandenberghe, Vwani Roychowdhury (2008). Covariance selection for nonchordal graphs via chordal embedding. Optimization methods & software , 23 (4) , 501-520. https://doi.org/10.1080/10556780802102693

Identifiers

DOI
10.1080/10556780802102693