CS: Recovering Lost Sensor Data through CS, A Question to Anders Hansen

You nay recall Zainul Charbiwala's question on computing the Restricted Isometry Constant (part 1, part 2, part 3, part 4). Well he just gave a talk entitled Recovering Lost Sensor Data through Compressed Sensing on January 15th. The abstract read:

Data loss in wireless sensing applications is inevitable, both due to communication impairments as well as faulty sensors. We introduce an idea using Compressed Sensing (CS) that exploits knowledge of signal model for recovering lost sensor data. In particular, we show that if the signal to be acquired is compressible, it is possible to use CS not only to reduce the acquisition rate but to also improve robustness to losses.This becomes possible because CS employs randomness within the sampling process and to the receiver, lost data is virtually indistinguishable from randomly sampled data.To ensure performance, all that is required is that the sensor over-sample the phenomena, by a rate proportional to the expected loss.

In this talk, we will cover a brief introduction to Compressed Sensing and then illustrate the recovery mechanism we call CS Erasure Coding(CSEC). We show that CSEC is efficient for handling missing data in erasure (lossy) channels, that it parallels the performance of competitive coding schemes and that it is also computationally cheaper. We support our proposal through extensive performance studies on real world wireless channels.

The slides are here. I note the use of the trademarked words "big picture - compressed sensing" :-)


Back when I read about by Anders Hansen's article on Compressive Sampling in Infinite Dimensions several days ago, Because he has done some work on pseudospectra and I broached on the subject here before, I went out and asked him the following dumb question:

... I just noticed your work on CS in infinite dimensional spaces. I also noticed from your publication your interest in non-normality. I have a really dumb question for you. As you know, at some engineering level, people want to know if their underdetermined systems found through the discretization of the physics of their problem could fall into something accessible to CS. There are current attempts undertaken by different researchers to look for a way to computationally check if a sufficient condition based on the RIP or the nullspace condition is checkable in a relatively fast fashion. However these condition checking exercises fail when the matrices become large.

Here is my really dumb question, do you know if there is some type of connection between the pseudo-spectrum of a linear operator and any of the conditions (RIP, KGG, NullSpace) required for finding sparse solutions using l1 minimization (the typical CS problems.)

Anders Hansen very kindly responded with the following:

...Thanks so much for your interest in my work. I must apologize for the late replay, but I have been traveling. The question you ask is certainly not dumb, in fact the answer is not obvious at all. However, before I continue with the question let me mention that the RIP condition is a very strong requirement. In fact in most of the reconstruction problems that I encounter, that is never satisfied, but reconstruction is still possible. It is really the randomness of the measurements that allow for this. If you check out my paper on this you'll see that there is no mentioning of the RIP and there are other conditions (much weaker) that one has to check in order to get recovery (these can also be checked numerically). Anyway, there are tons of work to be done on this.

Now for the pseudospectrum question. This must be investigated, but my gut feeling is that there is no obvious connection. Consider the following problem. Let A be a self-adjoint and U the discrete fourier tranform (DFT). Now U is unitary and by randomly choosing row from U (how many one must choose depends on the sparsity and the dimension of the space) it is likely that one can recover a sparse signal (or even get the RIP), but it is the incoherence of the DFT that is crucial. Now U is unitary, so normal, hence the epsilon-pseudospectrum is just the epsilon neighborhood around the spectrum. Also, A is self-adjoint thus the pseudospectral qualities are the same as for U, however A may very well be the identity, and that will not be useful for any recovery purpose. Thus, one can have two operators with very different recovery properties and same pseudospectral qualities. Now this example does not say that there may not be any information from the pseudospectrum. Consider two operators with the same incoherence and different pseudospectrum. Can one deduce something from that observation. I don't think so, but as I say, this is not obvious. The reason why I am slightly sceptical is that incoherence depends on the choice of basis. Pseudospectra do not change by changing the basis.

So it looks like this was a dumb question, except maybe if one put some constraint on what to look for in the pseudospectrum.... Thanks Anders !

As it turns out both items in today's entry are about the RIP....

Bon Voyage Papa