Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding

Abstract

Sparse superposition codes, also called sparse regression codes (SPARCs), are a class of codes for efficient communication over the AWGN channel at rates approaching the channel capacity. In a standard SPARC, codewords are sparse linear combinations of columns of an i.i.d. Gaussian design matrix, while in a spatially coupled SPARC the design matrix has a block-wise structure, where the variance of the Gaussian entries can be varied across blocks. A well-designed spatial coupling structure can significantly enhance the error performance of iterative decoding algorithms such as Approximate Message Passing (AMP). In this paper, we obtain a non-asymptotic bound on the probability of error of spatially coupled SPARCs with AMP decoding. Applying this bound to a simple band-diagonal design matrix, we prove that spatially coupled SPARCs with AMP decoding achieve the capacity of the AWGN channel. The bound also highlights how the decay of error probability depends on each design parameter of the spatially coupled SPARC. An attractive feature of AMP decoding is that its asymptotic mean squared error (MSE) can be predicted via a deterministic recursion called state evolution. Our result provides the first proof that the MSE concentrates on the state evolution prediction for spatially coupled designs. Combined with the state evolution prediction, this result implies that spatially coupled SPARCs with the proposed band-diagonal design are capacity-achieving. Using the proof technique used to establish the main result, we also obtain a concentration inequality for the MSE of AMP applied to compressed sensing with spatially coupled design matrices. Finally we provide numerical simulation results that demonstrate the finite length error performance of spatially coupled SPARCs. The performance is compared with coded modulation schemes that use LDPC codes from the DVB-S2 standard.

arXiv commentTo appear in IEEE Transactions on Information Theory. This version contains proofs of two technical lemmas that were omitted in the journal version

References in corpus (21)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
• Spatially Coupled LDPC Codes Constructed from Protographs
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
• A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Finite Sample Analysis of Approximate Message Passing Algorithms
• Performance Improvement of Iterative Multiuser Detection for Large Sparsely-Spread CDMA Systems by Spatial Coupling
• Sparse Regression Codes
• Techniques for improving the finite length performance of sparse superposition codes
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• A Phenomenological Study on Threshold Improvement via Spatial Coupling
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding

Cited by in corpus (7)

• Fundamental limits of many-user MAC with finite payloads and fading
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Near-Optimal Coding for Many-user Multiple Access Channels
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes
• Compressed Coding, AMP Based Decoding and Analog Spatial Coupling
• Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes