Approximate Support Recovery using Codes for Unsourced Multiple Access

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.

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

Gkagkos, Michail||Pradhan, Asit Kumar||Amalladinne, Vamsi||Narayanan, Krishna||Chamberland, Jean-Francois||Georghiades, Costas N

Overview