Compressed Sensing: Deterministic Subsampling, A New Era ?

As mentioned earlier, Yves Meyer and Basarab Matei are extending the results of Emmanuel Candes, Justin Romberg and Terry Tao mentioned in Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information where the initial main question was : "Is it possible to reconstruct a function f from the partial knowledge of its Fourier coefficients on the set ?" Yves Meyer and Basarab Matei improve these results by proving that a positive function in (and zero outside) can be recovered if one knows its fourier coefficients with indices on a lattice defined as:

Which also is the lattice formed by the Fourier spectrum of a Quasicrystal ( and can be changed).


More details can be found in [1]. It doesn't get more straightforward than that. They also seem to have some results on noisy experiments. Since this is a problem with complex variables, it looks as though one would have to resort to a second order cone program (see [2])

To be complete, we would like to mention that for complex valued signals, the minimum l1 problem (1.5) and, therefore, the minimum TV problem (1.1) can be recast as special convex programs known as second order cone programs (SOCP’s).

I have not implemented it yet but other questions with regards to greedy algorithms or l_p techniques seem to be totally open. In the end, it doesn't get any more deterministic than that. What does this result mean for the rest of us ? Either we have access directly to the Fourier Transform of the signal of interest like in the case of MRI or in Interferometry, or we need to have specifically designed instrumentation that deal directly in the Fourier world. While this analysis seems to be focused on images, there is no requirement to stay in dimension 2 either. We may even need to make sure to check that dictionaries of elemental bases are themselves positive ( using techniques like Non-Negative Matrix Factorization (NMF)) so that each element is sampled with few Fourier coefficients. It looks like Meyer and Barabei have opened an entire field of low hanging fruits in both theoretical and applied math as well as hardware implementations.


[1] A variant on the compressed sensing of Emmanuel Candes, Yves Meyer, Basarab Matei. For a copy please contact directly the authors.
[2]Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, Emmanuel Candes, Justin Romberg and Terry Tao

Thank you http://servalx02.blogspot.com/ on how to use LATeX page on Blogger.