Today, let's talk about getting something from nothing. The University of Houston presents this program about the machines that make our civilization run, and the people whose ingenuity created them.
In his short story "On Exactitude in Science" Jorge Lu's Borges describes a map so detailed that it is the exact size of the empire it represents. Every bridge, road and house on the map is the size of their real counterpart. Of course, such a map is absurd. Maps are useful because they show us the most important features ' they give us only the information we need. Even a map that is more than a few feet across is useless for navigation. The job of a mapmaker is to discard enormous amounts of detail, and show us only what we need to get from one place to another.
This is not only true for maps. Our megapixel cameras are similar to the cartographers in Borges' story. Each photo we take contains enormous amounts of data. However, the information that we need to reconstruct a good approximation of each image is much smaller. This is why photos are almost always compressed when stored. Indeed, most compression works by discarding some of the unnecessary information in the original pictures.
If much of the information in a digital photo is thrown away afterwards, then why do we need megapixel cameras? Why not record just the essential information about the scene in front of us to start with. If we did so, we would not have to compress the pictures later.
But how to make just the right measurements has long puzzled scientists and mathematicians. The problem is that one approach may work for some pictures, but fail for others. Can we make a camera that will take only a few measurements from which we can reconstruct any picture?
The mathematician Emmanuel Cand's stumbled upon an idea that allows us to do this almost by chance. He was looking at new ways to denoise an image. He knew that the best algorithm that would extract the relevant information he needed would require far too much time to run. He therefore tried an approach that at first sight should not have worked well. To his surprise he recovered almost all the information in the original image, the process worked like magic. Cand's said later: "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."
This was a step in the development of what is now called "compressive sensing": A way to take good pictures by taking relatively few measurements. Surprisingly, these measurements can be taken at random. To many the entire approach seemed to good to be true. But mathematicians soon answered these doubts. As a result, compressive sensing is used in different areas of medical imaging, and its applications are growing.
We are awash in information. But the main problem is not how to acquire more. Like cartographers, we need to extract what matters, and discard the rest. And here, like in so many other matters, mathematics can show the way.
Starting from top left. David Donoho, Terence Tao, Justin Romeberg, Emmanuel Candes.
I'm Krešimir Josić, at the University of Houston, where we're interested in the way inventive minds work.
(Theme music)
Compressive sensing has a long history. Here is a good article in Wired that gives a more detailed overview of its origins, including contributions by David Donoho, Terrence Tao, Justin Romberg and others, in addition to Emanuel Cand's http://www.wired.com/2010/02/ff_algorithm/.
Here is another overview with a bit more math, but also very understandable http://www.ams.org/samplings/math-history/hap7-pixel.pdf .
There is an excellent article about Terrence Tao in the New York Times. He is one of the greatest living mathematicians http://www.nytimes.com/2015/07/26/magazine/the-singular-mind-of-terry-tao.html?_r=0
It actually builds on an idea by Lewis Carroll https://en.wikipedia.org/wiki/On_Exactitude_in_Science .
Here is an interview with Emmanuel Cand's. Follow the link to a more technical review article. http://archive.sciencewatch.com/dr/erf/2011/11junerf/11junerfCandET/
Richard Baraniuk's website at Rice University is here http://web.ece.rice.edu/richb/
Thanks to Bernhard Bodmann for his feedback on this episode.
This episode was first aired on August 19, 2015