# Approximate Support Recovery using Codes for Unsourced Multiple Access Academic Article

•
• Overview
•
• Research
•
• Identity
•
•
• View All
•

### 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.