2009 Research Summary

Probabilistic Analysis of Linear Programming Decoding

View Current Project Information

Konstantinos Daskalakis, Georgios Alexandros Dimakis, Richard M. Karp and Martin Wainwright

National Science Foundation CCF-0515259, National Science Foundation DMS-0528488, National Science Foundation CCF-0515259, Marvell and California MICRO

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses all prior non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a flow on hypergraphs. An interesting by-product of our analysis is to establish the existence of "almost expansion" in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, with expansion coefficients much larger than the classical case.

[1]

C. Daskalakis, A. G. Dimakis, R. Karp, and M. J. Wainwright, "Probabilistic Analysis of Linear Programming Decoding," SIAM Symp. Discrete Algorithms (SODA), New Orleans, LA, January 2007.