Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples

Using a mathematical concept called sparsity, the compressed-sensing algorithm takes lo-res files and transforms them into sharp images. 
Illustration: Gabriel Peyre

In the early spring of 2009, a team of doctors at the Lucile Packard Children’s Hospital at Stanford University lifted a 2-year-old into an MRI scanner. The boy, whom I’ll call Bryce, looked tiny and forlorn inside the cavernous metal device. The stuffed monkey dangling from the entrance to the scanner did little to cheer up the scene. Bryce couldn’t see it, in any case; he was under general anesthesia, with a tube snaking from his throat to a ventilator beside the scanner. Ten months earlier, Bryce had received a portion of a donor’s liver to replace his own failing organ. For a while, he did well. But his latest lab tests were alarming. Something was going wrong — there was a chance that one or both of the liver’s bile ducts were blocked.

Shreyas Vasanawala, a pediatric radiologist at Packard, didn’t know for sure what was wrong, and hoped the MRI would reveal the answer. Vasanawala needed a phenomenally hi-res scan, but if he was going to get it, his young patient would have to remain perfectly still. If Bryce took a single breath, the image would be blurred. That meant deepening the anesthesia enough to stop respiration. It would take a full two minutes for a standard MRI to capture the image, but if the anesthesiologists shut down Bryce’s breathing for that long, his glitchy liver would be the least of his problems.

However, Vasanawala and one of his colleagues, an electrical engineer named Michael Lustig, were going to use a new and much faster scanning method. Their MRI machine used an experimental algorithm called compressed sensing — a technique that may be the hottest topic in applied math today. In the future, it could transform the way that we look for distant galaxies. For now, it means that Vasanawala and Lustig needed only 40 seconds to gather enough data to produce a crystal-clear image of Bryce’s liver.

Compressed sensing was discovered by chance. In February 2004, Emmanuel Candès was messing around on his computer, looking at an image called the Shepp-Logan Phantom. The image — a standard picture used by computer scientists and engineers to test imaging algorithms — resembles a Close Encounters alien doing a quizzical eyebrow lift. Candès, then a professor at Caltech, now at Stanford, was experimenting with a badly corrupted version of the phantom meant to simulate the noisy, fuzzy images you get when an MRI isn’t given enough time to complete a scan. Candès thought a mathematical technique called l₁ minimization might help clean up the streaks a bit. He pressed a key and the algorithm went to work.

Candès expected the phantom on his screen to get slightly cleaner. But then suddenly he saw it sharply defined and perfect in every detail — rendered, as though by magic, from the incomplete data. Weird, he thought. Impossible, in fact. “It was as if you gave me the first three digits of a 10-digit bank account number — and then I was able to guess the next seven,” he says. He tried rerunning the experiment on different kinds of phantom images; they resolved perfectly every time.

Candès, with the assistance of postdoc Justin Romberg, came up with what he considered to be a sketchy and incomplete theory for what he saw on his computer. He then presented it on a blackboard to a colleague at UCLA named Terry Tao. Candès came away from the conversation thinking that Tao was skeptical — the improvement in image clarity was close to impossible, after all. But the next evening, Tao sent a set of notes to Candès about the blackboard session. It was the basis of their first paper together. And over the next two years, they would write several more.

That was the beginning of compressed sensing, or CS, the paradigm-busting field in mathematics that’s reshaping the way people work with large data sets. Only six years old, CS has already inspired more than a thousand papers and pulled in millions of dollars in federal grants. In 2006, Candès’ work on the topic was rewarded with the $500,000 Waterman Prize, the highest honor bestowed by the National Science Foundation. It’s not hard to see why. Imagine MRI machines that take seconds to produce images that used to take up to an hour, military software that is vastly better at intercepting an adversary’s communications, and sensors that can analyze distant interstellar radio waves. Suddenly, data becomes easier to gather, manipulate, and interpret.

Photos: Obama: Corbis; Image Simulation: Jarvis Haupt/Robert Nowak

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.

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 l₁ 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.

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 l₁ minimization to fill in the empty spaces in the sparsest way. The result is almost certain to sound just like the original music.

With his architect glasses and slightly poufy haircut, Candès has the air of a hip geek. The 39-year-old Frenchman is soft-spoken but uncompromising when he believes that something isn’t up to his standards. “No, no, it is nonsense,” he says when I bring up the work of a CS specialist whose view on a technical point differs — very slightly, it seems to me — from his own. “No, no, no, no. It is nonsense and it is nonsense and it is wrong.”

Candès can envision a long list of applications based on what he and his colleagues have accomplished. He sees, 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 pixelsinstead 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.

That’s the future. Today, CS is already rewriting the way we capture medical information. A team at the University of Wisconsin, with participation from GE Healthcare, is combining CS with technologies called HYPR and VIPR to speed up certain kinds of magnetic resonance scans, in some cases by a factor of several thousand. (I’m on the university’s faculty but have no connection to this particular research.) GE Healthcare is also experimenting with a novel protocol that promises to use CS to vastly improve observations of the metabolic dynamics of cancer patients. Meanwhile, the CS-enabled MRI machines at Packard can record images up to three times as quickly as conventional scanners.

And that was just enough for 2-year-old Bryce. Vasanawala, in the control room, gave the signal; the anesthesiologist delivered a slug of sedative to the boy and turned off his ventilator. His breathing immediately stopped. Vasanawala started the scan while the anesthesiologist monitored Bryce’s heart rate and blood oxygenation level. Forty seconds later, the scan was done and Bryce had suffered no appreciable oxygen loss. Later that day, the CS algorithm was able to produce a sharp image from the brief scan, good enough for Vasanawala to see the blockages in both bile ducts. An interventional radiologist snaked a wire into each duct, gently clearing the blockages and installing tiny tubes that allowed the bile to drain properly. And with that — a bit of math and a bit of medicine — Bryce’s lab test results headed back to normal.

Jordan Ellenberg ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ), an associate professor of mathematics at the University of Wisconsin, wrote about the Netflix Prize in issue 16.03.