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
