Mar 07 2010
Compressed Sensing and Sparsity, The Mathematical Quest of Dr. Emmanuel Candes


I subscribe to Wired Magazine, but am sometimes frustrated by the nature of its content which can drift off into the nonsensical. Just when I am ready to give up on the publication, it prints something that renews my interest.
The March 2010 issue has an article by Jordan Ellenberg, a mathematician at the University of Wisconsin, “F_ll _n t_e Bl_nks” about the mathematical concepts of sparsity and compressed sensing. I will not spoil the article but he begins the article by describing an MRI scan of a young child at Lucille Packard Children’s Hospital at Stanford. The pediatricians needed a high resolution scan of the child’s liver. If the doctors were to get the scan they needed, the child would have to remain perfectly still for two minutes. If the doctors gave the child enough anesthesia to stop his breathing for that period of time, they could place him in grave danger.
The solution lay in an algorithm for compressed sensing discovered by Emmanuel Candes, an applied mathematician, then at Caltech now at Stanford, in 2004. As Jordan Ellenberg explains Candes,center photo, was looking at a image called the Shepp-Logan Phantom, shown on the left, used by computer scientists to work on imaging algorithms. The image replicates the fuzzy one doctors might get if they had insufficient time to do an MRI. Candes applied an algorithm called l one minimization to the image by the press of a computer key. To his amazement the image appeared in perfect definition.
He consulted a colleague at UCLA, Terry Tao, and they developed an explanation of what might have happened. As a consequence of this research MRI machines can now produce images in seconds that used to take up to an hour to produce. The National Science Foundation awarded Candes the $ 500,000 Waterman Prize, its highest honor, for the work in 2006.
Ellenberg gives a commonsense explanation. Suppose one takes a digital image of an object that is composed of one million pixels. In compressed sensing or CS instead of measuring all one million of the pixels, one measure “only” 100.000 pixels leaving an infinite number of ways the remaining 900,000 pixels could be filled in. Candes and Tao turned to the mathematical notion of sparsity. They noted that a picture is made up of a few understandable elements of wiggly lines and blocks of color. In mathematical terms it is sparse in the way a random collection of dots on a page is not.
But Candes and Tao realized that the sparsest image is the one with the fewest number of building blocks and that they could use the l one minimization algorithm to find it quickly.The algorithm takes the blank space and starts trying to fill them in with with large blocks of color. Ellenberg notes that if the algorithm sees a cluster of green pixels it will fill the space between them with a large green rectangle. In areas of different colors it puts down smaller and smaller rectangles or other shapes to fill in the colors. At the end of the process the algorithm creates an image with the smallest possible combination of building blocks whose one million pixels have all been filled in with color. The Wired article, available on the magazine site on the Internet, has an interesting graphic showing the application of the algorithm to a grainy picture of President Obama.
The article notes that Candes and Tao have shown mathematically that the chance the image will be wrong is infinitesimally small. If it is off a bit, a mathematician can tweak the image on a laptop instead of shutting down the young patient’s lungs for an extra minute to keep his breathing still. Ellenberg notes that every interesting signal is sparse, he uses the example of a piano chord, if one can only discern the way to define it. Take what you have and then use l one minimization algorithim to fill in the blanks.
CS also addresses a growing problem, what do we do with all the information that is being accumulated? The February 24 th edition of the Economist has a 14 page supplement on “The Data Deluge.” In a sidebar entitled ” All Too Much, Monstrous Amounts of Data.” the magazine notes that the amount of information is growing at a annual compound rate of 60 %. It cites a study which notes that in 2010 1,200 exabytes of data will be generated. One exabyte is the number two to the power of sixty or ten billion copies of the one hundred and two page magazine. The Large Hadron Collider at CERN generates 40 terabytes of digital data per second. All the catalogued books in the Library of Congress contain fifteen terabytes. In other words, the information generated is more than can be stored or analyzed, so the scientists collect what they can and let the rest disappear. These numbers are beyond normal human comprehension.
Candes sees the use of CS to lighten this load. Compression and decompression algorithms will steadily improve. Perhaps in the future we will store only twenty per cent of the pixels from an audio visual image and then use the algorithms to produce the original should it be needed.
In a sense everything old is new again. In the current movie “The Last Station,” Helen Mirren plays Tolstoy’s ( played by Christopher Plummer) wife. She had worked with him for years on his novels and was able to anticipate his thought processes. In one scene she recounts how he gave her only two letters from a paragraph he was working on and exxpains how using those two letters she was able to construct the entire paragraph, a human sparsity algorithm at work.

















