Compressed Sensing and Natural Image Statistics

Compressed sensing (CS) refers to a branch of applied mathematics which is based on the surprising result whereby signals that are exactly “k-sparse” (i.e. can be represented by at most k nonzero coefficients in some basis) can be exactly reconstructed using a small number of random measurements. Since natural images tend to be sparse in the wavelet basis, one of the motivating examples of CS has always been to reconstruct high resolution images from a small number of random measurements. Unfortunately, there are some significant deviations between the way that natural images behave and the assumptions of the dramatic theorems, and in fact random projections perform quite poorly when applied to real images. I will describe an alternative theory, which we call “Informative Sensing”, that seeks a small number of projections that are maximally informative given a known distribution over signals. I will show experimental results demonstrating that the informative projections indeed outperform random projections, but that the savings relative to more standard imaging methods are altogether rather modest.

Joint work with Hyun Sung Chang and Bill Freeman.