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

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/(\log n{)}^{2T}$, where $T$, the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity.

27 pages. IEEE Transactions on Information Theory

References in corpus (3)

• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Techniques for improving the finite length performance of sparse superposition codes

Cited by in corpus (7)

• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Fundamental limits of many-user MAC with finite payloads and fading
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Sparse Regression Codes
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• Near-Optimal Coding for Many-user Multiple Access Channels
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes