|
Activity Number:
|
177
|
|
Type:
|
Invited
|
|
Date/Time:
|
Monday, July 30, 2007 : 2:00 PM to 3:50 PM
|
|
Sponsor:
|
IMS
|
| Abstract - #307918 |
|
Title:
|
Large-Scale Covariance Selection by Chordal Embedding
|
|
Author(s):
|
Lieven Vandenberghe*+ and Joachim Dahl
|
|
Companies:
|
University of California, Los Angeles and Aalborg University
|
|
Address:
|
Electrical Engineering Department, Los Angeles, CA, 90095-1594,
|
|
Keywords:
|
covariance selection ; convex optimization ; graphical models ; chordal graphs ; semidefinite programming
|
|
Abstract:
|
We discuss algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints, also known as covariance selection. The problem can be formulated as an unconstrained convex optimization problem and has a well-known closed-form solution if the underlying graph is chordal. Our focus will be on convex optimization algorithms for problems with non-chordal graphs. We first derive efficient methods for evaluating and inverting 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. We then use these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large non-chordal graphs, by embedding the graph in a chordal graph. We also discuss connections with sparse semidefinite programming.
|
