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+ Klog nloglog n)$ and $mathcal{O}(K^{3}+K^{2}log n+Klog nlog log n)$ per iteration, respectively. When $Kll 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.