Guillermo Sapiro has done some quite fascinating work on applications of compressed sensing to photography (and one might say to practice in general) which he spoke about at MIT last week. The tagline is this: In compressed sensing one proves that using a random basis (i.e. random sensing matrix) one can recover signals (after the measurement) as long as one knows any basis where the signal is sparse. In other words, random matrices have this universality property. In practice, however, if you sense with a random matrix the recovery quality of, say, images is somewhat horrible — images come out as if you added Gaussian noise to them. Sapiro’s work addresses this problem.

The key idea in his work is to learn a basis that is good for images. Such basis will have to give up the universality property, but this is OK. Learning such a basis is done by taking a big collection of images and trying to find a basis where all images have sparse representations that are not too far (in L2 sense) from the original images. It turns out that a relatively simple iterative algorithm, involving linear regression at each step, does the job just fine. The results are stunning! Images come out with practically perfect quality. 

According to Sapiro, his papers are not theoretical-theoretical, in the sense that there are no proofs of “rigid” statements as one typically wants in the theory community. The usefulness of the algorithms is exhibited by look-and-feel. As one might imagine, these techniques have various applications beyond just sensing and compressing. One can do (what Sapiro calls) inpainting. This is when you are given an image missing a large fraction of its pixels or an image with a low signal-to-noise ration. If you like to “fill-in” the missing (or noisy) pixels, all you need to do is find the sparse representation of the given image that is closest in norm to the noisy original. Once again, results are stunning visually.

Lastly, this technique theme can be used for classification of the sort where you say “this image depicts cows rather than cars”. The trick here is that one learns a basis for cars and for cows such that the car basis is additionally optimized to perform intentionally bad on cows and vice-versa. The learning of such bases is a slightly more complicated version (there is an added condition) of the basic learning algorithm mentioned earlier.