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.
