Approximate Support Recovery using Codes for Unsourced Multiple Access Academic Article uri icon

abstract

  • We consider the approximate support recovery (ASR) task of inferring the support of a $K$-sparse vector ${\bf x} in mathbb{R}^n$ from $m$ noisy measurements. We examine the case where $n$ is large, which precludes the application of standard compressed sensing solvers, thereby necessitating solutions with lower complexity. We design a scheme for ASR by leveraging techniques developed for unsourced multiple access. We present two decoding algorithms with computational complexities $mathcal{O}(K^2 log n+K log n log log n)$ and $mathcal{O}(K^3 +K^2 log n+ K log n log log n)$ per iteration, respectively. When $K ll n$, this is much lower than the complexity of approximate message passing with a minimum mean squared error denoiser% (AMP-MMSE) ,which requires $mathcal{O}(mn)$ operations per iteration. This gain comes at a slight performance cost. Our findings suggest that notions from multiple access %such as spreading, matched filter receivers and codes can play an important role in the design of measurement schemes for ASR.

author list (cited authors)

  • Gkagkos, M., Pradhan, A. K., Amalladinne, V., Narayanan, K., Chamberland, J., & Georghiades, C. N.

publication date

  • January 1, 2016 11:11 AM

publisher