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

[Rich Murray]

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 ( [hidden email] ), 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  [hidden email]

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

[glen e. p. ropella-2]

Thus spake Rich Murray circa 10-02-26 09:18 AM:
> http://www.wired.com/magazine/2010/02/ff_algorithm/all/1

Thanks for forwarding this.  On the surface, it seems like it's a
particular type of genetic algorithm.  The sparsity function is the
objective, the low-res measurements are a constraint, the shapes that
are plugged into the holes are the terminals, and the methods for
choosing when to place smaller shapes are the operators.  The population
consists of individual, filled-in images.

Given that, I wonder if CS has the same persnickety implementation
issues that GAs have?  TANSTAAFL, I mean.  I.e. the magic lies in
getting the objective function, terminals, and operators just right to
make any progress.  And behind every "miraculous" success lies a long
evolution of tweak a little, here, tweak a little there, etc.

Anyone know more about this and can shatter my analogy before I attempt
to wade through a bunch of CS/l_1 papers?

--
glen e. p. ropella, 971-222-9095, http://agent-based-modeling.com


============================================================
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]

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" <[hidden email]> 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 ( [hidden email] ), 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  [hidden email]

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