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

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.