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.
But how can you do all the number crunching that is required to find the sparsest image 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. [...]
Compressed sensing has already had a spectacular scientific impact. That’s because every interesting signal is sparse — if you can just figure out the right way to define it. For example, the sound of a piano chord is the combination of a small set of pure notes, maybe five at the most. Of all the possible frequencies that might be playing, only a handful are active; the rest of the landscape is silent. So you can use CS to reconstruct music from an old undersampled recording that is missing information about the sound waves formed at certain frequencies. Just take the material you have and use l1 minimization to fill in the empty spaces in the sparsest way. The result is almost certain to sound just like the original music. [...]
...for example, a future in which the technique is used in more than MRI machines. Digital cameras, he explains, gather huge amounts of information and then compress the images. But compression, at least if CS is available, is a gigantic waste. If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? For digital snapshots of your kids, battery waste may not matter much; you just plug in and recharge. “But when the battery is orbiting Jupiter,” Candès says, “it’s a different story.” Ditto if you want your camera to snap a photo with a trillion pixels instead of a few million.
The ability to gather meaningful data from tiny samples of information is also enticing to the military: Enemy communications, for instance, can hop from frequency to frequency. No existing hardware is fast enough to scan the full range. But the adversary’s signal, wherever it is, is sparse — built up from simple signals in some relatively tiny but unknown portion of the frequency band. That means CS could be used to distinguish enemy chatter on a random band from crackle. Not surprisingly, Darpa, the Defense Department’s research arm, is funding CS research.
Compressed sensing isn’t useful just for solving today’s technological problems; the technique will help us in the future as we struggle with how to treat the vast amounts of information we have in storage. The world produces untold petabytes of data every day — data that we’d like to see packed away securely, efficiently, and retrievably. At present, most of our audiovisual info is stored in sophisticated compression formats. If, or when, the format becomes obsolete, you’ve got a painful conversion project on your hands. But in the CS future, Candès believes, we’ll record just 20 percent of the pixels in certain images, like expensive-to-capture infrared shots of astronomical phenomena. Because we’re recording so much less data to begin with, there will be no need to compress. And instead of steadily improving compression algorithms, we’ll have steadily improving decompression algorithms that reconstruct the original image more and more faithfully from the stored data." [Wired]
