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

作者：Akcakaya Mehmet^*; Park Jinsoo; Tarokh Vahid

来源：IEEE Transactions on Signal Processing, 2011, 59(11): 5369-5379.

DOI：10.1109/TSP.2011.2163402

• Belief propagation
• coding theory
• compressive sensing
• EM algorithm
• Gaussian scale mixtures
• low density frames
• sum product algorithm

We consider the compressive sensing of a sparse or compressible x is an element of R(M) signal. 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) over cap 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.

• 出版日期2011-11