Extended message passing algorithm for inference in loopy Gaussian graphical models Academic Article uri icon

abstract

  • We consider message passing for probabilistic inference in undirected Gaussian graphical models. We show that for singly connected graphs, message passing yields an algorithm that is equivalent to the application of Gaussian elimination to the solution of a particular system of equations. This relation provides a natural way of extending message passing to arbitrary graphs with loops by first studying the operations required by Gaussian elimination. We thus obtain a finite time convergent algorithm that solves the inference problem exactly and whose complexity grows gradually with the "distance" of the graph to a tree. This algorithm can be implemented in a distributed fashion at nodes through message passing, as for example in sensor networks. 2003 Elsevier B.V. All rights reserved.

published proceedings

  • Ad Hoc Networks

author list (cited authors)

  • Plarre, K. H., & Kumar, P. R.

citation count

  • 22

complete list of authors

  • Plarre, KH||Kumar, PR

publication date

  • April 2004