Collaborative Effort: Message-Passing Algorithms: From Practice to Theory and Back to Practice

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The research supported under this grant targets the thorough and effective understanding of message-passing algorithms which constitute a large and very potent class of estimation and detection techniques. Indeed, while message-passing (iterative) processing is very successful in practice, understanding its limitations and its sources of non-optimal behavior has been elusive. Despite the enormous impact that message-passing algorithms have, in particular in a communication scenario, practical systems currently rely almost exclusively on a simulation-based evaluation. In this situation, understanding the behavior and geometry of message-passing will not only reduce the necessity of simulations but provide powerful tools for system optimization. This proposal draws on recent exciting developments that connect message-passing algorithms to the well established theory of convex optimization. As it turns out, message-passing algorithms are intimately related to a linear programming formulation of the inference task at hand. In fact, belief propagation algorithms may be interpreted as an efficient duality-based method to closely approximate the solution to a linear program. Once such connections are established the investigators will strive to understand message-passing algorithms from an entirely new and fruitful point of view. Also, the investigators have already shown that the connection to convex optimization is rooted in the basic property of message-passing algorithms, namely that they operate only locally in a given graphical model. Thus the findings resulting from the approach investigated here will apply to any reasonable locally-operating algorithm.