A sparsity detection framework for on-off random access channels

Alyson K. Fletcher, Sundeep Rangan, Vivek K. Goyal

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper considers a simple on-off random multiple access channel, where n users communicate simultaneously to a single receiver over m degrees of freedom. Each user transmits with probability λ, where typically λn < m ≪ n, and the receiver must detect which users transmitted. We show that when the codebook has i.i.d. Gaussian entries, detecting which users transmitted is mathematically equivalent to a certain sparsity detection problem considered in compressed sensing. Using recent sparsity results, we derive upper and lower bounds on the capacities of these channels. We show that common sparsity detection algorithms, such as lasso and orthogonal matching pursuit (OMP), can be used as tractable multiuser detection schemes and have significantly better performance than single-user detection. These methods do achieve some near-far resistance but-at high signal-to-noise ratios (SNRs)-may achieve capacities far below optimal maximum likelihood detection. We then present a new algorithm, called sequential OMP, that illustrates that iterative detection combined with power ordering or power shaping can significantly improve the high SNR performance. Sequential OMP is analogous to successive interference cancellation in the classic multiple access channel. Our results thereby provide insight into the roles of power control and multiuser detection on random-access signaling.

Original languageEnglish (US)
Title of host publicationWavelets XIII
StatePublished - 2009
EventWavelets XIII - San Diego, CA, United States
Duration: Aug 2 2009Aug 4 2009

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X


OtherWavelets XIII
Country/TerritoryUnited States
CitySan Diego, CA


  • Compressed sensing
  • Convex optimization
  • Lasso
  • Maximum likelihood estimation
  • Multiple access channel
  • Multiuser detection
  • Orthogonalmatching pursuit
  • Power control
  • Random matrices
  • Single-user detection
  • Sparsity
  • Thresholding

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'A sparsity detection framework for on-off random access channels'. Together they form a unique fingerprint.

Cite this