Sparse Representations

Posted on 11/17/07 in Research Articles

What do researchers studying infrared spectroscopy, seismic imaging, error correcting codes, and MRI’s have in common? They all can get better results if they have the right math. Fourier analysis, discovered in analyzing the flow of heat, revolutionized how mathematics is used in a variety of sciences by breaking complicated functions into a sum of simple parts. Of course, it is even better if you can break something complicated into a small number of more basic parts – this is known as a sparse representation. A breakthrough was made by David Donoho and by Emmanuel Candes and sparse repsTerence Tao, who discovered new paradigms for sparse representations. Their method reduces a problem that is computationally very hard to one that is computationally much more tractable.

In the Fall of 2004, IPAM brought together a mix of pure and applied mathematicians, statisticians, atrophysicists, geoscientists, and computer scientists for a first-ever 3-month program on Multiscale Geometry and Analysis in High Dimensions. When Donoho gave an exposition of his work at the Tutorials for IPAM’s program, the impact was immediate. Ronald Coifman saw within days the possibilities of this idea in the context of infrared spectroscopy. Working with Fred Warner, he obtained a spectral reconstruction that was more than a 50% reduction in measurement time for comparable spectral quality. Michael Lustig returned to Stanford from the tutorials inspired by Donoho and Emmanuel Candes’ talks and obtained a 50% speed improvement for an MRI scanner with no perceptual loss.

In the second workshop of this program, Emmanuel Candes described the pathbreaking work he had done with Terence Tao during the program that gave a new method using random projections for obtaining sparse representations. After discussions with participating computer scientists, they applied their techniques to error-correcting codes. The resulting scheme, which is quite novel, has an unusually high tolerance for errors and has been remarkable effective in numerical experiments. In a completely different direction, Felix Herrmann, a geoscientist who participated in the entire program, adapted this circle of ideas to make important improvements in seismic imaging.

This body of work has had enormous impact and has inspired numerous further scientific conferences.