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

2 Comments:

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