Information Theory Seminar

TITLE: Van der Waals Curve and Maxwell Construction for Probabilistic Coding

SPEAKER: Cyril Measson (Bell Labs and Stanford University)

DATE: 2:00 - 3:00 PM, Wednesday, February 14, 2007

LOCATION: Sigma Conference Room, 1L

ABSTRACT:
Message-passing algorithms, in particular Belief Propagation (BP), are of fundamental and practical importance for information sciences as well as for statistical physics. Recent progress in their understanding has been obtained from the exchange of ideas between different fields. In this talk, we investigate BP in the framework of information theory and we deal with coding systems based on sparse graphs. The key issue we present is the relationship between BP and Maximum A Posteriori (MAP) decoding. We show that between the two there is a fundamental connection, which is reminiscent of the Maxwell construction in thermodynamics.

The main objects we consider are EXIT (extrinsic information transfer)-like functions, i.e., linear operators that act on a probability density function and perform a one-dimensional projection of this density. EXIT functions were originally introduced as handy tools for the design of iterative coding systems. It gradually became clear that EXIT functions possess several fundamental properties. Many of these properties, however, apply only to the erasure case. This motivates us to introduce GEXIT (generalized EXIT) functions that coincide with EXIT functions over the binary erasure channel (BEC). In many aspects, GEXIT functions over general memoryless symmetric channels play the same role as EXIT functions do over the BEC. In particular, GEXIT functions are characterized by the general area theorem.

The perhaps most appealing consequence of this theorem is that we can use GEXIT functions to show that in the limit of large sparse graphs a fundamental connection appears between BP and MAP decoding. In this asymptotic setting, the BP and MAP performance curves are characterized by a common object that is similar to the Van der Waals equation of state and that is called EBP GEXIT curve. It is shown that the MAP performance curve and the MAP threshold can be determined from the EBP GEXIT curve via a Maxwell-type construction. A decoding algorithm, which we call Maxwell decoder, provides an operational interpretation of this relationship for the BEC. Both the algorithm and the analysis of the decoder are the translation of the Maxwell construction from thermodynamics to the context of probabilistic decoding. We show the first steps to extend this construction to general memoryless output-symmetric channels. More exactly, a general upper bound on the MAP threshold for sparse graph codes is given. It is conjectured that the fundamental connection between BP and MAP carries over to the general case.

BIOGRAPHY:
Cyril Measson wrote his M.Sc. thesis at the Munich University of Technology (TUM) in 1998. From 1998 to 2000 he was with the Institute for Communications Engineering at TUM and Bell-Labs, Lucent, Murray Hill. From 2000 to 2001 he was attending the doctoral school in Communication Systems at the Swiss Federal Institute of Technology (EPFL) in Lausanne. He received his Ph.D. in Electrical Engineering from EPFL in 2006. He is recipient of an SNF (Swiss National Fund) research fellowship and is currently a visiting post-doctoral researcher at Stanford (on leave from Alcatel-Lucent, Murray Hill).