Skip to content

Compressive Sensing

July 8, 2015

In his short story “On Exactitude in Science” Jorge Luis 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 the most important features of a location – 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 then to discard enormous amounts of detail, and show us only what we need to know 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.

But if much of the information in a photo is thrown away afterwards, then why do we need megapixel cameras? Why not just record the essential information about the scene in front of us to start with. If we did so, we would not have to compress the files later.

How to do this has long puzzled scientists and mathematicians. The problem is that one approach may work for some pictures, but fail for others. How can we make a camera that will always only make measurements we need to reconstruct a picture?

The mathematician Emmanuel Candés stumbled upon the answer almost by chance while trying to remove noise from an image. He knew that an exact algorithm that would identify only relevant information 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 the first step in the development of what is now called “compressive sensing”: A way to take good pictures by taking very few measurements. Surprisingly, rather than carefully planning which measurements to take, it is best to take measurements at random. When this was first proposed, many thought it must be wrong. How could taking measurements at random work better than a sophisticated algorithm? Later mathematical analysis answered these doubts, however. 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 find what matters, and discard the rest. And here, like in so many other matters, it is mathematics that shows the way.

Some notes:

Here is an interview with one of the discoverers of compressive sensing, Emmanuel Candés. Follow the link to a more technical review article.

Here is a good article in Wired that gives a more detailed overview of the origins of compressive sensing  Here is another overview with a bit more math, but also very understandable. Here is also an understandable lecture.

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: