Another Comment on " Random Matrices Are Too Damn Large ! "

Ben Adcock, one of the author of a paper I mentioned in Random Matrices Are Too Damn Large ! sent me the following:

Dear Igor, 

Many thanks for citing our newest preprint in your blog post on Wednesday. The computational infeasibility of random matrices on all but small problems is a critical issue that has been often overlooked. 

Having said that, the key message of our paper is that incoherent sensing matrices, regardless of storage/speed issues, are highly suboptimal in practice. Any attempt to mimic random Gaussians in hardware will also share this suboptimality. 

This run contrary to the standard view in the community. Of course, random Gaussians are ideal when there is sparsity but nothing else. But natural images, when sparsified via *-lets or TV for example, possess far more structure than sparsity alone. 

Our paper shows that one can significantly outperform random matrices, regardless of the recovery algorithm used (e.g. l1, greedy, AMP,...). We do this by designing measurements in the form of multilevel subsampled Fourier or Hadamard matrices that encompass both the sparsity and the structure. Conveniently, these matrices are also computationally efficient, since they possess O(N*log(N)) transforms. 

Storage/speed aside though, this is the key message of the paper: if one deals with sparsifying transforms that yield structured sparsity, then it is highly desirable, and completely practical, to design measurements that exploit this structure. This yields not only better results, but also allows one to go to much higher resolutions, where the asymptotic behavior brings even more benefits. 

A good example of universal vs non-universal sensing is provided in Fig 11 of the paper. The asymptotic resolution dependency is shown in Figs 6 and 7, where a 2048x2048 image was recovered very well at only 6% subsampling rate in just ~60 seconds. 

The paper can be downloaded here: http://arxiv.org/pdf/1406.4178

I hope you find this remark interesting. If you have questions, comments etc, then please let me know.
Best wishes,
Ben

Thank you Ben !

As I have said numerous times, this line of investigation is indeed very interesting as it makes a deeper connection between the object being sampled and the measurement matrix. I note that the incoherence argument still stands but in a finer way than the generic "coarse" approach we have been using in generic compressive sensing. Maybe we are observing some schism here, where purely sparse arguments now have to yield to finer structured sparsity arguments. But I am not so certain about it being a clear cut break as sparsity arguments or counting are deeply rooted concepts. Furthermore, I would not be surprised to see the multilevel phase transitions showing up in the approach of Ben et al. 

To come back to the initial blog entry that started this discussion, it was mostly to prepare Nuit Blanche readers for the next day entry that introduced our approach to using random materials for information transmission at a lower rate than was thought possible [1,2, 3]. I would not be surprised if we could not use Ben et al's work to figure out something deeper about these materials. More on that later...

[1] Imaging With Nature: Compressive Imaging Using a Multiply Scattering Medium

[2] Additional Photos and Video to "Imaging With Nature: Compressive Imaging Using a Multiply Scattering Medium"

[3] The Post Publication Peer Review of "Imaging With Nature: Compressive Imaging Using a Multiply Scattering Medium"

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.