Tag Archives: David Donoho

Compressed Sensing: Filling in the Blanks

I stumbled across this article today, Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples by By Jordan Ellenberg, Wired Magazine, February 22, 2010, and found it so fascinating – in particular because of my recent research into fractals – that I had to take a little tour around the internet to find a little more information on compressed sensing.

Wikipedia describes compressed sensing as: “a technique for acquiring and reconstructing a signal utilizing the prior knowledge that it is sparse or compressible. The field has existed for at least four decades, but recently the field has exploded, in part due to several important results by David Donoho, Emmanuel Candès, Justin Romberg and Terence Tao.”

“The ideas behind compressive sensing came together in 2004 when Emmanuel J. Candès, a  mathematician at Caltech, was working on a problem in magnetic resonance imaging. He discovered that a test image [a badly corrupted version of the image shown here] could be P = phantom('Modified Shepp-Logan',200);reconstructed exactly even with data deemed insufficient by the Nyquist-Shannon criterion.”

According to the story Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples by By Jordan Ellenberg, Wired Magazine, February 22, 2010, the mathematical technique called l1 minimization is now being looked at in a number of experimental applications, such as DARPA funded research into acquisition of enemy communication signals:

DARPA ~ …mathematics thrust area have successfully applied a methodology of discovery of physics-based structure within a sensing problem, from which it was often possible to determine and algorithmically exploit efficient low-dimensional representations of those problems even though they are originally posed in high-dimensional settings. Computational complexity and statistical performance of fielded algorithms within the DSP component of sensor systems have both been substantially improved through this approach. The aim of ISP is much more ambitious: to develop and amplify this concept across all components of an entire sensor system and then across networks of sensor systems.

data storage:

Wired ~ …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.

and further into the future, perhaps CS will even live in our digital camera’s:

Wired ~ 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.

Today though, 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.  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.

Wired ~ 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.

Read the rest of this entry »


Tags: , , , , , , , , , ,