A Coding Theory Approach to Noisy Compressive Sensing Using Low Density Frames

摘要

We consider the compressive sensing of a sparse or compressible signal ${bf x} in {BBR}^{M}$. We explicitly construct a class of measurement matrices inspired by coding theory, referred to as low density frames, and develop decoding algorithms that produce an accurate estimate ${mathhat {bf x}}$ even in the presence of additive noise. Low density frames are sparse matrices and have small storage requirements. Our decoding algorithms can be implemented in $O(Md_{v}^{2})$ complexity, where $d_{v}$ is the left degree of the underlying bipartite graph. Simulation results are provided, demonstrating that our approach outperforms state-of-the-art recovery algorithms for numerous cases of interest. In particular, for Gaussian sparse signals and Gaussian noise, we are within 2-dB range of the theoretical lower bound in most cases.