Toward fast reliable communication at rates near capacity with Gaussian noise

For the additive Gaussian noise channel with average codeword power constraint, sparse superposition codes and adaptive successive decoding is developed. Codewords are linear combinations of subsets of vectors, with the message indexed by the choice of subset. A feasible decoding algorithm is presented. Communication is reliable with error probability exponentially small for all rates below the Shannon capacity.

• Publication year

  2010

• Venue

  2010 IEEE International Symposium on Information Theory

• Publication date

  2010-06-13

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/ISIT.2010.5513330arXiv 1006.3870
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Channel Coding Rate in the Finite Blocklength Regime

  2010cited by this paper
• Sharp upper bound on error probability of exact sparsity recovery

  2009cited by this paper
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso)

  2009cited by this paper
• Support recovery in compressed sensing: An estimation theoretic approach

  2009cited by this paper
• Concatenated codes

  2009cited by this paper
• Near-ideal model selection by ℓ1 minimization

  2008cited by this paper
• On the rate of channel polarization

  2008cited by this paper
• Approximation and learning by greedy algorithms

  2008cited by this paper
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery

  2008cited by this paper
• Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels

  2008cited by this paper
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

  2007cited by this paper
• Stable recovery of sparse overcomplete representations in the presence of noise

  2006cited by this paper
• Just relax: convex programming methods for identifying sparse signals in noise

  2006cited by this paper
• Asymptotically Optimal Multiple-Access Communication Via Distributed Rate Splitting

  2006cited by this paper
• A Mathematical Theory of Communication

  2006cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Low-Density Parity-Check Codes

  2004cited by this paper
• Efficient erasure correcting codes

  2001cited by this paper
• Modulation and Coding for Linear Gaussian Channels

  1998cited by this paper
• Improved low-density parity-check codes using irregular graphs and belief propagation

  1998cited by this paper
• A rate-splitting approach to the Gaussian multiple-access channel

  1996cited by this paper
• Asymptotic distribution of the errors in scalar and vector quantizers

  1996cited by this paper
• Universal approximation bounds for superpositions of a sigmoidal function

  1993cited by this paper
• A Simple Lemma on Greedy Approximation in Hilbert Space and Convergence Rates for Projection Pursuit Regression and Neural Network Training

  1992cited by this paper
• Information Theory and Reliable Communication

  1969cited by this paper
• Theory of Error-correcting Codes

  year unknowncited by this paper
• © Institute of Mathematical Statistics, 2009 NEAR-IDEAL MODEL SELECTION BY ℓ1 MINIMIZATION

  year unknowncited by this paper
• Broadcast Channels

  year unknowncited by this paper

• Sparse Superposition Codes with Binomial Dictionary are Capacity-Achieving with Maximum Likelihood Decoding

  2025cites this paper
• Capacity-Achieving Sparse Superposition Codes with Spatially Coupled VAMP Decoder

  2025cites this paper
• Generalization and Construction of Single-Section Sparse Regression Codes

  2024cites this paper
• Sparse Regression Codes for Non-Coherent SIMO Channels

  2024cites this paper
• Exploring interpersonal communication strategies in the healthcare system: insights from Barangay health workers (BHW) in the Philippines

  2023cites this paper
• Efficient Decoding of Compositional Structure in Holistic Representations

  2023influential citation
• 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
• Strong Replica Symmetry in High-Dimensional Optimal Bayesian Inference

  2020cites this paper
• Learning to compress and search visual data in large-scale systems

  2019cites this paper
• Quasi-Orthogonal Sparse Superposition Codes

  2019cites this paper
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices

  2018cites this paper
• Sparse Superposition Codes for the Gaussian Channel

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

  2018cites this paper
• An improved analysis of least squares superposition codes with bernoulli dictionary

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

  2018cites this paper
• Compressed FEC Codes With Spatial-Coupling

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

  2017cites this paper
• Coupling Data Transmission

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

  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
• I-MMSE relations in random linear estimation and a sub-extensive interpolation method

  2017cites this paper
• Implementation of Sparse Superposition Codes

  2017cites this paper
• An improved upper bound on block error probability of least squares superposition codes with unbiased Bernoulli dictionary

  2016cites this paper
• The mutual information in random linear estimation

  2016cites this paper
• Proof of threshold saturation for spatially coupled sparse superposition codes

  2016cites this paper
• Threshold saturation of spatially coupled sparse superposition codes for all memoryless channels

  2016cites this paper
• Sparse superposition codes: A practical approach

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

  2015influential citation
• Coding and modulation techniques for high spectral efficiency transmission in 5G and satcom

  2015cites this paper
• Pseudo-random Gaussian distribution through optimised LFSR permutations

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

  2014influential citation
• APPROXIMATE ITERATIVE BAYES OPTIMAL ESTIMATES FOR HIGH-RATE SPARSE SUPERPOSITION CODES

  2013cites this paper
• Least Squares Superposition Codes With Bernoulli Dictionary are Still Reliable at Rates up to Capacity

  2013influential citation
• Lossy compression via sparse linear regression: Computationally efficient encoding and decoding

  2013cites this paper
• Sparse Regression codes: Recent results and future directions

  2013cites this paper
• Coupling Data Transmission for Multiple-Access Communications

  2012cites this paper
• Gaussian rate-distortion via sparse linear regression over compact dictionaries

  2012cites this paper
• Least Squares Superposition Codes of Moderate Dictionary Size Are Reliable at Rates up to Capacity

  2012cites this paper
• Coupling Data Transmission for Capacity-Achieving Multiple-Access Communications

  2012cites this paper
• Fast Sparse Superposition Codes have Exponentially Small Error Probability for R < C

  2012cites this paper
• Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding

  2012cites this paper
• Lossy Compression via Sparse Linear Regression: Performance Under Minimum-Distance Encoding

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

  2012cites this paper
• Sparse regression codes for multi-terminal source and channel coding

  2012cites this paper
• Low-complexity near-optimal codes for Gaussian relay networks

  2011cites this paper
• Analysis of fast sparse superposition codes

  2011cites this paper
• Sparse Superposition Codes: Fast and Reliable at Rates Approaching Capacity with Gaussian Noise

  2010cites this paper
• Least squares superposition codes of moderate dictionary size, reliable at rates up to capacity

  2010cites this paper