Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis
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.
Attached Files
Submitted - cjw_et_nips07.pdf
Files
Name | Size | Download all |
---|---|---|
md5:928b943437f13936463bb55a223ce699
|
718.2 kB | Preview Download |
Additional details
- Eprint ID
- 34766
- Resolver ID
- CaltechAUTHORS:20121008-155412807
- Created
-
2012-10-08Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field