Saturday, October 13, 2007

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.)


Anonymous Paul Beame said...

Those aren't the only SODA 08 papers on compressed sensing. There is also: "Almost Euclidean subspaces of l_1^N via expander codes" by Guruswami, Lee, and Razborov (even though it doesn't sound like it).

7:25 PM  
Anonymous Anonymous said...

Absolutely, mea culpa. I need to read that paper. -- metoo.

5:35 PM  

Post a Comment

<< Home