Skip navigation

Analysis of Loopy Belief Propagation: Walk-Sums and Linear Programming Approaches

Event Date: November 18, 2009
Speaker: Dr Dmitry Malioutov
Speaker Affiliation: DRW, Chicago
Sponsor: CNSIP Area Seminar
Time: 4:15 pm
Location: EE 118
Contact Name: Prof. Ilya Pollak
Contact Email:

Loopy belief propagation and its variants have emerged as a powerful yet enigmatic algorithmic framework that revolutionized a number of applied fields: from error control coding, to computer vision, computational biology, and combinatorial optimization. Belief propagation has a solid foundation for problems which have a certain tree-structure, but its success in graphs with loops is not fully understood even after a forceful barrage of research efforts from machine learning, statistical physics and theoretical computer science communities. 


In this talk we consider two specific versions of belief propagation: BP for Gaussian models, and BP for the discrete maximum-weight matching problem.  We describe the walk-sum framework which sheds much light on convergence and accuracy properties of Gaussian BP, and a linear-programming analysis of BP for weighted matching BP.  We also describe some applications of these algorithms in sensor networks and remote sensing.




Dmitry Malioutov obtained his PhD in Electrical Engineering and Computer Science from MIT in 2008.  After a postdoc position in the Machine Learning and Perception group in Microsoft Research, UK, he is now conducting research in algorithmic trading in DRW, Chicago.  His research is focused on statistical signal processing, machine learning and convex optimization, with special interest in sparse signal representation, graphical models and message passing algorithms.