Skip to main content

Message-Passing Algorithms and Improved LP Decoding

Author(s): Arora, Sanjeev; Daskalakis, Constantinos; Steurer, David

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorArora, Sanjeev-
dc.contributor.authorDaskalakis, Constantinos-
dc.contributor.authorSteurer, David-
dc.identifier.citationArora, Sanjeev, Constantinos Daskalakis, and David Steurer. "Message-Passing Algorithms and Improved LP Decoding." IEEE Transactions on Information Theory 58, no. 12 (2012): pp. 7260-7271. doi:10.1109/TIT.2012.2208584en_US
dc.description.abstractLinear 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.en_US
dc.format.extent7260 - 7271en_US
dc.relation.ispartofIEEE Transactions on Information Theoren_US
dc.rightsAuthor's manuscripten_US
dc.titleMessage-Passing Algorithms and Improved LP Decodingen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
MessagePassingAlgorithms.pdf367.91 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.