Friday, October 16, 2009

CS: Food for thoughts for the week-end.

Before all of you go home for the week-end, let me add one more thing to the entry of yesterday and then some. Even though I suck, I don't think I am the only one who is going to save that entry, print it and parse it over the week-end. Looks like Giuseppe Paleologo is going to do the same but I am sure we won't be the only ones. Giuseppe added the following in the comment section of yesterday's entry:

I have to say that it's quite amazing that a tweet I shot to Igor cascaded in two detailed replies from none other than Jared Tanner and Remi Gribonval. Thanks to Jared for the nice geometric intuition provided for the NSP. I still have to digest his comment, and his recent paper with Blanchard and Cartis.

Briefly, I should mention that the question of RIP vs NSP is interesting to me because in statistical applications where A is observational, RIP is not obviously satisfied. However, even when it is not satisfied, l1 minimization or lasso perform well, so possibly there is a different explanation for their success. In this respect, I am especially interested in stable recovery under the two assumptions.

I have been reading some papers and presentations by Remi, and have been thinking about his statement: "however the RIP seems necessary to guarantee robustness to noise" (which appears in the recent IEEE paper). In most papers this seems to be the case, because stability depends obviously on the metric properties of the encoder, which RIP captures. The (lone?) exception is a recent paper of Yin Zhang (http://www.caam.rice.edu/~zhang/reports/tr0811_revised.pdf), which characterizes stability not using RIP or the canonical NSP, but still in terms of projections on the null space. The quantity of interest in that analysis is the value of (||x||_1/||x||_2) for x \in N(A), which is different from NSP......
thanks Giuseppe !

By the way, don't miss Giuseppe's very interesting entry (and the comments) on being an Intern at Enron. As a person who was nearby Houston at that time, it really looked like some of the people who worked there, either did not have a clue about the real business of Enron or were fooling themselves in believing that some part of their business was actually making money. I do not know if I was the only one, but I clearly remember something was terribly amiss when Jeffrey Skilling had an interview on the Houston Chronicle saying he wanted to retire to spend more time with his family, that was August 15th 2001.

Returning to RIP vs NSP, I'll add on top of Giuseppe's comment that one of the most important step for an engineer to convince herself/himself that compressive sensing might be a good thing for her/him, revolves around trying to fit their known "measurement" device to the CS setting. An example of that was recently featured in TomoPIV meets Compressed Sensing by Stefania Petra and Christoph Schnörr or in the approach I am suggesting when we 'only' have integro-differential equations for which we have some knowledge about computing eigenfunctions fo said operators. Let us note also the fact that NSP can also include a more specific class of signals: positive signals.

I think, at some point, I am also going to have to write down what some of you have been saying to me about the spectral gap of sparse measurement matrices in the RIP-1 setting and its potential relationship to the eigenfunctions of that operator. In particular my interest is in finding out if there is a relationship between the non-normality of a measurement operator and its potential to be a good/bad expander and how this influence their goodness or badness for doing CS with them. All this is highly speculative.

Unrelated to this, two entries by David Brady got my attention recently:
Finally, let us recall that the focusing using random materials and different combinations of an SLM take about 30 minutes to perform according to Ivo Vellekoop's PhD thesis. Could any of the solvers used in CS reconstruction enable a faster focusing ? I bet they would.



While we are on the subject of random lens cameras, I wanted to talk about this a while back, but I have not had the time to do so, so I am leaving it as a food for thought for the week-end. The good folks at MIT (the Photonics Bandgap Fibers and Devices Group under the leadership of Yoel Fink) have devised a camera based on fiber optics. The interesting technology has pieces of metal inside the fiber optic that allows outside objects to shine directly into the light path of the fiber optic so that it is eventually channeled eventually at some common point down the fiber. In effect, this is a multiplexing operation and one could have this fiber optics pipes woven inside apparels to provide some "random" measurement of the surrounding. Since the cloth follows the movement of the body, one can only imagine how the work in signal manifolds would fit in. Some more information on the MIT technology can be found here and in the reference below.

As you all know, I am very much interested in developing a dirt cheap Compressive Sensing application for the purpose of making CS more "obvious" to the average tinkerer/maker. Hence, I wonder how expensive or inexpensive one could fabricate something equivalent to these fibers ? anybody know ? maybe randomly scratching normal fibers to let light come in, that doesn't sound too bad of an idea. The problem being that one wants to avoid breaking these fibers.

Finally, the stunning (in detail) first photo of this entry was taken from the international space station by one of the astronauts. Could we have a different lens mount and perform the equivalent of a random lens imaging experiment with them ? If you are interested we need to talk about an opportunity like this with Nanoracks (you won't see a mention of it on the web yet).


Reference: Abouraddy, A.F., Shapira, O., Bayindir, M., Arnold, J., Sorin, F., Saygin-Hinczewski, D., Joannopoulos, J.D., Fink, Y., "Large-scale optical-field measurements with geometric fibre constructs", Nature Materials 5, 532-536 (2006). [Full Text (pdf)]

Credit:
1 st/2nd Photo: NASA/Bill Ingalls, photo taken from the international space station, 300 km above the scene of interest (the landing of the Soyuz spacecraft in Kazakhstan). Photo taken with one of these instruments on board.
3rd Photo: NASA/JPL/University of Arizona, USGS Dune Database Entry (ESP_014426_2070), Photo taken by the Hirise camera of some of Mars' dunes. (via the Bad Astronomy blog).

No comments:

Printfriendly