Sunday, January 23, 2011

Islands of Knowledge

[Yesterday's poll is at the end of this entry.] [Update: I have highlighted the most important part of a sentence]

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 [1] and Donoho [2] 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 [3]:




[1] 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)
[2] D. Donoho, Compressed Sensing
[3] Vivek Goyal, Alyson Fletcher, Sundeep Rangan, The Optimistic Bayesian: Replica Method Analysis of Compressed Sensing

3 comments:

Anonymous said...

Dear Igor

"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"

I respectfully disagree
1) L1 in seismic was for deconvolution, nothing to do with CS.
2) The "Golden Oldies" section of Donoho's publications is worth reading, in particular "Superresolution via Sparsity Constraints", "Uncertainty Principles and Signal Recovery". It is quite clear that even in 1990 Donoho's understanding of L1 (and other sparsity promoting functional like entropy) and his relation with L0 was almost perfect.

Igor said...

Hello,

You seem to be arguing about the first part of the sentence, but are you sure you are arguing about the second part of that sentence (which is really the point I was making) ? Namely:

"..in the sense that none of the sensors were modified as a result of this finding.."

Cheers,

Igor.

flex said...

Actually, the paper most frequently referred to in this context is the paper by

Claerbout, J. F., and Muir, F., 1973, Robust modeling with erratic data: Geophysics, 38, no. 5, 826-844,

which deals with alternatives to least-squares modeling of data. I believe one can find in this paper the following quote:

“When a traveler reaches a fork in the road, the 11-norm tells him to take either one way or the other, but the l2 -norm instructs him to head off into the bushes.”

Printfriendly