Compressed Sensing: Chirp sensing codes a new deterministic measurement tool and Image Processing with Non-local Spectral Bases

A new update from the Rice Repository, where we have yet another deterministic construction of a measurement matrix by Lorne Applebaum, Stephen Howard, Stephen Searle and Robert Calderbank in Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery. The abstract reads:

Compressed sensing is a novel technique to acquire sparse signals with few measurements. Normally, compressed sensing uses random projections as measurements. Here we design deterministic measurements and an algorithm to accomplish signal recovery with computational efficiently. A measurement matrix is designed with chirp sequences forming the columns. Chirps are used since an efficient method using FFTs can recover the parameters of a small superposition. We show empirically that this type of matrix is valid as compressed sensing measurements. This is done by a comparison with random projections and a modified reduced isometry property. Further, by implementing our algorithm, simulations show successful recovery of signals with sparsity levels similar to those possible by Matching Pursuit with random measurements. For sufficiently sparse signals, our algorithm recovers the signal with computational complexity O(K logK) for K measurements. This is a significant improvement over existing algorithms.

Let us note the use of the statistics of the eigenvalues of the Gram matrices (made from the measurement matrix) "rather than a formulation of their bound" in oder to express some statement on the RIP constants. The measurement matrix is made up of a combination of chirps. The paper also prescribes a reconstruction technique as well. The reconstruction complexity is expected to scale as O(MK logK). From the conclusion:

This paper can serve as a preliminary read to [11] for those less familiar with Reed-Muller codes. Regardless of the above limitation, chirp sensing codes excel as method for fast signal recovery with compressed sensing.

In a different closely related area, we have an investigation of Image Processing with Non-local Spectral Bases by Gabriel Peyré. The abstract reads:

This article studies regularization schemes that are defined using a lifting of the image pixels in a high dimensional space. For some specific classes of geometric images, this discrete set of points is sampled along a low dimensional smooth manifold. The construction of differential operators on this lifted space allows one to compute PDE flows and perform variational optimizations. All these schemes lead to regularizations that exploit the manifold structure of the lifted image. Depending on the specific definition of the lifting, one recovers several well-known semi-local and non-local denoising algorithms that can be interpreted as local estimators over a semilocal or a non-local manifold. This framework also allows one to define thresholding operators in adapted orthogonal bases. These bases are eigenvectors of the discrete Laplacian on a manifold adapted to the geometry of the image. Numerical results compare the efficiency of PDE flows, energy minimizations and thresholdings in the semi-local and non-local settings. The superiority of the non-local computations is studied through the performance of non-linear approximation in orthogonal bases.

It is a long paper worth reading as it tries to connect traditional techniques to newer ones like diffusion methods that have also been used for dimension reduction and by the same token the building of sparse dictionaries.

The main contribution of this paper is that it bridges the gap between adaptive filtering methods and thresholding in adapted orthogonal bases. In order to do so, it reviews recent approaches to semi-local and non-local adaptive filtering of images. The use of thresholding in non-local orthogonal bases is suggested in [50] and we further study the properties of such thresholdings. The connexions with more traditional wavelet-based and total variation algorithms is made clear together with a study of the pros and cons of each method.