LP decoding achieves capacity

ABSTRACT

We give a linear programming (LP) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. This is the first such result for LP decoding. More generally, as far as the authors are aware this is the first known polynomial-time capacity-achieving decoder with the maximum-likelihood (ML) certificate property---where output codewords come with a proof of optimality. Additionally, this result extends the capacity-achieving property of expander codes beyond the binary symmetric channel to a larger family of communication channels.Perhaps most importantly, since LP decoding performs well in practice on turbo codes and low-density parity-check (LDPC) codes (comparable to the popular "belief propagation" algorithm), this result exhibits the power of a new, widely applicable "dual witness" technique (Feldman, Malkin, Servedio, Stein and Wainwright, ISIT '04) for bounding decoder performance.For expander codes over an adversarial channel, we prove that LP decoding corrects a constant fraction of errors. To show this, we provide a new combinatorial characterization of error events that is of independent interest, and which we expect will lead to further improvements.

REFERENCES

• 1: N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6 ]
• 2: A. Barg and G. Zémor. Error exponents of expander codes. IEEE Trans. on Information Theory, 48(6):1725--1729, 2002.
• 3: A. Barg and G. Zémor. Concatenated codes: Serial and parallel. Manuscript, submitted to IEEE Trans. on Information Theory, 2003.
• 4: Alexander Barg , Gilles Zémor, Error Exponents of Expander Codes under Linear-Complexity Decoding, SIAM Journal on Discrete Mathematics, v.17 n.3, p.426-445, 2004 [doi>10.1137/S0895480102403799]
• 5: C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: turbo-codes. Proc. IEEE International Conf. on Comm. (ICC), pages 1064--1070, May 1993.
• 6: D. Burshtein and G. Miller. Expander graph arguments for message-passing algorithms. IEEE Trans. on Information Theory, pages 782--790, February 2002.
• 7: S.-Y. Chung, G. D. Forney, T. Richardson, and R. Urbanke. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit. IEEE Communications Letters, 5(2):58--60, February 2001.
• 8: C. Di, D. Proietti, T. Richardson, E. Telatar, and R. Urbanke. Finite length analysis of low-density parity check codes. IEEE Trans. on Information Theory, 48(6), 2002.
• 9: Jon Feldman , David R. Karger, Decoding error-correcting codes via linear programming, 2003
• 10: J. Feldman, D. R. Karger, and M. J. Wainwright. Linear programming-based decoding of turbo-like codes and its relation to iterative approaches. In Proc. 40th Annual Allerton Conf. on Communication, Control, and Computing, October 2002.
• 11: J. Feldman, D. R. Karger, and M. J. Wainwright. LP decoding. In Proc. 41st Annual Allerton Conf. on Comm., Control, and Computing, October 2003.
• 12: Jon Feldman , David R. Karger, Decoding Turbo-Like Codes via Linear Programming, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.251-260, November 16-19, 2002
• 13: J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright. LP decoding corrects a constant fraction of errors. In Proc. IEEE International Symposium on Information Theory, 2004.
• 14: J. Feldman, M. J. Wainwright, and D. R. Karger. Using linear programming to decode linear codes. 37th annual Conf. on Information Sciences and Systems (CISS '03), March 2003. Submitted to IEEE Trans. on Information Theory, May, 2003.
• 15: G. D. Forney. Concatenated Codes. M.I.T., 1966.
• 16: G. D. Forney, R. Koetter, F. R. Kschischang, and A. Reznik. On the effective weights of pseudocode-words for codes defined on graphs with cycles. In Codes, systems and graphical models, pages 101--112. Springer, 2001.
• 17: R. Gallager. Low-density parity-check codes. IRE Trans. Inform. Theory, IT-8:21--28, Jan. 1962.
• 18: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 19: Venkatesan Guruswami , Piotr Indyk, Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510023]
• 20: Venkatesan Guruswami , Piotr Indyk, Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: R. Koetter and P. O. Vontobel. Graph-covers and iterative decoding of finite length codes. In Proc. 3rd International Symp. on Turbo Codes, September 2003.
• 22: Ralf Koetter. personal communication, 2004.
• 23: M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman. Improved low-density parity-check codes using irregular graphs and belief propagation. Proc. 1998 IEEE International Symposium on Information Theory, page 117, 1998.
• 24: 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.
• 25: R. M. Roth and V. Skachek. On nearly-MDS expander codes. In International Symposium on Information Theory (ISIT '04), Chicago, IL, June 2004.
• 26: C. E. Shannon. A mathematical theory of communication. Bell System Tech. Journal, 27:379--423, 1948.
• 27: M. Sipser and D. Spielman. Expander codes. IEEE Trans. on Information Theory, 42(6):1710--1722, 1996.
• 28: V. Skachek and R. Roth. Generalized minimum distance iterative decoding of expander codes. In Proc. IEEE Information Theory Workshop, 2003.
• 29: Daniel Alan Spielman , Michael Sipser, Computationally efficient error-correcting codes and holographic proofs, 1995
• 30: P.O. Vontobel and R. Koetter. Lower bounds on the minimum pseudo-weight of linear codes. In International Symposium on Information Theory (ISIT '04), Chicago, IL, June 2004.
• 31: P.O. Vontobel and R. Koetter. On the relationship between linear programming decoding and max-product decoding. Manuscript, submitted to ISITA 2004, Parma, Italy, May 2004.
• 32: N. Wiberg. Codes and Decoding on General Graphs. PhD thesis, Linkoping University, Sweden, 1996.
• 33: G. Zémor. On expander codes. IEEE Trans. on Information Theory, 47(2):835--837, 2001.