 |
TITLE:
Linear Programming and Message Passing
SPEAKER: Sujay Sanghavi (MIT)
DATE: 11:00 AM - 12:00 noon, September 7, 2007
LOCATION: Tioga, 3U
ABSTRACT:
Message-passing inference algorithms, like Belief Propagation, have
proven to be excellent heuristics for solving large-scale problems in
fields as diverse as image processing, machine learning and
error-control coding. These are local, iterative algorithms that operate
on graphs generated from the problem instances. Inspite of their
empirical success, there are few analytical guarantees or performance
characterizations when they are operated on general graphs with cycles.
In general these algorithms may not converge, or may converge to an
incorrect answer.
In this talk, we present new analytical results on the convergence and
correctness of one such algorithm - Max Product - for a few problems,
such as max-weight matching and max-weight stable set in general
(non-bipartite) graphs, and decoding for erasure channels. The analysis
relies on the theory of linear programming, and the method of LP
Relaxation, which provides a powerful framework for the analysis of
message-passing algorithms. Applications to decoding, scheduling etc.
will be discussed.
(The talk is self-contained, no specific background is assumed.)
BIOGRAPHY:
Sujay Sanghavi received his PhD in 2006 from the ECE department at the
University of Illinois, Urbana-Champaign, where he worked on
communication network algorithms. He also has an MS in Math and an MS in
ECE from UIUC, and a B. Tech in EE from IIT Bombay.
Sujay is currently a post-doc at LIDS, MIT where he works on the
analysis and design of message-passing algorithms. His research
interests are in probability and optimization as applied to problems in
communications and signal processing.
|
|
|
printable version
