Least squares superposition codes of moderate dictionary size, reliable at rates up to capacity

Sparse superposition codes are developed for the additive white Gaussian noise channel with average codeword power constraint. Codewords are linear combinations of subsets of vectors, with the possible messages indexed by the choice of subset. Decoding is by least squares, tailored to the assumed form of linear combination. Communication is shown to be reliable with error probability exponentially small for all rates up to 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.5513318arXiv 1006.3780
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

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

  2012cited by this paper
• Capacity Achieving Random Sparse Linear Codes

  2011cited by this paper
• Polar coding schemes for the AWGN channel

  2011cited by this paper
• Adaptive Forward-Backward Greedy Algorithm for Learning Sparse Representations

  2011cited by this paper
• Coding for noisy channels

  2011cited by this paper
• Multiuser detection in asynchronous on-off random access channels using lasso

  2010cited by this paper
• Sparse superposition codes for Gaussian vector quantization

  2010cited by this paper
• Channel Coding Rate in the Finite Blocklength Regime

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

  2010cited by this paper
• Exponential Bounds Implying Construction of Compressed Sensing Matrices, Error-Correcting Codes, and Neighborly Polytopes by Random Sampling

  2010cited by this paper
• False Discovery Rate Control With Groups

  2010cited by this paper
• Sparse Superposition Codes: Fast and Reliable at Rates Approaching Capacity with Gaussian Noise

  2010cited by this paper
• Sparse regularization in MRI iterative reconstruction using GPUs

  2010cited by this paper
• On-Off Random Access Channels: A Compressed Sensing Framework

  2009cited by this paper
• On the Consistency of Feature Selection using Greedy Least Squares Regression

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

  2009cited by this paper
• Concatenated codes

  2009cited by this paper
• Sampling bounds for sparse support recovery in the presence of noise

  2008cited by this paper
• Noisy compressive sampling limits in linear and sublinear regimes

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

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

  2008cited by this paper
• Iterative Thresholding for Sparse Approximations

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

  2008cited by this paper
• On the conditioning of random subdictionaries

  2008cited by this paper
• Norms of Random Submatrices and Sparse Approximation

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

  2008cited by this paper
• Risk of penalized least squares, greedy selection andl 1-penalization for flexible function libraries

  2008cited by this paper
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

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

  2008cited by this paper
• Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

  2008cited by this paper
• Shannon-Theoretic Limits on Noisy Compressive Sampling

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

  2007cited by this paper
• Information theoretic bounds to sensing capacity of sensor networks under fixed SNR

  2007cited by this paper
• On Model Selection Consistency of Lasso

  2006cited by this paper
• Denoising by Sparse Approximation: Error Bounds Based on Rate-Distortion Theory

  2006cited by this paper
• A Mathematical Theory of Communication

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

  2006cited by this paper
• For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution

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

  2006cited by this paper
• For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution

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

  2006cited by this paper
• Joint Permutor Analysis and Design for Multiple Turbo Codes

  2006cited by this paper
• Channel coding: The road to channel capacity

  2006cited by this paper
• Annals of Statistics

  2006cited by this paper
• Decoding by linear programming

  2005cited by this paper
• Applications of sparse approximation in communications

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• On sparse representations in arbitrary redundant bases

  2004cited by this paper
• Error Control Coding

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

  2004cited by this paper
• Greed is good: algorithmic results for sparse approximation

  2004cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004cited by this paper
• Recovery of exact sparse representations in the presence of noise

  2004cited by this paper
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

  2003cited by this paper
• Áååë Ì Blockinòò Blockin Blockinð Êêôóöø ¾¼¼¾¹¿¾ Ùùù×ø ¾¼¼¾

  2002cited by this paper
• Uncertainty principles and ideal atomic decomposition

  2001cited by this paper
• The capacity of low-density parity-check codes under message-passing decoding

  2001cited by this paper
• Efficient erasure correcting codes

  2001cited by this paper
• Design of capacity-approaching irregular low-density parity-check codes

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

  1998cited by this paper
• Turbo Decoding as an Instance of Pearl's "Belief Propagation" Algorithm

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

  1998influential reference
• A rate-splitting approach to the Gaussian multiple-access channel

  1996cited by this paper
• A distance spectrum interpretation of turbo codes

  1996cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Controlling the false discovery rate: a practical and powerful approach to multiple testing

  1995cited by this paper
• Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition

  1993cited by this paper
• Matching pursuits with time-frequency dictionaries

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

  1993cited by this paper
• Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1

  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
• Condition numbers of random matrices

  1991cited by this paper
• Sphere Packings, Lattices and Groups

  1987cited by this paper
• Error control coding : fundamentals and applications

  1983cited by this paper
• The Theory of Error-Correcting Codes

  1977cited by this paper
• Information Theory and Reliable Communication

  1969cited by this paper
• Probability inequalities for sum of bounded random variables

  1963cited by this paper
• Broadcast Channels

  year unknowninfluential reference
• © Institute of Mathematical Statistics, 2009 NEAR-IDEAL MODEL SELECTION BY ℓ1 MINIMIZATION

  year unknowncited by this paper
• Theory of Error-correcting Codes

  year unknowncited by this paper

• Block Sparse Vector Codes for Ultra-Reliable and Low-Latency Short-Packet Transmission

  2025cites this paper
• Sparse Regression Codes for Covert Communication over Multiple Access Channels

  2025cites this paper
• Generalized Index Redefinition-Based Sparse Mapping for Sparse Vector Transmission

  2025cites this paper
• Sparse Regression LDPC Codes for the Block-Fading Non-Coherent SIMO Channel

  2025influential citation
• Random Multiplexing

  2025cites this paper
• Sparse Regression Codes for Secret Key Agreement: Achieving Strong Secrecy and Near-Optimal Rates for Gaussian Sources

  2025cites this paper
• Sparse Regression Codes exploit Multi-User Diversity without CSI

  2025cites this paper
• Sparse Superposition Codes with Binomial Dictionary are Capacity-Achieving with Maximum Likelihood Decoding

  2025influential citation
• Sparse Superposition Codes With Short Lengths Based on Zero Correlation Zone Sequence Sets

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

  2025cites this paper
• Multi-User SR-LDPC Codes via Coded Demixing with Applications to Cell-Free Systems

  2024cites this paper
• Fast Channel Simulation via Error-Correcting Codes

  2024cites this paper
• The Error Probability of Spatially Coupled Sparse Regression Codes Over Memoryless Channels

  2024influential citation
• Generalization and Construction of Single-Section Sparse Regression Codes

  2024cites this paper
• Multi-User SR-LDPC Codes

  2024cites this paper
• Unsourced Multiple Access: A Coding Paradigm for Massive Random Access

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

  2024cites this paper
• The Entropic Doubling Constant and Robustness of Gaussian Codebooks for Additive-Noise Channels

  2024cites this paper
• Coded Many-User Multiple Access via Approximate Message Passing

  2024cites this paper
• Generalized Sparse Regression Codes for Short Block Lengths

  2023cites this paper
• Sparse Regression LDPC Codes

  2023influential citation
• Coded Orthogonal Modulation for the Multi-Antenna MAC

  2023cites this paper
• Power Allocation for the Base Matrix of Spatially Coupled Sparse Regression Codes

  2023cites this paper
• Improved Finite-Length Bound of Gaussian Unsourced Multiple Access

  2023cites this paper
• Low-Rate and Short-Block-Length Random Permutation-Coded Modulations Achieve Finite-Length Bounds

  2023cites this paper
• Capacity-Achieving Sparse Regression Codes via Vector Approximate Message Passing

  2023cites this paper
• On Sparse Regression LDPC Codes

  2023cites this paper
• On Capacity Achieving of Sparse Regression Code with the Row-Orthogonal Matrix

  2022cites this paper
• On the Convergence of Orthogonal/Vector AMP: Long-Memory Message-Passing Strategy

  2022cites this paper
• Long-Memory Message-Passing for Spatially Coupled Systems

  2022cites this paper
• Block Orthogonal Sparse Superposition Codes for Ultra-Reliable Low-Latency Communications

  2022cites this paper
• MMSE-A-MAP Decoder for Block Orthogonal Sparse Superposition Codes in Fading Channels

  2022cites this paper
• Constant Weight Codes With Gabor Dictionaries and Bayesian Decoding for Massive Random Access

  2022cites this paper
• Improved Bounds for the Many-User MAC

  2022cites this paper
• Orthogonal Approximate Message-Passing for Spatially Coupled Systems

  2022cites this paper
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition

  2022cites this paper
• Sparse Regression Codes for MIMO Detection

  2022cites this paper
• On the Convergence of Orthogonal/Vector AMP: Long-Memory Message-Passing Strategy

  2021cites this paper
• Secure Coding for the Gaussian Wiretap Channel with Sparse Regression Codes

  2021influential citation
• Block Orthogonal Sparse Superposition Codes

  2021cites this paper
• Near-Optimal Coding for Many-User Multiple Access Channels

  2021cites this paper
• On the Finite Length Performance of Sparse Regression Codes with Peak-Power Limitation

  2021cites this paper
• Joint Device Detection, Channel Estimation, and Data Decoding With Collision Resolution for MIMO Massive Unsourced Random Access

  2021cites this paper
• Irregularly Clipped Sparse Regression Codes

  2021cites this paper
• Unsourced Random Access With Coded Compressed Sensing: Integrating AMP and Belief Propagation

  2020cites this paper
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity

  2020cites this paper
• Massive Unsourced Random Access Based on Uncoupled Compressive Sensing: Another Blessing of Massive MIMO

  2020cites this paper
• Compressed Coding, AMP-Based Decoding, and Analog Spatial Coupling

  2020cites this paper
• Capacity-Achieving Spatially Coupled Sparse Superposition Codes With AMP Decoding

  2020influential citation
• Rigorous State Evolution Analysis for Approximate Message Passing With Side Information

  2020cites this paper
• Modulated Sparse Superposition Codes for the Complex AWGN Channel

  2020influential citation
• Grant-Free Access for IoT in Beyond-5G Systems: The Potential of Receiver Diversity

  2020cites this paper
• Soft Interference Cancellation for Random Coding in Massive Gaussian Multiple-Access †

  2020cites this paper
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models

  2020cites this paper
• Orthogonal Sparse Superposition Codes

  2020cites this paper
• Greedy Algorithms for Sparse and Positive Signal Recovery Based on Bit-Wise MAP Detection

  2020cites this paper
• Modulated Sparse Regression Codes

  2020cites this paper
• Expectation Propagation Decoding for Sparse Superposition Codes

  2020cites this paper
• Massive MIMO is Very Useful for Pilot-Free Uplink Communications

  2020cites this paper
• Compressed-Coding and Analog Spatial-Coupling using AMP based Decoding

  2020cites this paper
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes

  2020cites this paper
• Fundamental Limits of Many-User MAC With Finite Payloads and Fading

  2019cites this paper
• SPARCs for Unsourced Random Access

  2019cites this paper
• Spatially Coupled Sparse Regression Codes with Sliding Window AMP Decoding

  2019cites this paper
• Sparse Regression Codes

  2019influential citation
• Spatially Coupled Sparse Regression Codes: Design and State Evolution Analysis

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

  2018influential citation
• Scalable Massive Random Access in C- RAN with Fronthaul Limitations

  2018cites this paper
• A novel physical layer scheme based on superposition codes

  2017influential citation
• The error exponent of sparse regression codes with AMP decoding

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

  2017influential citation
• Techniques for Improving the Finite Length Performance of Sparse Superposition Codes

  2017influential citation
• Fast Randomized Algorithms for Convex Optimization and Statistical Estimation

  2016cites this paper
• A capacity-achieving coding scheme for the AWGN channel with polynomial encoding and decoding complexity

  2016influential citation
• An improved upper bound on block error probability of least squares superposition codes with unbiased Bernoulli dictionary

  2016influential citation
• Iterative Algorithms for Inference and Optimization, with Applications in Communications and Compressed Sensing

  2016influential citation
• Polar codes and polar lattices for efficient communication and source quantization

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

  2016cites this paper
• A Novel Channel Coding Scheme for RFID Generation-2 Systems

  2016cites this paper
• ISIT 2016 Tutorial: Sparse Regression Codes

  2016cites this paper
• Improving the Performance of Nested Lattice Codes Using Concatenation

  2016cites this paper
• Capacity-Achieving Sparse Superposition Codes via Approximate Message Passing Decoding

  2015influential citation
• Achieving Secrecy Capacity of the Gaussian Wiretap Channel With Polar Lattices

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

  2015cites this paper
• The Gaussian rate-distortion function of sparse regression codes with optimal encoding

  2014cites this paper
• Semantically-Secure Coding Scheme Achieving the Capacity of a Gaussian Wiretap Channel

  2014cites this paper
• Explicit capacity-achieving coding scheme for the Gaussian wiretap channel

  2014cites this paper
• The Rate-Distortion Function and Excess-Distortion Exponent of Sparse Regression Codes With Optimal Encoding

  2014cites this paper
• The Rate-Distortion Function and Error Exponent of Sparse Regression Codes with Optimal Encoding

  2014cites this paper
• Randomized sketches of convex programs with sharp guarantees

  2014cites this paper
• Lossy compression via sparse linear regression: Computationally efficient encoding and decoding

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

  2013cites this paper
• State–of–the–art report on nonlinear representation of sources and channels

  2013cites this paper
• Complexity and rate-distortion tradeoff via successive refinement

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

  2012cites this paper
• Information Theoretic Limit of Single-Frame Super-Resolution

  2012influential citation
• Gaussian rate-distortion via sparse linear regression over compact dictionaries

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

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

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

  2012cites this paper