Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding

Abstract

Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the AWGN channel at rates approaching the channel capacity. The codebook is defined in terms of a Gaussian design matrix, and codewords are sparse linear combinations of columns of the matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes, whose decoding complexity scales linearly with the size of the design matrix. The performance of the decoder is rigorously analyzed and it is shown to asymptotically achieve the AWGN capacity with an appropriate power allocation. Simulation results are provided to demonstrate the performance of the decoder at finite blocklengths. We introduce a power allocation scheme to improve the empirical performance, and demonstrate how the decoding complexity can be significantly reduced by using Hadamard design matrices.

25 pages, 4 figures. IEEE Transactions on Information Theory

References in corpus (9)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Construction of Capacity-Achieving Lattice Codes: Polar Lattices

Cited by in corpus (30)

• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• SPARCs for Unsourced Random Access
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• The Mutual Information in Random Linear Estimation
• 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
• Techniques for improving the finite length performance of sparse superposition codes
• Sparse Regression Codes
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Approximate Message Passing Algorithm with Universal Denoising and Gaussian Mixture Learning
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
• Near-Optimal Coding for Many-user Multiple Access Channels
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Capacity Optimality of AMP in Coded Systems
• Soft Interference Cancellation for Random Coding in Massive Gaussian Multiple-Access
• An Overview of Multi-Processor Approximate Message Passing
• Orthogonal Sparse Superposition Codes for Ultra-Reliable Low-Latency Communications
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models
• Compressed Coding, AMP Based Decoding and Analog Spatial Coupling
• Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes
• Linear Operator Approximate Message Passing (OpAMP)
• Rigorous State Evolution Analysis for Approximate Message Passing with Side Information
• Deep Learning Based Near-Orthogonal Superposition Code for Short Message Transmission