Timezone: »

 
Poster
Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis
Venkat Chandrasekaran · Jason K Johnson · Alan S Willsky

Mon Dec 03 10:30 AM -- 10:40 AM (PST) @
in Poster Session »

We consider the estimation problem in Gaussian graphical models with arbitrary structure. We analyze the Embedded Trees algorithm, which solves a sequence of problems on tractable subgraphs thereby leading to the solution of the estimation problem on an intractable graph. Our analysis is based on the recently developed walk-sum interpretation of Gaussian estimation. We show that non-stationary iterations of the Embedded Trees algorithm using any sequence of subgraphs converge in walk-summable models. Based on walk-sum calculations, we develop adaptive methods that optimize the choice of subgraphs used at each iteration with a view to achieving maximum reduction in error. These adaptive procedures provide a significant speedup in convergence over stationary iterative methods, and also appear to converge in a larger class of models.

[ PDF] 

Author Information

Venkat Chandrasekaran (California Institute of Technology)
Jason K Johnson (Massachusetts Institute of Technology)
Alan S Willsky (Massachusetts Institute of Technology)

More from the Same Authors