Threshold saturation of spatially coupled sparse superposition codes for all memoryless channels

We recently proved threshold saturation for spatially coupled sparse superposition codes on the additive white Gaussian noise channel [1]. Here we generalize our analysis to a much broader setting. We show for any memoryless channel that spatial coupling allows generalized approximate message-passing (GAMP) decoding to reach the potential (or Bayes optimal) threshold of the code ensemble. Moreover in the large input alphabet size limit: i) the GAMP algorithmic threshold of the underlying (or uncoupled) code ensemble is simply expressed as a Fisher information; ii) the potential threshold tends to Shannon's capacity. Although we focus on coding for sake of coherence with our previous results, the framework and methods are very general and hold for a wide class of generalized estimation problems with random linear mixing.

• Publication year

  2016

• Venue

  Information Theory Workshop

• Publication date

  2016-03-15

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/ITW.2016.7606799arXiv 1603.04591
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Proof of threshold saturation for spatially coupled sparse superposition codes

  2016cited by this paper
• Approximate Message-Passing Decoder and Capacity Achieving Sparse Superposition Codes

  2015cited by this paper
• Capacity-achieving Sparse Regression Codes via approximate message passing decoding

  2015cited by this paper
• Fisher Information Properties

  2015cited by this paper
• Replica analysis and approximate message passing decoder for superposition codes

  2014cited by this paper
• Properties of spatial coupling in compressed sensing

  2014cited by this paper
• How to achieve the capacity of asymmetric channels

  2014cited by this paper
• Fast Sparse Superposition Codes Have Near Exponential Error Probability for $R<{\cal C}$

  2014cited by this paper
• A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions

  2013cited by this paper
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

  2013cited by this paper
• Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels

  2013cited by this paper
• A simple proof of threshold saturation for coupled scalar recursions

  2012cited by this paper
• High-rate sparse superposition codes with iteratively optimal estimates

  2012cited by this paper
• Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

  2012cited by this paper
• Toward fast reliable communication at rates near capacity with Gaussian noise

  2010cited by this paper
• The dynamics of message passing on dense graphs, with applications to compressed sensing

  2010cited by this paper
• Generalized approximate message passing for estimation with random linear mixing

  2010cited by this paper

• Sparse Regression Codes for Non-Coherent SIMO Channels

  2024cites this paper
• Sparse superposition codes with rotational invariant coding matrices for memoryless channels

  2022cites this paper
• Sparse superposition codes under VAMP decoding with generic rotational invariant coding matrices

  2022influential citation
• Near-Optimal Coding for Massive Multiple Access

  2021influential citation
• Compressed Coding, AMP-Based Decoding, and Analog Spatial Coupling

  2020influential citation
• Sparse Regression Codes

  2019cites this paper
• Bethe States of Random Factor Graphs

  2019cites this paper
• SPARCs for Unsourced Random Access

  2019cites this paper
• Spatially Coupled Sparse Regression Codes: Design and State Evolution Analysis

  2018cites this paper
• Capacity-achieving sparse regression codes via spatial coupling

  2018cites this paper
• A Compressed Sensing Approach for Distribution Matching

  2018cites this paper
• High-Dimensional Inference on Dense Graphs with Applications to Coding Theory and Machine Learning

  2018influential citation
• The Mutual information of LDGM codes

  2017cites this paper
• Universal Sparse Superposition Codes With Spatial Coupling and GAMP Decoding

  2017cites this paper
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation

  2017cites this paper
• Generalized approximate message-passing decoder for universal sparse superposition codes

  2017cites this paper
• The Error Probability of Sparse Superposition Codes With Approximate Message Passing Decoding

  2017cites this paper
• Study of the Sparse Superposition Codes and the Generalized Approximate Message Passing Decoder for the Communication over Binary Symmetric and Z Channels

  2017cites this paper
• Clipping Can Improve the Performance of Spatially Coupled Sparse Superposition Codes

  2017cites this paper
• Optimal errors and phase transitions in high-dimensional generalized linear models

  2017cites this paper
• Bethe States of Random Factor Graphs

  2017cites this paper
• Phase Transitions, Optimal Errors and Optimality of Message-Passing in Generalized Linear Models

  2017cites this paper
• Statistical Mechanics of MAP Estimation: General Replica Ansatz

  2016cites this paper
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

  2016influential citation
• The mutual information in random linear estimation

  2016cites this paper
• Approximate Message-Passing Decoder and Capacity Achieving Sparse Superposition Codes

  2015cites this paper