Compressed Sensing: A Lower Bound for the Number of Measurements in Sparse Measurement Matrices ?

[Update: see the comment section of this post, Radu Berinde mentions that the bound I am mentioning is satisfied with high probability. Thank you Radu]

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:

Conversely, the number of measurements (n) must be enough for the inequality to stand.

m less than C(n,k)

If one considers using k = 2, and the number of measurements is 2 (n=2) then the absolute maximum size of the signal is 1. When the number of measurements is 10, then the absolute maximum size of the signal is 45. When looking at a 5 MB image, one needs to play with n (number of measurements) and k (number of ones per column) to find the closest m to 5 x 10^6.

Wolfram's site has a collection of references on binomial coefficients and the latest sharpest bound is:

Sondow (2005) [1] and Sondow and Zudilin (2006) [2] noted the inequality

for a positive integer and a real number.

If I did the variable change correctly, the lower bound of this inequality translates into:

m less than 1/4 n (n/k)^k 1/(1-k/n)^(n-k-1)

or roughly when k is small compared to n:

m less than 1/(4 k^k) n^(k+1)

For k=4 (4 zeros per column)

m less than 1/1024 n^ 5
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.

Finally, in regards to a previous question, the sparsity structure of this measurement matrices can used by most current solvers through the use of a function handle. A minor point remains as to whether the actual solvers could not be further designed with the sparsity structure in mind.


Reference:
[1] Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.

[2] Sondow, J. and Zudilin, W. "Euler's Constant, -Logarithms, and Formulas of Ramanujan and Gosper." Ramanujan J. 12, 225-244, 2006.

Photo Credit: NASA/JPL/Space Science Institute, The Cassini spacecraft's close flyby of Epimetheus (116 kilometers, or 72 miles across) on December 3, 2007 returned detailed images of the moon's south polar region.