Replica Analysis and Approximate Message Passing Decoder for Superposition Codes

Abstract

Superposition codes are efficient for the Additive White Gaussian Noise channel. We provide here a replica analysis of the performances of these codes for large signals. We also consider a Bayesian Approximate Message Passing decoder based on a belief-propagation approach, and discuss its performance using the density evolution technic. Our main findings are 1) for the sizes we can access, the message-passing decoder outperforms other decoders studied in the literature 2) its performance is limited by a sharp phase transition and 3) while these codes reach capacity as $B$ (a crucial parameter in the code) increases, the performance of the message passing decoder worsen as the phase transition goes to lower rates.

5 pages, 5 figures, To be presented at the 2014 IEEE International Symposium on Information Theory

References in corpus (6)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

Cited by in corpus (15)

• Statistical physics of inference: Thresholds and algorithms
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• The Mutual Information in Random Linear Estimation
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Finite Sample Analysis of Approximate Message Passing Algorithms
• Sparse Regression Codes
• Techniques for improving the finite length performance of sparse superposition codes
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• Generalized Approximate Message-Passing Decoder for Universal Sparse Superposition Codes
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes
• Rigorous State Evolution Analysis for Approximate Message Passing with Side Information
• An Improved Analysis of Least Squares Superposition Codes with Bernoulli Dictionary