Compressed Sensing: Algorithms for Deterministic Compressed Sensing

Prompted by a commenter, I realized that there are now four, [update: strike that, make that five] different ways of building deterministic algorithms for the measurement matrices in Compressed Sensing. Terry Tao had previously introduced the subject. One can also read his take on DeVore's construction. There are currently at least three other lines of research yielding deterministic compressed sensing measurement matrices, that of Mark Iwen as mentioned before and Piotr Indyk as Muthu Muthukrishnan is pointing out in this entry. So to sumarize we have four constructions :

• Explicit Constructions for Compressed Sensing of Sparse Signals by Piotr Indyk.
• A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods, by Mark Iwen.
• Deterministic Constructions of Compressed Sensing Matrices by Ron DeVore.
• Annihilating filter-based decoding in the compressed sensing framework by Ali Hormati and Martin Vetterli
• A Frame Construction and A Universal Distortion Bound for Sparse Representations by Mehmet Akçakaya and Vahid Tarokh.

For the last entry, Emmanuel Candès made a presentation at IMA ( Compressive Sampling and Frontiers in Signal Processing ) highlithing the connections of Compressed Sensing with information and coding theory.


Photo Credit: JAXA/NHK, First HDTV view of the moon from the Kayuga probe of the Japanese Space Agency this past week. The whole movie can be seen here.