Noise is the Medium and the Message

I was in Lenox, MA for a few days to give a talk at a MURI workshop. Aside from the lovely New England countryside, which on Tuesday and Wednesday looked just like the photo above, I got to see a talk about single pixel cameras using compressive imaging with L1 norm reconstruction. This is all based on the work of Terry Tau and Emmanuel Candes. Tau is the the youngest guy ever to win a Fields Medal. Apparently he's quite smrt.

So Whitaker-Shannon says that you can perfectly reconstruct a Nyquist sampled-bandwidth limited signal. Okay, everyone knows that, but it turns out Shannon was way too pessimistic - almost nothing is band-limited; Almost everything is sparse, which is to say that the entropy of the universe is low. Anyone who reads blogs knows that. And if it doesn't seem so now, everything is sparse in the right set of basis functions, and for nearly everything the right set of basis-functions turns out to be noise. Weird.

To apply this to imaging, take some binary noise and line it up into a grid; it would look like an empty cross-word puzzle. Take a same-sized image, like the one above, and multiply them together, pixel by pixel, so that you get an image where half the pixels have been set to zero. Then add up all their values into a single number. Write that down. Then start over with a new noise pattern, which is your second basis function, and turn the image into a second number by projecting it onto the basis function. For an image with N pixels, do this about K=(0.05 to 0.20)*N times. Send your friend the K values, and he can asymmptotically reconstruct the image with 99% fidelity using The Magic of the L1 Norm (you can get MATLAB code there if you want to play yourself). At this point, all I can say is that it's magic, but the fundamental insight is that things are sparse, and so there going to be room to maneuver here. The signal is almost never pathological.

The great thing is that you can turn brute force O(n^3) problems into ~O(n log n) problems; A savings of nearly n^2. In an age of cheap CCD cameras, the imaging application turns out to be useful for imaging in non-visible wavelengths, like IR, Gamma Ray, and THz, where silicon doesn't do you a lot of good. Or perhaps you want to take gigapixel+ images using megapixel camera.

This turns out to be similar to one-time pad code-breaking. The low entropy of secret messages induces statistical similarities into the encrypted message.

Anyway, very cool.