Sparse Regression Codes

Abstract

Developing computationally-efficient codes that approach the Shannon-theoretic limits for communication and compression has long been one of the major goals of information and coding theory. There have been significant advances towards this goal in the last couple of decades, with the emergence of turbo codes, sparse-graph codes, and polar codes. These codes are designed primarily for discrete-alphabet channels and sources. For Gaussian channels and sources, where the alphabet is inherently continuous, Sparse Superposition Codes or Sparse Regression Codes (SPARCs) are a promising class of codes for achieving the Shannon limits. This survey provides a unified and comprehensive overview of sparse regression codes, covering theory, algorithms, and practical implementation aspects. The first part of the monograph focuses on SPARCs for AWGN channel coding, and the second part on SPARCs for lossy compression (with squared error distortion criterion). In the third part, SPARCs are used to construct codes for Gaussian multi-terminal channel and source coding models such as broadcast channels, multiple-access channels, and source and channel coding with side information. The survey concludes with a discussion of open problems and directions for future work.

Published in Foundations and Trends in Communications and Information Theory, 2019

References in corpus (15)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Message Passing Algorithms for Compressed Sensing
• Spatially Coupled LDPC Codes Constructed from Protographs
• SPARCs for Unsourced Random Access
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Techniques for improving the finite length performance of sparse superposition codes
• Rate-Distortion via Markov Chain Monte Carlo
• Construction of Capacity-Achieving Lattice Codes: Polar Lattices
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• The Rate-Distortion Function and Excess-Distortion Exponent of Sparse Regression Codes with Optimal Encoding

Cited by in corpus (7)

• Fundamental limits of many-user MAC with finite payloads and fading
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes