Compressed Sensing: Toeplitz Block Matrices in Compressed Sensing

Following up on previous results, here is this preprint by Florian Sebert, Leslie Ying, and Yi Ming Zou entitled Toeplitz Block Matrices in Compressed Sensing. The abstract reads:

Recent work in compressed sensing theory shows that nxN independent and identically distributed (IID) sensing matrices whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if n is much less than N. Motivated by signal processing applications, random filtering with Toeplitz sensing matrices whose elements are drawn from the same distributions were considered and shown to also be sufficient to recover a sparse signal from reduced samples exactly with high probability. This paper considers Toeplitz block matrices as sensing matrices. They naturally arise in multichannel and multidimensional filtering applications and include Toeplitz matrices as special cases. It is shown that the probability of exact reconstruction is also high. Their performance is validated using simulations.

There is a good summary of the type of matrices that satisfy RIP and with what probability. These types of block Toeplitz construction seem to be doing as well as the average gaussian random matrix.