Generalized Approximate Message-Passing for Compressed Sensing with Sublinear Sparsity

This paper proposes generalized approximate message passing (GAMP) for reconstruction of sparse signals from generalized linear measurements. The signal sparsity is assumed to grow sublinearly in the signal dimension, in contrast to conventional linear sparsity. State evolution is utilized to design GAMP for signals with sublinear sparsity. When the support of nonzero signals does not include a neighborhood of zero, the so-called all-or-nothing phenomenon occurs for Bayesian GAMP: Bayesian GAMP achieves asymptotically exact signal reconstruction if and only if the prefactor in the sample complexity scaling is larger than a threshold. Numerical simulations show that Bayesian GAMP outperforms existing algorithms for the reconstruction of signals with sublinear sparsity in the linear measurement and 1-bit compressed sensing.