CS: Commenting on the beauty of compressive sensing

Previously, I mentioned something about this entry in the GE Global Research Blog:

After a corporate interest advertized by Nokia, here is a blog entry from GE Global Research that summarizes some work performed there on Compressed Sensing. The entry is entitled The beauty of compressive sensing. One can read:

In the first image (to the left, in the upper left), the pixels are roughly half white and half dark. The Fourier coefficients (upper right) are not sparse either, containing many high frequency components. Therefore, the L1-based reconstruction methods have difficulty in recovering the original image from few samples. In contrast, the entropy optimization method can perfectly reconstruct the signal with 2500 measurements (bottom right), about 61% of the number of pixels.

...The GE work seems to point to the use of a solver comparable to an l_0 solver. I look forward to the publications on that.

Phil Schniter sent me the following observation:

hi igor,

I think that this "half-white half-dark" scenario put forth by the authors is easily handled by many of the existing model-based sparse-reconstruction algorithms.

To see why, recall that model-based reconstruction is known to recover accurately using M = O(K) measurements, where M denotes the number of measurements and K denotes the number of non-zero signal coefficients, out of N total coefficients. In particular, suppose that a given model-sparse algorithm recovers with M=C*K measurements for some constant C>1. the problem suggested above, for which K/N = 0.5, requires oversampling ratio 0.61 = M/N = C*K/N = C/2, which corresponds to C = 1.22.

To check whether there exist algorithms which recover accurately with M=1.22*K measurements, one can consider donoho/tanner phase transition curves over the undersampling/sparsity region (delta,rho), where rho=K/M and delta=M/N. Note that the range of problems for which K/N=0.2 (i.e., rho*delta=0.5) describe an arc in the upper right quadrant of the (delta,rho) region, passing through (0.5,1) and (0.71,0.71) and (1,0.5). so, the question boils down to: which algorithms yield phase transition curves that intersect this arc? I demonstrated one in my CISS 2010 paper on Turbo Reconstruction of Structured Sparse Signals (http://www.ece.osu.edu/~schniter/pdf/ciss10_bp.pdf) that embedded the donoho/maleki/montanari AMP algorithm within a larger iterative framework.

cheers,
phil

I think I need to pay more attention to these model based reconstruction solvers. For information, the Donoho-Tanner phase transition can be found in Phase Transitions of the Regular Polytopes and Cone. If I recall correctly they were not computed with the AMP solver but rather with the commercial MOSEK solver.

Thanks Phil !

Harry Sun and Yi (Jessica) Yao, the authors of the study mentioned in the blog, kindly responded in the comment section with:

To make the L1 optimization work, an inherently sparse visual signal has to be sparsified by an operator, e.g. Fourier transform, so that most coefficients become zero. However, finding such an operator for any inherently sparse signal is not trivial. The work mentioned in the blog has been issued as an internal technical report, and is being considered for external submission. Thank you for your feedback.

As I said before, I look forward to reading this report when it comes out.

Credit: Top figure from the GE Global Research Blog, second figure from Turbo Reconstruction of Structured Sparse Signals, last figure from the Phase Transitions of the Regular Polytopes and Cone site.