CS: Compressed Sensing Big Picture, a Blog entry, Learning Dictionaries While Solving, Several presentations.

Anna Gilbert mentioned to me that the listing of the different measurement / encoding means used in Compressed Sensing as listed in the big picture was, maybe, a little confusing. I was in the middle of reordering that listing following the comments by Piotr Indyk so I welcomed additional inputs:

I was reading today's blog entry and thought I should point out Mark's Fourier papers. Mark Iwen has two papers on deterministic subsampling algorithms for sublinear time (i.e., faster than optimization) Fourier recovery. His results handle noisy signals, not just k-sparse ones. The main drawback of the construction is that it scales like k^2 polylog(n), rather than k polylog(n). But, it is sparse and the associated algorithm is fast. His second paper goes through the number theory to show that with prime group tests, you can't get smaller than k^2 polylog(n).


1. M. A. Iwen,
A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods, ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA,
(2008).
2. M. A. Iwen & C. V. Spencer, Improved Bounds for a Deterministic Sublinear-Time Sparse Fourier Algorithm, Conference on Information Sciences and Systems (CISS), Princeton, NJ,
(2008).

These two articles were already there but at the wrong locations. So after some rearranging, Anna further commented:

The classification is getting better although upon further scrutiny, I can see the possibilities for further rearrangements:

non-deterministic, non-adaptive
non-deterministic, adaptive
deterministic
a. Fourier <-> spike bases
b. other

Basically, my point is that some of the deterministic constructions are for measuring in the spike basis and recovering in the spike basis (or measuring using special kerdock code vectors and reconstructing in some other basis) or measuring in spike and recovering in Fourier (and vice versa) and your categorization seems restricted to Fourier and spikes. Fourier and spike are, of course, special bases as they are natural, they're mutually as incoherent as can be, etc. With such a categorization, you can then include Cormode and Muthukrishnan's work on deterministic, combinatorial approach to compressed sensing under other bases and you'll have a more balanced view of the literature.

I need to include the papers of Cormode and Muthukrishnan in the Big Picture measurement section but if like Anna or Piotr you feel strongly about how some instances of what is written in the big picture or on this blog need to be presented in a different fashion then please let me know. I even get to modify the offending lines quicker if there are suggestions on how to make it better.

I am also trying to clean up the section on hardware. It is somehow difficult and I am wondering if I should not use the Technology Readiness Level (TRL) scale to put some order there. For instance, work on MRI is going very fast whereas other type of imaging are still at their infancy. Then again, other technologies, while not doing CS per se, are already doing some type of subsampling that, if twisted a little could be considered CS and could be using nonlinear CS reconstruction techniques.

In other news, Petar Maymounkov has a blog entry on Compressed Sensing or more specifically, on the use of dictionaries that are eventually needed to decode compressed measurements. It led me to one paper by Guillermo Sapiro and Hstau Y. Liao entitled Sparse image representation for limited data tomography. The abstract reads:

In limited data tomography, with applications such as electron microscopy and medical imaging, the scanning views are within an angular range that is often both limited and sparsely sampled. In these situations, standard algorithms produce reconstructions with notorious artifacts. We show in this paper that a sparsity image representation principle, based on learning dictionaries for sparse representations of image patches, leads to significantly improved reconstructions of the unknown density from its limited angle projections. The presentation of the underlying framework is complemented with illustrative results on artificial and real data.

What is interesting in this approach is that the dictionary is learned (using K-SVD) while the nonlinear reconstruction process is taking place. I don't think I have seen that before in CS yet.

Finally, there are several presentations related to Compressed Sensing just sprung up on the web:

• Large Scale Approximate Inference for Bayesian Image Reconstruction and Measurement Design by Matthias W. Seeger and,
• Compressed Sensing by Wolfgang Dahmen
• All the presentations made at Journée représentations parcimonieuses du GDR ISIS are now available. Some are in French and some in English. They are all very interesting. Of the ones I could attend, I have already mentioned this one and this one. Following up on that François Malgouyres makes available his code performing the Basis Pursuit Denoising using one of these proximal solvers (PPA).

Credit: NASA/JPL/University of Arizona, Descent of the Phoenix Lander (PSP_008579_9020), picture taken autonomously by a robot (Mars Reconnaissance Orbiter (MRO) /HIRISE camera) of a robot (Phoenix) as it falls on Mars. wow.