  We consider the compressive sensing of a sparse or compressible signal ${\bf
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{\bf 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.
