Compressive Sensing by Random Convolution

This paper demonstrates that convolution with random waveform followed by random time-domain subsampling is a universally efficient compressive sensing strategy. We show that an n-dimensional signal which is S-sparse in any fixed orthonormal representation can be recovered from m � S log n samples from its convolution with a pulse whose Fourier transform has unit magnitude and random phase at all frequencies. The time-domain subsampling can be done in one of two ways: in the first, we simply observe m samples of the random convolution, in the second, we break the random convolution into m blocks, and summarize each with a single randomized sum. We also discuss several imaging applications where convolution with a random pulse allows us to super-resolve fine-scale features, allowing us to recover high-resolution signals from low-resolution measurements. 1. Introduction. The new field of compressive sensing (CS) has given us a fresh look at data acquisition, one of the fundamental tasks in signal processing. The message of this theory can be summarized succinctly [11,12,14,17]: sparse signals can be recovered from a small number of linear measurements. We model the acquisition of a signal x0 as a series of inner products against