CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20121008-155412807

[img]
Preview
PDF - Submitted Version
See Usage Policy.

718kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20121008-155412807

Abstract

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
http://books.nips.cc/papers/files/nips20/NIPS2007_0539.pdfPublisherUNSPECIFIED
Record Number:CaltechAUTHORS:20121008-155412807
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20121008-155412807
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34766
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 23:10
Last Modified:03 Oct 2019 04:22

Repository Staff Only: item control page