Probabilistic Analysis of Linear Programming Decoding

Abstract

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 previous 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 generalized matching. An interesting by-product of our analysis is to establish the existence of ``probabilistic expansion'' in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst-case setting.

To appear, IEEE Transactions on Information Theory, (replaces shorter version that appeared in SODA'07)

References in corpus (3)

• Towards Low-Complexity Linear-Programming Decoding
• Adaptive Linear Programming Decoding
• An Efficient Pseudo-Codeword Search Algorithm for Linear Programming Decoding of LDPC Codes

Cited by in corpus (18)

• LDPC Codes for Compressed Sensing
• The ADMM penalized decoder for LDPC codes
• Instanton-based Techniques for Analysis and Reduction of Error Floors of LDPC Codes
• Optimization by Decoded Quantum Interferometry
• Relax, no need to round: integrality of clustering formulations
• Decomposition Methods for Large Scale LP Decoding
• LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing
• Improved Linear Programming Decoding using Frustrated Cycles
• Error Bounds for Repeat-Accumulate Codes Decoded via Linear Programming
• Proximal-ADMM Decoder for Nonbinary LDPC Codes
• SMYRF: Efficient Attention using Asymmetric Clustering
• Reweighted LP Decoding for LDPC Codes
• ADMM LP decoding of non-binary LDPC codes in ${\mathbb{F}}_{2^m}$
• Exact MAP Inference by Avoiding Fractional Vertices
• Local-Optimality Guarantees for Optimal Decoding Based on Paths
• LP Decoding of Regular LDPC Codes in Memoryless Channels
• Impact of redundant checks on the LP decoding thresholds of LDPC codes
• Linear Programming Decoding of Spatially Coupled Codes