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 is significantly higher than the best previously noted correctable bit error rate for LP decoding. Unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between LP decoding and message passing algorithms.

An interesting byproduct of our method is a notion of a "locally optimal" solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a "re-weighted" version of the min-sum algorithm, obviating the need for linear programming. Our analysis implies, in particular, that this re-weighted version of the min-sum decoder corrects up to a 0.05-fraction of errors.

REFERENCES

• 1: E. J. Candes and T. Tao. Near--optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52(12):5406--5425, 2006.
• 2: J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu. Reduced-complexity decoding of LDPC codes. Communications, IEEE Transactions on, 53(8):1288--1299, Aug. 2005.
• 3: J. Chen and M. Fossorier. Density evolution for two improved BP-based decoding algorithms of LDPC codes. Communications Letters, IEEE, 6(5):208--210, May 2002.
• 4: J. Chen and M. Fossorier. Near optimum universal belief propagation based decoding of low-density parity check codes. Communications, IEEE Transactions on, 50(3):406--414, Mar 2002.
• 5: C. Daskalakis, A. G. Dimakis, R. M. Karp, and M. J. Wainwright. Probabilistic analysis of linear programming decoding. IEEE Transactions on Information Theory, 54(8):3565--3578, 2008.
• 6: Jon Feldman , David R. Karger, Decoding turbo-like codes via linear programming, Journal of Computer and System Sciences, v.68 n.4, p.733-752, June 2004 [doi>10.1016/j.jcss.2003.11.005]
• 7: J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright. Lp decoding corrects a constant fraction of errors. IEEE Transactions on Information Theory, 53(1):82--89, 2007.
• 8: J. Feldman, M. J. Wainwright, and D. R. Karger. Using linear programming to decode binary linear codes. IEEE Trans. Inform. Theory, 51(3):954--972, 2005.
• 9: B. J. Frey and R. Koetter. The attenuated max-product algorithm. In Advanced mean field methods (Birmingham, 1999), Neural Inf. Process. Ser., pages 213--227. MIT Press, Cambridge, MA, 2001.
• 10: R. G. Gallager. Low-density parity check codes. MIT Press, Cambridge, MA, 1963.
• 11: Venkatesan Guruswami , James R. Lee , Alexander Razborov, Almost Euclidean subspaces of ℓ^N₁ via expander codes, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.353-362, January 20-22, 2008, San Francisco, California
• 12: Piotr Indyk, Explicit constructions for compressed sensing of sparse signals, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.30-33, January 20-22, 2008, San Francisco, California
• 13: R. Koetter and P. O. Vontobel. On the block error probability of LP decoding of LDPC codes. In Inaugural Workshop of the Center for Information Theory and its Applications, 2006. Available as eprint arXiv:cs/0602086v1.
• 14: T. Richardson and R. Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. on Info. Theory, 47(2), Feb. 2001.
• 15: Hanif D. Sherali , Warren P. Adams, A hierarchy of relaxation between the continuous and convex hull representations, SIAM Journal on Discrete Mathematics, v.3 n.3, p.411-430, Aug. 1990 [doi>10.1137/0403036]
• 16: A. Shokrollahi. Ldpc codes: An introduction. M. Sipser and D. Spielman. Expander codes. IEEE Trans. Info. Theory, 42:1710--1722, November 1996.
• 17: N. Wiberg. Codes and Decoding on General Graphs. PhD thesis, Linkoeping University, Sweden, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
ldpc codes, lp decoding, message-passing algorithms, min-sum algorithm