Efficient projection onto the parity polytope and its application to LP decoding

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 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 talk 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 nearly linear time algorithm for two-norm projection onto the "parity polytope" . The parity polytope is formed by taking the convex hull of all codewords of the single parity-check code. Efficient solution of this projection allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We discuss performance results for a number of long LDPC codes, presenting results on error rates and computational complexity. In comparison to BP decoding we observe that the waterfall of the LP decoder initiates at a higher SNR. In conclusion we present a small modification of the LP decoder wherein by slightly penalizing the linear objective of the LP we close the SNR gap between BP and LP.

joint work with Siddarth Barman, Xishuo Liu, and Benjamin Recht
Stark Draper cooks up the math that makes your mobile phone work. His other recipes make your computer more energy-efficient and store your personal biometric data more securely. He has held academic, industrial and consulting roles with Arraycomm Inc., a telecommunications start-up in California, the Mitsubishi Electric Research Labs (MERL), UC Berkeley and UW-Madison. He leads his research team in collaborations with 3M, Bell Labs, Disney Research, Facebook, HP Labs, IBM, Mitsubishi Electric and Samsung, among others. His is an Associate Professor at the University of Toronto and from 2007-2013 was an Associate Professor at the University of Wisconsin, Madison. He has received the NSF CAREER Award and the Mitsubishi Electric Research Lab (MERL) President's Award.