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

We consider the compressive sensing of a sparse or compressible signal x ∈ ℝ^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 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²) 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.