The Error Probability of Sparse Superposition Codes With Approximate Message Passing Decoding

DOI10.1109/TIT.2018.2882177MaRDI QIDQ5224000zbMATH OpenFDO

Authors Cynthia Rush, Ramji Venkataramanan

Publication date 19 July 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.06866

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Source coding (94A29) Error probability in coding theory (94B70)

Abstract: Sparse superposition codes, or sparse regression codes (SPARCs), are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviations bound on the probability of AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in $n/(logn{)}^{2T}$, where $T$, the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity.

Cited in

(2)

• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

This page was built for publication: The Error Probability of Sparse Superposition Codes With Approximate Message Passing Decoding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224000)