Logo IMG
HOME > PAST ISSUE > July-August 2009 > Article Detail


The Best Bits

A new technology called compressive sensing slims down data at the source

Brian Hayes


The ideas behind compressive sensing came together about five years ago when Emmanuel J. Candès, a mathematician at Caltech, was working on a problem in magnetic resonance imaging. He was surprised to discover that he could reconstruct a test image exactly even though the available data seemed insufficient according to the Nyquist-Shannon criterion.

Compressive sensing in medical imagingClick to Enlarge ImageWorking with Justin Romberg (now at Georgia Tech), Candès showed that this result was not a fluke and worked out much of the underlying theory. Later Candès began collaborating with Terence Tao of UCLA (who was about to win the Fields Medal, the major prize in mathematics). In 2006 Candès, Romberg and Tao published a paper that set forth the basic principles of compressive sensing. They showed that the method achieves an efficiency close to the theoretical optimum (so we should not expect even better methods to come along soon).

Even before the Candès-Romberg-Tao paper was formally published, the results began to attract wide attention, and a number of other workers and departments launched related projects. David Donoho of Stanford University (who was Candès’s Ph.D. advisor) has made notable contributions both to theory and to applications. At Rice University Richard Baraniuk leads a large and active group; Romberg continues at Georgia Tech. By now there is a worldwide community, with workshops, conferences, web sites, special issues of journals and all the other apparatus of a rapidly expanding research area. (On the other hand, there is no consensus yet on what to call the field; many variations on compressed/compressive/condensed sensing/sampling remain in circulation.)

A prehistory of compressive sensing has also come to light, particularly in the earth sciences. In the 1970s seismologists learned to construct images of reflective layers within the earth based on data streams that did not seem to satisfy the Nyquist-Shannon criterion. The techniques can now be seen as prefiguring compressive sensing.

comments powered by Disqus


Subscribe to American Scientist