Very interesting! I of course believe them that this works amazingly well in most applications it has been tested in. I wonder, however, if there are not easily predictable contexts in which it will err. Most obviously (say I, sitting in my arm-chair), when attempting to reconstruct an image that was fuzzy (i.e., a very soft-focus photograph).
Eric On Fri, Feb 26, 2010 12:18 PM, "Rich Murray" <[email protected]> wrote: > equivalent to Turing machine? approximation for complex algorithms >(travelling salesman problem level)? compressed sensing 2004 Emmanuel >Candès >& Justin Romberg, article Wired 2010 March, Jordan Ellenberg: Rich Murray >2010.02.26 >http://rmforall.blogspot.com/2010_02_01_archive.htm >Friday, February 26, 2010 >http://groups.yahoo.com/group/rmforall/message/94 >_____________________________________________________ > > > >What happens in higher dimensional spaces, such as the 10+1 dimensions of >superstring theory? > >Brains must use this... could this be a universal computer? > >http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 > >F_ll _n t_e bk__ks >A revolutionary algorithy can make something out of nothing. > >Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples >By Jordan Ellenberg February 22, 2010 12:00 pm Wired March 2010 18:03 > >Using a mathematical concept called sparsity, the compressed-sensing >algorithm takes lo-res files and transforms them into sharp images. > >Illustration: Gabriel PeyreIn 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 aClose >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 l1 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. > >How Math Gets the Grain Out > >Compressed sensing is a mathematical tool that creates hi-res data sets from >lo-res samples. It can be used to resurrect old musical recordings, find >enemy radio signals, and generate MRIs much more quickly. Here's how it >would work with a photograph. > > >1 Undersample > >A camera or other device captures only a small, randomly chosen fraction of >the pixels that normally comprise a particular image. This saves time and >space. > >2 Fill in the dots > >An algorithm calledl1 minimization starts by arbitrarily picking one of the >effectively infinite number of ways to fill in all the missing pixels. > >3 Add shapes > >The algorithm then begins to modify the picture in stages by laying colored >shapes over the randomly selected image. The goal is to seek what's called >sparsity, a measure of image simplicity > >4 Add smaller shapes > >The algorithm inserts the smallest number of shapes, of the simplest kind, >that match the original pixels. If it sees four adjacent green pixels, it >may add a green rectangle there. > >5 Achieve clarity > >Iteration after iteration, the algorithm adds smaller and smaller shapes, >always seeking sparsity. Eventually it creates an image that will almost >certainly be a near-perfect facsimile of a hi-res one. > >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 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. > >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. > >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 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. > >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 ( [email protected] ), an associate professor >of >mathematics at the University of Wisconsin, wrote about the Netflix Prize in >issue 16.03. > >Registration on or use of this site constitutes acceptance of our User >Agreement (Revised 4/1/2009) and Privacy Policy (Revised >4/1/2009). >Wired.com © 2009 Condé Nast Digital. All rights reserved. >The material on this site may not be reproduced, distributed, transmitted, >cached or otherwise used, except with the prior written permission of Condé >Nast Digital. >_____________________________________________________ > > >Rich Murray, MA >Boston University Graduate School 1967 psychology, >BS MIT 1964, history and physics, >1943 Otowi Road, Santa Fe, New Mexico 87505 >505-501-2298 [email protected] > >http://groups.yahoo.com/group/rmforall/messages > >http://groups.yahoo.com/group/AstroDeep/messages > >http://RMForAll.blogspot.com new primary archive > >http://groups.yahoo.com/group/aspartameNM/messages >group with 144 members, 1,594 posts in a public archive > >http://groups.yahoo.com/group/aspartame/messages >group with 1215 members, 24,020 posts in a public archive > >participant, Santa Fe Complex www.sfcomplex.org >__________________________________________________ > > >============================================================ >FRIAM Applied Complexity Group listserv >Meets Fridays 9a-11:30 at cafe at St. John's College >lectures, archives, unsubscribe, maps at http://www.friam.org > > > Eric Charles Professional Student and Assistant Professor of Psychology Penn State University Altoona, PA 16601
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
