Mathematical Moments: Making Something out of (Next to) Nothing

Images of Stanford math building, one done using compressed sensingNormally when creating a digital file, such as a picture, much more information is recorded than necessary—even before storing or sending. The image on the right was created with compressed (or compressive) sensing, a breakthrough technique based on probability and linear algebra. Rather than recording excess information and discarding what is not needed, sensors collect the most significant information at the time of creation, which saves power, time, and memory. The potential increase in efficiency has led researchers to investigate employing compressed sensing in applications ranging from missions in space, where minimizing power consumption is important, to MRIs, for which faster image creation would allow for better scans and happier patients. Photographs courtesy of J. Bobin, E. van den Berg, and E. Candès, Stanford University.

Just as a word has different representations in different languages, signals (such as images or audio) can be represented many different ways. Compressed sensing relies on using the representation for the given class of signals that requires the fewest bits. Linear programming applied to that representation finds the most likely candidate fitting the particular low-information signal. Mathematicians have proved that in all but the very rarest case that candidate—often constructed from less than a tiny fraction of the data traditionally collected—matches the original. The ability to locate and capture only the most important components without any loss of quality is so unexpected that even the mathematicians who discovered compressed sensing found it hard to believe.

Emmanuel Candès
Emmanuel Candes
Stanford University

Listen to Emmanuel Candès speak about the exciting new field of compressed sensing.

For More Information: “Compressed Sensing Makes Every Pixel Count,” What’s Happening in the Mathematical Sciences, Vol. 7, Dana Mackenzie.