Although min-sum algorithm (MSA) and linear programming (LP) decoding are tightly related, it is not straightforward to translate MSA decoding performance analysis techniques to the LP decoding setup. Towards closing this performance analysis techniques gap, Koetter and Vontobel [ITAW 2006] showed how the collection of messages from several MSA decoding iterations can be used to construct a dual witness for LP decoding, thereby deriving some performance results for LP decoding. In a recent breakthrough paper by Arora, Daskalakis, and Steurer (ADS) [STOC 2009], the understanding of the performance of LP decoding was brought to a new level, not only from the perspective of available analysis tools but also from the perspective of significantly improving the known asymptotic LP decoding threshold bounds. ADS achieved this by showing how MSA decoding analysis type results can be used in the primal domain of the LP decoder, along the way also giving evidence that the above detour over the dual domain is neither necessary nor simpler. In the present paper we focus on the geometrical aspects of the ADS paper and show that one of the key results of the ADS paper can be reformulated as the construction of a rather nontrivial class of supersets of the fundamental cone, where these supersets are convex cones that are generated by vectors that are derived from computation trees and minimal valid deviations therein. As we will discuss, the main ingredient that allows the verification of this superset construction is a certain class of backtrackless random walks on the code's normal factor graph. Moreover, formulating our results in terms of normal factor graphs will facilitate the generalization of the geometrical results of the ADS paper to setups with non-uniform node degrees, with other types of constraint function nodes, and with no restrictions on the girth. We conclude the paper by showing connections between the entropy rates of the above-mentioned random walks and the Bethe entropy function of the normal factor graph that these random walks are defined on.
Although min-sum algorithm (MSA) and linear programming (LP) decoding are tightly related, it is not straightforward to translate MSA decoding performance analysis techniques to the LP decoding setup. Towards closing this performance analysis techniques gap, Koetter and Vontobel [ITAW 2006] showed how the collection of messages from several MSA decoding iterations can be used to construct a dual witness for LP decoding, thereby deriving some performance results for LP decoding. In a recent breakthrough paper by Arora, Daskalakis, and Steurer (ADS) [STOC 2009], the understanding of the performance of LP decoding was brought to a new level, not only from the perspective of available analysis tools but also from the perspective of significantly improving the known asymptotic LP decoding threshold bounds. ADS achieved this by showing how MSA decoding analysis type results can be used in the primal domain of the LP decoder, along the way also giving evidence that the above detour over the dual domain is neither necessary nor simpler. In the present paper we focus on the geometrical aspects of the ADS paper and show that one of the key results of the ADS paper can be reformulated as the construction of a rather nontrivial class of supersets of the fundamental cone, where these supersets are convex cones that are generated by vectors that are derived from computation trees and minimal valid deviations therein. As we will discuss, the main ingredient that allows the verification of this superset construction is a certain class of backtrackless random walks on the code's normal factor graph. Moreover, formulating our results in terms of normal factor graphs will facilitate the generalization of the geometrical results of the ADS paper to setups with non-uniform node degrees, with other types of constraint function nodes, and with no restrictions on the girth. We conclude the paper by showing connections between the entropy rates of the above-mentioned random walks and the Bethe entropy function of the normal factor graph that these random walks are defined on.
Linear programming (LP) 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 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 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-½ 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. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. 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 “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.
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.
We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length
A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.
We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help toward a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.
Low-density parity-check codes, a class of capacity-approaching linear codes, are particularly recognized for their efficient decoding scheme. The decoding scheme, known as the sum-product, is an iterative algorithm consisting of passing messages between variable and check nodes of the factor graph. The sum-product algorithm is fully parallelizable, owing to the fact that all messages can be update concurrently. However, since it requires extensive number of highly interconnected wires, the fully-parallel implementation of the sum-product on chips is exceedingly challenging. Stochastic decoding algorithms, which exchange binary messages, are of great interest for mitigating this challenge and have been the focus of extensive research over the past decade. They significantly reduce the required wiring and computational complexity of the message-passing algorithm. Even though stochastic decoders have been shown extremely effective in practice, the theoretical aspect and understanding of such algorithms remains limited at large. Our main objective in this paper is to address this issue. We first propose a novel algorithm referred to as the Markov based stochastic decoding. Then, we provide concrete quantitative guarantees on its performance for tree-structured as well as general factor graphs. More specifically, we provide upper-bounds on the first and second moments of the error, illustrating that the proposed algorithm is an asymptotically consistent estimate of the sum-product algorithm. We also validate our theoretical predictions with experimental results, showing we achieve comparable performance to other practical stochastic decoders.