Approximate message-passing decoder and capacity-achieving sparse superposition codes

Abstract

We study the approximate message-passing decoder for sparse superposition coding on the additive white Gaussian noise channel and extend our preliminary work [1]. We use heuristic statistical-physics-based tools such as the cavity and the replica methods for the statistical analysis of the scheme. While superposition codes asymptotically reach the Shannon capacity, we show that our iterative decoder is limited by a phase transition similar to the one that happens in Low Density Parity check codes. We consider two solutions to this problem, that both allow to reach the Shannon capacity: i) a power allocation strategy and ii) the use of spatial coupling, a novelty for these codes that appears to be promising. We present in particular simulations suggesting that spatial coupling is more robust and allows for better reconstruction at finite code lengths. Finally, we show empirically that the use of a fast Hadamard-based operator allows for an efficient reconstruction, both in terms of computational time and memory, and the ability to deal with very large messages.

40 pages, 18 figures

References in corpus (8)

• Statistical physics of inference: Thresholds and algorithms
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• The Mutual Information in Random Linear Estimation
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Generalized Approximate Message-Passing Decoder for Universal Sparse Superposition Codes
• Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction
• Statistical physics and approximate message-passing algorithms for sparse linear estimation problems in signal processing and coding theory

Cited by in corpus (34)

• Statistical physics of inference: Thresholds and algorithms
• Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access with a Massive MIMO Receiver
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• SPARCs for Unsourced Random Access
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• The Mutual Information in Random Linear Estimation
• Fundamental limits of many-user MAC with finite payloads and fading
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Bayesian Optimal Data Detector for mmWave OFDM System with Low-Resolution ADC
• Finite Sample Analysis of Approximate Message Passing Algorithms
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices
• Sparse Regression Codes
• Techniques for improving the finite length performance of sparse superposition codes
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• Performance Analysis of Approximate Message Passing for Distributed Compressed Sensing
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• Performance Limits for Noisy Multi-Measurement Vector Problems
• Performance Analysis of Joint Active User Detection and Channel Estimation for Massive Connectivity
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
• Performance Limits with Additive Error Metrics in Noisy Multi-Measurement Vector Problem
• Near-Optimal Coding for Many-user Multiple Access Channels
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Capacity Optimality of AMP in Coded Systems
• Soft Interference Cancellation for Random Coding in Massive Gaussian Multiple-Access
• Statistical Physics and Information Theory Perspectives on Linear Inverse Problems
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes
• Orthogonal Sparse Superposition Codes for Ultra-Reliable Low-Latency Communications
• Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes
• Compressed Coding, AMP Based Decoding and Analog Spatial Coupling
• An Improved Analysis of Least Squares Superposition Codes with Bernoulli Dictionary
• Study of the Sparse Superposition Codes and the Generalized Approximate Message Passing Decoder for the Communication over Binary Symmetric and Z Channels