CS: Theoretical Analysis of Compressive Sensing via Random Filter

This is novel and interesting. Instead of using only a CS encoding / measurement matrix that is Gaussian or else, this new approach uses both multiplexed measurements and "normal" samples and show that after some subsampling, one can recover the full original signal. 

In Theoretical Analysis of Compressive Sensing via Random Filter by Lianlin Li, Yin Xiang and Fang Li. The abstract reads:

In this paper, the theoretical analysis of compressive sensing via random filter, firstly outlined by J. Romberg [compressive sensing by random convolution, submitted to SIAM Journal on Imaging Science on July 9, 2008], has been refined or generalized to the design of general random filter used for compressive sensing. This universal CS measurement consists of two parts: one is from the convolution of unknown signal with a random waveform followed by random time-domain subsampling; the other is from the directly time-domain subsampling of the unknown signal. It has been shown that the proposed approach is a universally efficient data acquisition strategy, which means that the n-dimensional signal which is S sparse in any sparse representation can be exactly recovered from Slogn measurements with overwhelming probability.

I note that most of the papers that are providing a rationale for this paper are still in preprint and have shown up on Arxiv only about a month ago. I realize that one of the author reads this blog, but I still find it amazing how the web is enabling some thought process acceleration. On a technical level, I note that this approach bears some similarity to Dense Error Correction via l1 Minimization, John Wright and Yi Ma, except that the location of the identity matrix in the traditional Measurement matrix is different and this has profound implication on the measurement process ( whereas it doesn't in the paper by John Wright and Yi Ma ). If one were to mix both approaches, one could conceivably subsample non-sparse signals! I can think of different ways to use the concepts in this paper in imaging.

In a different direction, the structure of the random filters of Justin Romberg ( Justin Romberg, Compressive sensing by random convolution ) bears some similarity with the Toeplitz matrix used in the context of Coded aperture by Roummel Marcia and Rebecca Willett in Compressive Coded Aperture Superresolution Image Reconstruction (additional information can be found here).