Approximate Support Recovery using Codes for Unsourced Multiple Access
share
We consider the approximate support recovery (ASR) task of inferring the support of a K-sparse vector x∈ℝ^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 𝒪(K^2 log n+K log n loglog n) and 𝒪(K^3 +K^2 log n+ K log n loglog n) per iteration, respectively. When K ≪ n, this is much lower than the complexity of approximate message passing with a minimum mean squared error denoiser (AMP-MMSE) ,which requires 𝒪(mn) operations per iteration. This gain comes at a slight performance cost. Our findings suggest that notions from multiple access an important role in the design of measurement schemes for ASR.
READ FULL TEXT