Compressed Sensing: Toward Deterministic Subsampling

In a presentation today (see Calendar), Yves Meyer pointed out quite rightfully that while the initial experiment performed by Emmanuel Candes and Justin Romberg [1] is very nice and impressive, it currently is not explained by the current crop of results in the compressed sensing field. In other words, as shown in this figure



one can notice the sampling in the Fourier space is pretty regular i.e. along lines, whereas one should expect from the random approaches seen so far that the sampling should be done randomly all over the Fourier plane, i.e. more like this:





Today he presented some of his and Basarab Matei results trying to find a way to do more deterministic subsampling that could explain the initial result of [1]. As far as I could tell the current results they arrive at allows for positive functions sampled in the Fourier space at points that lie at the vertices of quasicrystals to obtain an exact reconstruction. This is really impressive. And yes, this is an uncanny result that again rely on geometry, something

figure from reference [2]

that we have seen earlier. Then again, could a quasicrystal lattice fit into the star like sampling of [1] ?
If you wondered, the Quasicrystals made of Meyer sets are named after their discoverer: Yves Meyer. More can be found here.



Reference: [1] E. J. Candès, J. Romberg and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52 489-509. (pdf)
[2] Third figure from http://www.jcrystal.com/steffenweber/qc.html