Covariance selection for nonchordal graphs via chordal embedding.
Saved in:
| Title: | Covariance selection for nonchordal graphs via chordal embedding. |
|---|---|
| Authors: | Dahl, Joachim1 (AUTHOR) joachim@es.aau.dk, Vandenberghe, Lieven2 (AUTHOR), Roychowdhury, Vwani2 (AUTHOR) |
| Source: | Optimization Methods & Software. Aug2008, Vol. 23 Issue 4, p501-520. 20p. 5 Diagrams, 3 Charts. |
| Subjects: | Sparse matrix software, Mathematical optimization, Mathematical analysis, Embeddings (Mathematics), Analysis of covariance |
| 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Optimization Methods & Software is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 10556788 |
| DOI: | 10.1080/10556780802102693 |
