Compressed Sensing: Fast Compressive Sampling with Structurally Random Matrices

Thong Do mentions that the paper presented here is already on the Rice website. Thong Do, Trac Tran and Lu Gan are co-authors of the fascinating Fast Compressive Sampling with Structurally Random Matrices which seems to lead to highly sparse measurement matrices. The abstract reads:

This paper presents a novel framework of fast and efficient compressive sampling based on the new concept of structurally random matrices. The proposed framework provides four important features. (i) It is universal with a variety of sparse signals. (ii) The number of measurements required for exact reconstruction is nearly optimal. (iii) It has very low complexity and fast computation based on block processing and linear filtering. (iv) It is developed on the provable mathematical model from which we are able to quantify trade-offs among streaming capability, computation/memory requirement and quality of reconstruction. All currently existing methods only have at most three out of these four highly desired features. Simulation results with several interesting structurally random matrices under various practical settings are also presented to verify the validity of the theory as well as to illustrate the promising potential of the proposed framework.

I cannot wait to see how it will fare with regards to reconstruction capabilities, i.e the ability of having very sparse measurement matrices and still allow for few measurements and good reconstruction. I need to look into this deeper.