Loopy Belief Propagation

Abstract:
This talk presents an analysis of Loopy Belief Propagation (LBP), a widely applied – but relatively poorly understood – heuristic used in communications, vision and image processing, statistical physics etc. We demonstrate how the theory of Linear programming can be used for an analysis of LBP in two settings.
In the first part of the talk, we investigate the performance of LBP in solving two canonical combinatorial problems: weighted matching and independent set. Both problems also naturally arise in network/resource scheduling in the presence of interference. For any instance of either problem, we demonstrate that the success of LBP is exactly characterized by the presence of fractional optima in the LP relaxation of the instance. This analysis yields techniques for enhancing the performance of LBP.
One of the signature successes of LBP has been the iterative decoding of codes. In the second part of the talk we investigate the performance of LBP for fountain codes, but when the amount of received information is LESS THAN that required for perfect recovery – a situation that is likely to occur in wireless or real-time settings. We use Linear programming to characterize the extent to which PARTIAL recovery is possible. This analysis yields new design principles for fountain codes.

Bio:
Sujay has a B. Tech in EE from IIT Bombay, an MS in ECE and MS in Mathematics from UIUC, and a PhD in ECE from UIUC. In his graduate research, he worked with Bruce Hajek on the design and analysis of communication networks. After graduating in 2006, Sujay has been a postdoc in MIT, where he works with Alan Willsky (and others) on large-scale signal processing problems.
Sujay's primary research interests are in probability and optimization, as applied to the design of algorithms in communications and signal processing.