Title: Message Passing Algorithms and Improved LP Decoding
Speaker: David Steurer, Princeton University
Date: Wednesday, March 23, 2009 11:00-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance (coming close to that of iterative decoding algorithms) and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel.
Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and significantly higher than the best previously noted correctable bit error rates. Unlike other techniques, our analysis considers directly the primal linear program, and works by exploiting an explicit connection between LP decoding, Sherali-Adams relaxations, and message passing algorithms.
Joint work with Sanjeev Arora and Constantinos Daskalakis.