Coding via random convolution

A random convolution based coding theorem is developed under the framework of compressive sensing (CS). It states a signal can be exactly recovered from very few random convolution codes, when the signal has a sparse representation in some orthobasis which keeps small coherence with the Fourier basis. The theorem also shows the codes can be chosen at any fixed locations of the convolution outputs.