A Caltech Library Service

Decomposition Methods for Large Scale LP Decoding

Barman, Siddharth and Liu, Xishuo and Draper, Stark C. and Recht, Benjamin (2013) Decomposition Methods for Large Scale LP Decoding. IEEE Transactions on Information Theory, 59 (12). pp. 7870-7886. ISSN 0018-9448. doi:10.1109/TIT.2013.2281372.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper, we draw on decomposition methods from optimization theory, specifically the alternating direction method of multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a “two-slice” characterization of the parity polytope, the polytope formed by taking the convex hull of all codewords of the single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by the ADMM decoder and its solution allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher SNR than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using the ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2013 IEEE. Manuscript received April 11, 2012; revised February 25, 2013; accepted April 29, 2013. Date of publication September 10, 2013; date of current version November 19, 2013. This work was supported in part by the National Science Foundation under Grants CCF-1217058 and CCF-1148243 and in part by the Office of Naval Research under Award N00014-13-1-0129. The work in this paper was performed while the authors were affiliated with the University of Wisconsin, Madison. This paper was presented in part at the Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 2011. The authors would like to thank M. Anderson, B. Butler, E. Bach, A. Dimakis, P. Siegel, E. Telatar, Y. Wang, J. Yedidia, and D. Zelený for useful discussions and references. The authors would also like to note that some of the simulation results presented herein would not have been possible without the resources and the computing assistance of the University of Wisconsin (UW), Madison, Center For High Throughput Computing (CHTC) in the Department of Computer Sciences. The CHTC is supported by UW-Madison and the Wisconsin Alumni Research Foundation, and is an active member of the Open Science Grid, which is supported by the National Science Foundation and the U.S. Department of Energy’s Office of Science.
Funding AgencyGrant Number
University of Wisconsin MadisonUNSPECIFIED
Wisconsin Alumni Research FoundationUNSPECIFIED
Department of Energy (DOE) Office of ScienceUNSPECIFIED
Office of Naval Research (ONR)N00014-13-1-0129
Subject Keywords:Alternating direction method of multipliers (ADMM); belief propagation (BP); decomposition methods; error floors; Euclidean projection; graphical models; iterative algorithms; linear programming (LP) decoding; low-density parity check (LDPC) codes; parity polytope; permutohedron
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number13914290
Issue or Number:12
Record Number:CaltechAUTHORS:20140103-101249506
Persistent URL:
Official Citation:Barman, S.; Xishuo Liu; Draper, S.C.; Recht, B., "Decomposition Methods for Large Scale LP Decoding," Information Theory, IEEE Transactions on , vol.59, no.12, pp.7870,7886, Dec. 2013 doi: 10.1109/TIT.2013.2281372 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:43201
Deposited By: Tony Diaz
Deposited On:03 Jan 2014 19:10
Last Modified:10 Nov 2021 16:34

Repository Staff Only: item control page