Oct 20:     Decoding Error-Correcting Codes via Linear Programming
                       Jon Feldman, Columbia University.



--------

Error-correcting codes are fundamental tools used to transmit digital
information over an unreliable channel.  Their study goes back to the work
of Shannon, who used them as the basis for the field of information
theory.  The problem of decoding up to the full error-correcting potential
of the system is often very complex, especially for modern codes that
approach the theoretical limits of the communication channel.

In this talk we investigate the application of linear programming (LP)
relaxation to the problem of decoding an error-correcting code.  Linear
programming relaxation is a standard technique in approximation algorithms
and operations research, and is central to the study of efficient
algorithms to find good (albeit suboptimal) solutions to very difficult
optimization problems.  Our new "LP decoders" have tight combinatorial
characterizations of decoding success that can be used to analyze
error-correcting performance.  Furthermore, LP decoders have the desirable
(and rare) property that whenever they output a result, it is guaranteed
to be the optimal result: the most likely (ML) information sent over the
channel.  We refer to this property as the "ML certificate" property.  We
also introduce the concept of the "fractional distance" of an LP
relaxation, and show that LP decoding always corrects a number of errors
up to half the fractional distance.

We analyze specific LP decoders for two major families of codes: "turbo"
codes and "low-density parity-check (LDPC)" codes.  These families of
codes have received a great deal of attention recently due to their
unprecedented error-correcting performance.  Our decoder is particularly
attractive for these codes because the standard message-passing algorithms
used for decoding are often difficult to analyze.  We compare the
performance of the LP decoder to the standard message-passing techniques,
both analytically and experimentally.  We also give new provably
convergent message-passing decoders based on linear programming duality.

This is joint work with David Karger and Martin Wainwright.