When is Inpainting an Instance of Weak Compressed Sensing ?

Here is my question: When is inpainting an instance of weak compressed sensing ? By weak compressive sensing, I mean that the sampling process is a multiplexing of sorts but it is "weak" in that the  contribution of the multiplexing is small compared to one single element. To make this "definition" clearer:

• a weak compressive sensing measurement matrix that can be thought as a selection of rows of the sum of the identity matrix and an epsilon times a gaussian matrix.
• a measurement matrix for strict inpainting would be a selection of rows of the identity matrix.

This is a discussion that started earlier this year as an extension of the example coming out of the Wired article. I wrote about it in Compressed Sensing or Inpainting ? Part I and in Compressed Sensing or Inpainting, part II. In that last entry, I mentioned

...This is why I wrote this example in Compressed Sensing: How to wow your friends back in 2007 that features an example with delta and sines. Let us note that in Compressive Sensing Audio, for the delta/sines assumption to hold, you really need have to sample enough within time-localized phenomena. In other words, Compressed Sensing is not a license to make appear something you did not catch with the sampling process. This needs to be said often, as in MRI or steady-state audio, the signal is being sampled with diracs in their appropriate phase spaces (Fourier for MRI and time for Audio) that will get you a result directly applicable by a compressive sensing approach. In other fields like imagery however, you do not sample directly in a good phase space and you need new types of exotic hardware to perform these new types of incoherent measurements...

then I asked the question

Is your average point and click camera with missing pixels a compressive sensing system ?

And finished the entry with:

 Eventually the question is "are lower quality cameras or microphones "weak" compressive sensing systems " ? More to come later...

Yesterday, the thought crossed my mind as I was reading the paper on a microscope that can achieve superresolution but that looks like, and is claimed to be, strict inpainting. We have had similar occurrences before. (they are listed below:) At the heart of  this issue is the question of whether the reconstruction involves information that has been acquired incoherently (CS) or information that is made up but is simple enough:

Here are occurences of strict inpainting, whereby data have been synthetically removed or cannot have been acquired in the first place:

• When is missing data recoverable? by Yin Zhang
• The magnificient recolorization example featured in the Compressive Sensing by Massimo Fornasier and Holger Rauhut
• Speech inpainting in Using sparse representations for missing data imputation in noise robust speech recognition by Jort Gemmeke and Bert Cranen
• Frequency inpainting:  SparSpec : a new method for fitting multiple sinusoids with irregularly sampled data, Sebastien Bourguignon, Hervé Carfantan and Torsten Böhm
• The Obama Picture in the Wired article by  Jarvis Haupt
• Compressive Sensing Audio by Laura Balzano, Robert Nowak and Jordan Ellenberg featured in the recent NPR piece

These are all synthetic cases, but in the case of a real hardware like the superresolution microscope (featured in Far-Field Microscopy of Sparse Subwavelength Objects by Alexander Szameit, Yoav Shechtman, H. Dana, S. Steiner, S. Gazit, T. Cohen-Hyams, E. Bullkich, O. Cohen, Yonina C. Eldar, S. Shoham, E. B. Kley, M. Segev. and  Super-Resolution and Reconstruction of Sparse Sub-Wavelength Images by Snir Gazit, Alexander Szameit, Yonina Eldar, Mordechai Segev.,) are we seeing an instance of:

• Strict inpainting: Information at the smallest scale is irretrievably lost as the authors claim , or
• Weak Compressive Sensing: i.e. some of the smaller scale information is included in the "low resolution" performed by the microscope and is therefore there for use by the reconstruction process.

In this case, the answer seems to be the second option. From the strict inpainting examples above, we know that the l_1/l_0 solvers bring back some level of reasonability but at what point, an analog device like the microscope is taking up information that eventually provides better than reasonable information as opposed to simply a reasonable expectation ? The answer may lie in the calibration process.


Image Credit: NASA/JPL/Space Science Institut, N00164124.jpg was taken on October 08, 2010 and received on Earth October 10, 2010.