RIP, not RIP - a little bit on compressed sensing

Shall the Restricted Isometry Property (RIP) Rest In Peace (RIP again)?

This afternoon, Albert Cohen presented recent findings (made with Wolfgang Dahmen and Ronald DeVore) on Compressed sensing and best k-term approximation. These findings pertain to the fields of compressive sensing (CS, see Nuit Blanche for some live coverage) and non-linear approximation (NLA), namely: how do fixed linear measurements (CS) and adaptive linear measurements (NLA) compare for signal approximation in the lp norm? Both in a deterministic and a probabilistic fashion. A. Cohen nicely reviewed some references on the topic, including the interesting FRI (Finite Rate of Innovation) by Per Luigi Dragotti and Martin Vetterli (et al.), nicely covered here (we come back later on this approach) and the compressive sensing resources. He emphasized an approach based on decoupling (1) the information quantity and (2) the algorithms. The basic question is: given some unknown x, presumably sparse, linearly observed via y = Px, find a decoder D (generally non-linear) such that D(Px) is close enough to x. (P,D) is characterized by some "instance optimality" property. The work focuses on the characterization of the null space ker(P), since it essentially measures P's ambiguity in recovering a sparse x from y. The existence of the decoder is related (Lemma 3.1 from Compressed sensing and best k-term approximation) to the injectivity of P and to the relative spread of ker(P). Compared to Candès-Tao-Romberg Restricted Isometry Property, this approach differs both in the algorithmic approach and in its stability. It is important to mention, that the "ker" (null space) point of view still applies when x = Ms is a quasi-sparsified (through a wavelet transform for instance) version of some signal s, while PM would not satisfy RIP, P would.

Coming back to Finite Rate of Innovation. A signal band-limited in [-1/2 1/2] is perfectly reconstructed with at least one uniform measurement per period of time, through a cardinal sine kernel. Which may be considered as an innovation rate per time unit. While the Nyquist-Shannon condition is sufficient, it is not necessary. FRI derives conditions, based on parametric hypotheses on the signals (e.g. formed with p diracs per time period), for perfectly reconstructing signals after an acquisition made of a sampling kernel followed by uniform sampling. Interestingly, in contrast to standard CS, the sparsity in FRI resides in a continuous domain, and not in a discrete one. This seems somewhat more natural. On the other hand, non-uniform sampling is more efficiently dealt with CS.

For recent accounts on FRI:
Estimating Signals with Finite Rate of Innovation from Noisy Samples: A Stochastic Algorithm, by Vincent Y. F. Tan, Vivek K. Goyal
Compressive Sampling: Sparse Sampling of Signal Innovations, by Thierry Blu, Pier-Luigi Dragotti, Martin Vetterli, Pina Marziliano, Lionel Coulot
Nuit Blanche of the above paper
Nuit Blanche in Neutron transport (very cold neutrons?)