Compressed Sensing: CS measurements of a field of Diracs, Partial Fourier vs Gaussian Ensembles

Yesterday, we looked at the reconstruction issue arising when one compares the true solution to the one found through different algorithms. We found that when a high accuracy was needed, one could not rely on the current crop of reweighted algorithms. These algorithms do find a solution with fewer terms but the accuracy of these terms is not optimal compared to the greedy algorithms. Blue Pill / Red Pill: Pick you poison.
Today, we are running the second version of MMA14 and show that for an image that is sparse in the space domain (see above), the Random Partial Fourier Transform


does a better job than a Gaussian ensemble.

(all these plots were produced with tol1 =1 e-3).

This is not unexpected. Without any computation of incoherence, it seems obvious that a Dirac (our image here is composed of several diracs) would be more incoherent with regard to a Fourier function than a function that mimic several diracs (Gaussian ensemble). Let us recall in this example that the image is an 8 by 8 image, i.e. with a least square method (L2 based reconstruction), we would need 64 measurements. The sparsity of the image is 5. In other words, if I had a normal detector taking measurements and sending it through the pipeline, I would naively need to transfer 5 information about the peaks height and 10 information about their location (x,y for each peak) or a total of 15 information. If I were to use a CS detector, 15 information (measurements) would yield above 90 percent chance of recovering the signal whereas 17 CS measurements would yield a 100 percent recovery.

This is an ideal case for one reason. When receiving the signal, one doesn't know the true signal. I would not be surprised if we could use the solution with n measurements and the solution with n+1 measurements and obtain "faster" convergence.