Title: Decoding Error-Correcting Codes via Linear Programming
Speaker: Jon Feldman, Columbia University
Date: October 20, 2003 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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.