Maths Adlibs

Very cool article in Wired on Compressed Sensing.

Compressed sensing works something like this: You’ve got a picture — of a kidney, of the president, doesn’t matter. The picture is made of 1 million pixels. In traditional imaging, that’s a million measurements you have to make. In compressed sensing, you measure only a small fraction — say, 100,000 pixels randomly selected from various parts of the image. From that starting point there is a gigantic, effectively infinite number of ways the remaining 900,000 pixels could be filled in.

The key to finding the single correct representation is a notion called sparsity, a mathematical way of describing an image’s complexity, or lack thereof. A picture made up of a few simple, understandable elements — like solid blocks of color or wiggly lines — is sparse; a screenful of random, chaotic dots is not. It turns out that out of all the bazillion possible reconstructions, the simplest, or sparsest, image is almost always the right one or very close to it.