Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes

Abstract

We study the Gaussian multiple access channel with random user activity, in the regime where the number of users is proportional to the code length. The receiver may know some statistics about the number of active users, but does not know the exact number nor the identities of the active users. We derive two achievability bounds on the probabilities of missed detection, false alarm, and active user error, and propose an efficient CDMA-type scheme whose performance can be compared against these bounds. The first bound is a finite-length result based on Gaussian random codebooks and maximum-likelihood decoding. The second is an asymptotic bound, established using spatially coupled Gaussian codebooks and approximate message passing (AMP) decoding. These bounds can be used to compute an achievable tradeoff between the active user density and energy-per-bit, for a fixed user payload and target error rate. The efficient CDMA scheme uses a spatially coupled signature matrix and AMP decoding, and we give rigorous asymptotic guarantees on its error performance. Our analysis provides the first state evolution result for spatially coupled AMP with matrix-valued iterates, which may be of independent interest. Numerical experiments demonstrate the promising error performance of the CDMA scheme for both small and large user payloads, when compared with the two achievability bounds.

62 pages, 15 figures, to appear in the IEEE Transactions on Information Theory

References in corpus (17)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Massive Connectivity with Massive MIMO-Part I: Device Activity Detection and Channel Estimation
• Sparse Activity Detection for Massive Connectivity
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Fundamental limits of many-user MAC with finite payloads and fading
• A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Sparse Regression Codes
• Gaussian Multiple and Random Access in the Finite Blocklength Regime
• Random Access Channel Coding in the Finite Blocklength Regime
• Near-Optimal Coding for Many-user Multiple Access Channels
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing