Name
Title | ||
|---|---|---|
Estimation in Gaussian Graphical Models Using Tractable Subgraphs: A Walk-Sum Analysis |
Abstract | ||
|---|---|---|
Graphical models provide a powerful formalism for statistical signal processing. Due to their sophisticated modeling capabilities, they have found applications in a variety of fields such as computer vision, image processing, and distributed sensor networks. In this paper, we present a general class of algorithms for estimation in Gaussian graphical models with arbitrary structure. These algorithms involve a sequence of inference problems on tractable subgraphs over subsets of variables. This framework includes parallel iterations such as embedded trees, serial iterations such as block Gauss-Seidel, and hybrid versions of these iterations. We also discuss a method that uses local memory at each node to overcome temporary communication failures that may arise in distributed sensor network applications. We analyze these algorithms based on the recently developed walk-sum interpretation of Gaussian inference. We describe the walks ldquocomputedrdquo by the algorithms using walk-sum diagrams, and show that for iterations based on a very large and flexible set of sequences of subgraphs, convergence is guaranteed in walk-summable models. Consequently, we are free to choose spanning trees and subsets of variables adaptively at each iteration. This leads to efficient methods for optimizing the next iteration step to achieve maximum reduction in error. Simulation results demonstrate that these nonstationary algorithms provide a significant speedup in convergence over traditional one-tree and two-tree iterations. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/TSP.2007.912280 | IEEE Transactions on Signal Processing |
Keywords | Field | DocType |
gaussian graphical model,next iteration step,gaussian inference,walk-sums,maximum walk-sum block.,index terms— graphical models,sensor network,graphical model,maximum walk-sum tree,walk-sum analysis,sensor network application,tractable subgraphs,walk-sum diagrams,gauss-markov random fields,image processing,inference problem,distributed estimation,serial iteration,gaussian graphical,subgraph preconditioners,parallel iteration,estimation,spanning tree,application software,computer vision,image sensors,signal processing,spanning trees,computational modeling,convergence,graphical models,indexing terms,iterative methods,statistical signal processing,algorithm design and analysis,gauss seidel,gaussian processes,tree graphs | Convergence (routing),Mathematical optimization,Tree (graph theory),Iterative method,Theoretical computer science,Gaussian,Gaussian process,Graphical model,Statistical signal processing,Mathematics,Speedup | Journal |
Volume | Issue | ISSN |
56 | 5 | 1053-587X |
Citations | PageRank | References |
19 | 1.11 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Venkat Chandrasekaran | 1 | 716 | 37.92 |
| J.K. Johnson | 2 | 19 | 1.11 |
| Alan S. Willsky | 3 | 7466 | 847.01 |