Deterministic Compressed Sensing

Compressed sensing continues to thrive, with young and established, Computer Science/Analysis/Communication theory/Applied signal processing researchers continuing to generate new results rapidly.The Rice site manages to keep pace, and the algorithms community is well-represented. Recent algorithmic results from upcoming SODA08 include:

• Mark Iwen's "A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods". Mark improves upon prior deterministic compressed sensing results by using better grouptesting family of sets.
  
• Piotr Indyk's "Explicit constructions for compressed sensing of sparse signals". Improved constructions using expanders. (Though not immediately related, check out his talk.)