Compressed Sensing: A Lecture on the Convergence of CoSaMP

Joel Tropp gave an excellent talk today at IHP. For two hours, he pretty much gave the proofs of the convergence of CoSaMP, a work he has done with Deanna Needell.

Besides the talk, here are some excerpts that I found interesting. He mentioned that Emmanuel Candes is still getting reviews saying "Everyone knows this is impossible" when talking about finding the solution of an under-determined system when the solution is sparse. I should probably include this in the adwords ads (please take the poll). It also really points to the need to do a better job spreading that word.

One of the reason, Joel is partial to the Partial Fourier Transform lies in three reasons:

• It is technologically relevant: some technology like MRI directly access the Fourier domain
• The FFT is a fast matrix-vector multiply (see previous discussion) and finally,
• There is a low storage requirement for that matrix (as opposed to Gaussian ensembles for instance)

Finally, when the Conjugate gradient error estimate is included in the general error treatment for the convergence of CoSaMP ( see previous discussion) it looks as though, one requires on the order of three iterations per use of the Conjugate Gradient to get a satisfactory convergence without polluting CoSaMP.

Joel also seems to think that RIP is not the reason why CoSaMP works and that there maybe a more generic reason but that it has not been found yet (my words). The proof of the convergence of CoSaMP relies heavily on RIP but maybe, this is my guess, better bounds independent of RIP could be found in the future.

The organizers did a good job of inviting him over.

On a different note Irina Rish seems top think that taping the workshop is a good idea. We'll see.