Title:
Message Passing Algorithms and Improved LP Decoding

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.