CS: Providing insight on Compressive Sensing, GEOCAM

Sometimes, it is important to take a step back and provide to a wider readership some form of insight about compressive sensing. Let me do that today by connecting the dots between some entries on Nuit Blanche and elements found in the presentation slides of researchers in the field. On the slides for "Testing the Nullspace Property using Semidefinite Programming", Alexandre d'Aspremont, Francis Bach, Laurent El Ghaoui make the excellent point in slide 4 that:

• Sparsity is a proxy for power laws. Most results stated here on sparse vectors apply to vectors with a power law decay in coefficient magnitude.
• Power laws appear everywhere. . .

and this is indeed what I have tried to elaborate in the Sparsity in Everything series of entries. One the same subject, a new idea is also emerging that says that power-laws do not fit well with outliers particularly on the high end of it. Didier Sornette, in his recent arxiv preprint entitled Dragon-Kings, Black Swans and the Prediction of Crises thinks there is a positive feedback mechanism that produces even larger elements making them much sparser. Could compressive sensing be used to detect events with positive feedbacks out of the many unpredictable ones that fit a power law and therefore are much smaller in effects ?

Terry Tao also has a new presentation on Compressive Sensing where one can find this nugget:

An analogy would be with the classic twelve coins puzzle: given twelve coins, one of them counterfeit (and thus heavier or lighter than the others), one can determine the counterfeit coin in just three weighings, by weighing the coins in suitably chosen batches. The key point is that the counterfeit data is sparse.

It also looks like this example helps journalists and the public at large get the idea on group testing as the example is used in this article on Terry's series of lectures in Australia. You may recall a similar example and treatment here on this blog of that problem with balls instead of coins.

Further in the presentation, he also makes the more cryptic statement :

There are now several theoretical results ensuring that basis pursuit works whenever the measurement matrix A is sufficiently “incoherent”, which roughly means that its matrix entries are uniform in magnitude. (It’s somewhat analogous to how the secret to solving the twelve coins problem is to weigh several of the coins at once.)

Finally, on a totally different note, here is a presentation done by some NASA contractor folks that uses the same name as our 2005 GEOCAM project and uses the same concepts. Low tech cameras and an aerial capability can provide real time data in case of catastrophes. My students and I worked on this as a student project a little bit after what happened to New Orleans with Katrina. All the photos taken during that flight are here and were assembled using a low cost off-the-shelf software called Autopano Pro ( that uses SIFT markers) to produce these beautiful maps. Eventually, we never got any interest by other parties about what we had done. I am very glad the idea is continuing to live on.