Coded Compressive Sensing: A Compute-and-Recover Approach

Original · EN

In this paper, we propose coded compressive sensing that recovers an n-dimensional integer sparse signal vector from a noisy and quantized measurement vector whose dimension m is far-fewer than n. The core idea of coded compressive sensing is to construct a linear sensing matrix whose columns consist of lattice codes. We present a two-stage decoding method named compute-and-recover to detect the sparse signal from the noisy and quantized measurements. In the first stage, we transform such measurements into noiseless finite-field measurements using the linearity of lattice codewords. In the second stage, syndrome decoding is applied over the finite-field to reconstruct the sparse signal vector. A sufficient condition of a perfect recovery is derived. Our theoretical result demonstrates an interplay among the quantization level p, the sparsity level k, the signal dimension n, and the number of measurements m for the perfect recovery. Considering 1-bit compressive sensing as a special case, we show that the proposed algorithm empirically outperforms an existing greedy recovery algorithm.