On the NIPS videos entry, I said:
"...Of particular interest is a question asked to Francis Bach at the end of his presentation where it looks like known bounds are O(p^6) whereas is own empirical experience seems to show an O(p^2) bound, mmmuh, a little bit like what happened in the 1970s' when the seismic folks thought the l_1 norm was a good proxy for l_0........"
To what a youngster commented:
"...I wonder if you'd be kind enough to elucidate what happened in the 70s for those of us not old enough to remember, and not well-versed enough in seismology?.."
I don't think I qualify for either of these statements, but I'll take them to mean that I know everything, muaaaahahahahahahah... Anyway, in seismology it was known since at least 1973 that l_1 minimization was promoting sparsity but nobody really knew why and what to make of it in the sense that none of the sensors were modified as a result of this finding. What the papers of Tao, Candes, Romberg  and Donoho  did was give a sense of the kind of acquisition that would be acceptable ( measurement matrix satisfying RIP, KGG....) which is the reason we can contemplate building hardware. From :
 E. J. Candès, J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59 1207-1223. (pdf)
 D. Donoho, Compressed Sensing
 Vivek Goyal, Alyson Fletcher, Sundeep Rangan, The Optimistic Bayesian: Replica Method Analysis of Compressed Sensing