Hamming's time: Scientific Discovery Enabled by Compressive Sensing and related fields

I was recently asked an interesting yet challenging question. I have two or three answers and also feel the question is somewhat unfair but it picked my interest. The question was: 

Has compressive sensing helped in making discoveries in the realm of general science (as opposed to computer science, signal processing, better solvers, etc...) ?

It could be better reframed as:

Has any of the compressive sensing pipeline tools (measurement matrices, randomization, L1 or better solvers) allowed one to make a discovery that was not possible before (with the other tools) ?

First, I think this is an unfair question because I don' t feel like it should even be asked! Indeed, nobody asks the obvious question as to whether full rank linear systems and least squares solvers have led to scientific discoveries (they have). On the other hand, a more elaborate technique has to provide an enhanced threshold of justification only a few years after it has been theoretically justified. But here is where it gets weird. I initially indicated that I felt that the following papers from Bruno Ohlshausen were compressive sensing related discoveries:

Emergence of Simple-Cell Receptive Field Properties by Learning a Sparse Code for Natural Images

Olshausen BA, Field DJ (1996).   Nature, 381: 607-609.  reprint (pdf)  |  abstract

Natural Image Statistics and Efficient Coding

Olshausen BA, Field DJ (1996).   Presented at the Workshop on Information Theory and the Brain , September 4-5, 1995, University of Stirling, Scotland. Published in Network, 7: 333-339.   reprint (pdf)  |  abstract

Indeed, after the publication of these papers, the community at large began to realize that sparse coding was not just an artifact of being into the parcimony business. Rather it was an actual biological process that could be mapped to specific cells and a specific area of the brain.

That example did not seem to fit the bill as the paper predated the 2004 papers of Candes, Tao, Romberg and that of Donoho. As such it would not count as compressive sensing.

This was a little disheartening as many people were doing compressive sensing before 2004 (see The invention of compressive sensing) with potentially a link to Prony back to 1796. Further, the clock did not start ticking back in 2004 or 2006, rather it probably began ticking in 2008/2009. Indeed from 2004 till 2007, several measurement matrices allowed nonlinear recovery of sparse signals. In fact during that time frame, there was no technical way of figuring out a simple way whether a specific measurement matrix would allow generic recovery of sparse signals (RIP is NP-Hard to check). It is only in 2007/2008 that generic phase transitions were discovered and eventually we had to wait until 2011 to get even better measurement ensembles beyond strictly random gaussian ensembles. In short, the clock started ticking five years ago, not ten. Given all this background, 

Has there been any discovery or prediction that has been enabled by compressive sensing within the past five years that could not be predicted before ?

I can think of at least two examples:

Compressive ghost imaging by Ori Katz, Yaron Bromberg, and Yaron Silberberg

Why ? Up until that point, ghost imaging was thought to be related to quantum mechanics. Even though various tests were "proving" it was not a quantum mechanical effect, that paper put the last nail to that coffin: The effect is interesting but it ain't quantum mechanical, period.

Applying compressed sensing to genome-wide association studies by Shashaank Vattikuti, James J Lee, Christopher C Chang, Stephen D H Hsu, and Carson C Chow

Why ? because a least squares solver is incapable of enabling a prediction of the type given in that paper. Here thanks to the phase transition found by Tanner and Donoho, one can predict within the linear model how many people are needed to figure out a genetic connection to a specific trait. This is new. You can argue that the linear model is wrong but this is a prediction for that model. There is no similar prediction capibility for a least squares solver.

In the future, I personally think that the map makers are likely to be on the right track to make scientific discoveries.

If you feel that there is a discovery I did not mention, feel free to add your candidate to the comment section of this entry below or in this attendant LinkedIn discussion thread.

      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.