  In this paper, we study the number of measurements required to recover a
sparse signal in ${\mathbb C}^M$ with $L$ non-zero coefficients from compressed
samples in the presence of noise. For a number of different recovery criteria,
we prove that $O(L)$ (an asymptotically linear multiple of $L$) measurements
are necessary and sufficient if $L$ grows linearly as a function of $M$. This
improves on the existing literature that is mostly focused on variants of a
specific recovery algorithm based on convex programming, for which
$O(L\log(M-L))$ measurements are required. We also show that $O(L\log(M-L))$
measurements are required in the sublinear regime ($L = o(M)$).
