It's a common thing to see on TV: the cops get a dark, blurry image of a perp, and using the magic of computers, are able to zoom in and see his face. But now that might be actually possible.

The technique, called compressed sensing, won't work like those fake programs do on TV. And it's mostly meant for scientific purposes, like shortening MRI scan times by only scanning a small amount of data and then filling in the rest.

But how can you do all the number crunching that is required to find the sparsest image quickly? It would take way too long to analyze all the possible versions of the image. Candès and Tao, however, knew that the sparsest image is the one created with the fewest number of building blocks. And they knew they could use l1 minimization to find it and find it quickly.

To do that, the algorithm takes the incomplete image and starts trying to fill in the blank spaces with large blocks of color. If it sees a cluster of green pixels near one another, for instance, it might plunk down a big green rectangle that fills the space between them. If it sees a cluster of yellow pixels, it puts down a large yellow rectangle. In areas where different colors are interspersed, it puts down smaller and smaller rectangles or other shapes that fill the space between each color. It keeps doing that over and over. Eventually it ends up with an image made of the smallest possible combination of building blocks and whose 1 million pixels have all been filled in with colors.

That image isn't absolutely guaranteed to be the sparsest one or the exact image you were trying to reconstruct, but Candès and Tao have shown mathematically that the chance of its being wrong is infinitesimally small. It might still take a few hours of laptop time, but waiting an extra hour for the computer is preferable to shutting down a toddler's lungs for an extra minute.

So yeah, it's meant for scientists right now, but this is clearly the first step to us all being about to enhance, enhance, enhance our pictures automagically. And that is damned cool.

[Wired]