Compressive Sensing Using Low Density Frames

Abstract

We consider the compressive sensing of a sparse or compressible signal $\mathbf{x}\in {\mathbb{R}}^M$. We explicitly construct a class of measurement matrices, referred to as the low density frames, and develop decoding algorithms that produce an accurate estimate $\hat{\mathbf{x}}$ even in the presence of additive noise. Low density frames are sparse matrices and have small storage requirements. Our decoding algorithms for these frames have $O(M)$ complexity. Simulation results are provided, demonstrating that our approach significantly 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.

11 pages, 6 figures, Submitted to IEEE Transactions on Signal Processing

References in corpus (5)

• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Shannon Theoretic Limits on Noisy Compressive Sampling

Cited by in corpus (3)

• Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
• A signal recovery algorithm for sparse matrix based compressed sensing
• An Efficient Approach Toward the Asymptotic Analysis of Node-Based Recovery Algorithms in Compressed Sensing