While fascinating, the Sparse Measurement Matrices proposed by Radu Berinde and Piotr Indyk has a small drawback, I think. Irrespective to the dimension of the underlying manifold under study, the number of measurements must meet a higher bound in order for all columns of the measurement matrix to be linearly independent. Namely, if k is the number of ones per column, n the number of measurements and m the dimension of the space where the signal lives, the maximum size of the signal (or dimension of the ambient space) cannot be higher than the binomial coefficient:
Sondow (2005)  and Sondow and Zudilin (2006)  noted the inequality
for a positive integer and a real number.
or roughly when k is small compared to n:
For k=4 (4 zeros per column)
in other words
the signal size must be less than the fifth power of the number of measurements up to a constant
So that for a 5 MB image of dimension, the number of measurements must roughly be superior to 88 (in fact the number must be superior to 107). For some cases, this number is clearly above the intrinsic dimension of the dataset and one wonders whether it is wise to oversample compared to a Gaussian Random Matrix approach (which would require 2K+1 measurements where K is the intrinsic dimension of the signal). On the other hand, these 88 sparse samples do not require the huge memory overhead needed to store the Gaussian Matrix. Clearly one needs to investigate a sweet spot for small sized signals. I have included this condition in the function Sparse Measurement Matrix implemented here.
Another item of caution is that the measurement matrix needs to be computed beforehand. The structure of the matrix requires that the matrix be built in full before using it. The other random measurement matrices do not have this feature.
Also, and it is relevant to people thinking about Hardware implementations, the measurements itself can be extremely sparse (all zeros) or extremely full (all ones). The sparsity of these matrices is driven through a number of non-zeros elements by columns not rows.
 Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.
 Sondow, J. and Zudilin, W. "Euler's Constant, -Logarithms, and Formulas of Ramanujan and Gosper." Ramanujan J. 12, 225-244, 2006.