CS: Answering a DSN question, Distilled Sensing, Modified-CS: Modifying CS for Problems with Partially Known Support, L1 and Hamilton-Jacobi

Responding to yesterday's question by Angshul Majumdar, Waheed Bajwa provided the following answer on Dsitributed Sensor Networks and Compressive Sensing:

...We have in the past investigated the use of compressed sensing in distributed sensor networks in precisely the setting mentioned by Angshul;

the relevant partial results can be found in our IPSN 2006 and ICASSP 2006 papers, while a comprehensive collection of all our related results can be found in our IT Trans 2007 paper. I believe that these papers collectively answer the points raised by Angshul in terms of the usage of CS-based encoding in sensor networks.

In particular, the upshot of our results is that if one has enough prior knowledge about the sensor network data then using that prior knowledge in encoding the data is superior to CS-based encoding in terms of power-distortion-latency metrics. But if one does not have enough prior knowledge about the underlying data then using CS-based encoding can be strictly superior to using a mismatched encoding mechanism. Further, CS-based encoding gives one the ability to design universal encoding mechanisms that need not be changed with the underlying data, but the price that one has to pay is in terms of the performance as compared to data-specific encoding---an observation that we term as the "universality vs prior knowledge trade-off".

Finally, note that whether one uses CS-based encoding or not, the end result is always better than sending individual measurements from each sensor independently. Angshul remarks regarding energy usage do not apply here since he is not taking into account the power pooling gain that one gets out of beamforming data from the sensors. This is explained in quite a detail in our IT Trans 2007 paper.

Bottom line: Using CS-based encoding in sensor networks is typically going to be better than making sensors send individual measurements to a central fusion center. Whether or not this is the best thing to do though depends upon whether or not we can get reliable prior information regarding the signal field of interest.

Thank you Waheed !

Jarvis Haupt just me the following:

I posted a slideshow example of the Distilled Sensing procedure recovering a sparse signal in one dimension. Here's the link:

http://homepages.cae.wisc.edu/~jhaupt/files/DS_example.pdf

also at www.distilledsensing.org

The observations collected at each step of the procedure are shown, along with the set of locations to be observed in the next step and the "retention" of the procedure (calculated clairvoyantly) which quantifies the fraction of true signal components and null components that are retained by thresholding at each step, as well as the overall retention.

Thanks Jarvis !

Here what I found on the interwebs:

Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support by Namrata Vaswani and Wei Lu. The abstract reads:

We study the problem of reconstructing a sparse signal from a limited number of its linear projections when a part of its support is known. This may be available from prior knowledge. Alternatively, in a problem of recursively reconstructing time sequences of sparse spatial signals, one may use the support estimate from the previous time instant as the “known” part of the support. The idea of our solution (modified-CS) is to solve a convex relaxation of the following problem: find the sparsest possible signal that satisfies the data constraint and whose support contains the “known” part of the support. We derive sufficient conditions for exact reconstruction using modified-CS. These are much weaker than those needed for CS, particularly when the known part of the support is large compared to the unknown part.

and not necessarily CS but close here is: Jean-.Luc Guermoind, Bojan Popov, An Optimal L1-Minimization Algorithm for Stationnary Hamilton-Jacobi Equations. The asbtract reads:

We describe an algorithm for solving steady one-dimensional convex-like Hamilton- Jacobi equations using a L1-minimization technique on piecewise linear approximations. For a large class of convex Hamiltonians, the algorithm is proven to be convergent and of optimal complexity whenever the viscosity solution is q-semiconcave. Numerical results are presented to illustrate the performance of the method.

from the conclusion

We have shown in this paper that it is indeed possible to approximately solve the minimization problem (2.13) in O(N) operations for one-dimensional stationary Hamilton-Jacobi equations. This confirms the idea that L1-based approximation techniques are not only optimal from the theoretical point of view (i.e., they naturally yield viscosity solutions without adding artificial viscosity), but they can also be made computationally practical and optimal complexity is achievable.

Image Credit: NASA/JPL/Space Science Institute, Dione as seen by Cassini three days ago.