Learning compressed sensing: Should the brain use random projections?

Yair Weiss
Hebrew University, Jerusalem
Currently on leave at MIT

Compressed sensing is a recent set of mathematical results showing that sparse signals can be exactly reconstructed from a small number of random linear measurements. Interestingly, for these ideal sparse signals with no measurement noise, {\em random} measurements significantly outperform measurements based on principal component analysis (PCA) or independent component analysis (ICA). At the same time, for other signal and noise distributions, PCA and ICA can significantly outperform random projections.

In this paper we ask: given a training set typical of the signals we wish to measure, what are the optimal set of linear projections for compressed sensing ? We show that the optimal projections are in general not the principal components nor the independent components of the data, but rather a seemingly novel set of projections that capture what is still uncertain about the signal, given the training set. We also present experimental results indicating that the projections onto the learned {\em uncertain components} may far outperform random projections. This is particularly true in the case of natural images, where random projections have vanishingly small signal to noise ratio.

Joint work with Hyun-Sung Chan and Bill Freeman