Compressed Sensing

Via a link posted by Jeff Hammerbacher, an interesting guy from Facebook, comes my current fascination with Compressive Sensing.

Compressive Sensing is a subfield of remote sensing study that attempts to resolve some of the difficult issues that arise when distributing a large number of small, failure-prone, and power-limited sensing devices. Suppose you have 1000 sensors, which need to work on a single battery for several years, and of which the expected failure rate is 20%. How to do that and get useable data at the end of the survey without breaking the bank is a difficult question.

Compressive Sensing then enters the picture. Taking queues from post-data-collection lossy compression, such as JPEG, which substantially reduces the amount of information required to faithfully represent the original information, Compressive Sensing asks "If we're going to throw all that data away in the end, after collecting the data, could we simply not collect the data to begin with?," which is tantamount to asking "Can we only record what will be important in the end?"

Of course, intuitively if you know what's going to be important in the end, there's really not that much point in recording it. We don't record things that we already understand, so how can you determine ahead of time what will be needed? It seems to go against all fundamentally held conceptions in data mining -- collect EVERYTHING, figure out what's important later.

Compressed Sensing, however, makes the incredibly counterintuitive leap that one should actually record only a completely random subset of the data random linear combination of the data (see update below), not paying any attention to the question of what will be important in the end. Linear algebra will come to your rescue and reveal anything you want to know by discerning its tertiary effects on what was actually collected.

Some useful links:

• Terence Tao, the fields medalist, gives a very accessible overview of the problem: http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/
• Rice University has perhaps the most comprehensive page of resources on the topic: http://www.dsp.ece.rice.edu/cs/ref_chron.php
• Rice also has pursued research into a single-pixel camera based on the principles of compressive sensing. It's a mind-bender: http://www.dsp.ece.rice.edu/cscamera/

How does this relate to Machine Learning, and why am I interested in it here? Well, partially it's just mad cool, and uses some incredible mathematics, plus I'm in love with Terence and drip over his every word. But also, perhaps more legitimately, Compressive Sensing has many interesting applications to dimensionality reduction. Just as one can represent an image by recording a completely random subset of the image, one can represent a high-dimensional feature space by taking completely random projections. That set of projections can then be used in your favorite algorithms, and Compressive Sensing comes to the rescue at the end when it's time to re-interpret the algorithm's output.

Igor Carron of Machine Learning (Theory) gives a nice overview of its potential impact: http://hunch.net/?p=273

Update: Igor Carron points out in the comments below that it's not a completely random subset of the data that's needed, but specifically a projection of the source data with a basis incoherent with that of the source data. A set of random linear projections turns out to do the trick.