A Caltech Library Service

Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis

Chandrasekaran, Venkat and Johnson, Jason K. and Willsky, Alan S. (2007) Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis. In: Advances in Neural Information Processing Systems 20. MIT Press , Cambridge, MA, pp. 249-256.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Record Number:CaltechAUTHORS:20121008-155412807
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34766
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 23:10
Last Modified:03 Oct 2019 04:22

Repository Staff Only: item control page