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 $\mathrm{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, which requires $\mathcal{O}(mn)$ operations per iteration. This gain comes at a slight performance cost. Our findings suggest that notions from multiple access can play an important role in the design of measurement schemes for ASR.