Compressed Sensing: Figuring out the Compressibility of a Signal or Dataset

As I am adding elements in the Big Picture section on Compressed Sensing, I have come to appreciate how some subjects eventually have a connection to CS. Case in point, in the description of the framework, while reconstruction is focusing most of our attention, a definite area of interest also includes recognizing that the signal of interest can be sparse in some basis. As we all know, Compressibility or sparsity of the signal/dataset is a prerequisite for CS.

While some of us are lucky to have a good idea of what those bases are, others are left with tensor products of wavelets in the hope of finding something relevant to their areas of expertise. So the question to them is to either keep finding bases through the eigenfunction expansion of the underlying physics operator of the phenomena at hand or ... use recent Machine Learning techniques to build those. The question we are trying to answer is: How do you find dictionaries of functions that will lead you to have signals that are compressible in them ? Here are the three categories I have been able to make up while surveying the subject. I am open to more enlightment on the subject.

1.1 Basis Functions for which signals are either sparse or compressible

This is the lucky case and the subject of much investigation in the literature.

• Fourier, Polynomials, etc...
  
• All kinds of wavelets and higher dimensional related functions (like Curvelets, Ridgelets, Countourlets,....) through nonseparable forms or through the use of tensor-products of these functions. Laurent Duval has a an encyclopedic listing of the most recent functions at Where is the Starlet.
  

1.2 Algorithms that find sparse dictionaries

These algorithms are pretty new and are likely to grow as some of them are being used in areas of robotics and hyperspectral imaging where historically no known bases are known in advance:

• Dictionary Learning Algorithms for Sparse Representation (Matlab implementation of FOCUSS / FOCUSS-CNDL is here)
• Multiscale sparse image representation with learned dictionaries [Matlab implementation of the K-SVD algorithm is here]
  
• Efficient sparse coding algorithms [ Matlab code is here ]
• Non-negative Sparse Modeling of Textures (NMF) [Matlab implementation of NMF (Non-negative Matrix Factorization) and NTF (Non-negative Tensor), a faster implementation of NMF can be found here]

Let us note the Matlab Toolbox Sparsity by Gabriel Peyre that has some of these techniques implemented (but no good readme file :-))

1.3 Data Driven Dictionaries

I am not sure there is a good separation between Algorithms that find Dictionaries in which data are sparse/compressible in (1.2) and Data Driven Dictionaries (1.3) where one constructs a set of eigenfunctions on a set of high dimensional data and hope that the decomposition at every point will yield few large coefficients. The idea here is to build some harmonic analysis on the manifold, in short functions on a manifold that have the property of bringing about dimensionality reduction. In this setting, one can list:

• Geometric harmonics (as demoed here)
• Diffusion Wavelets

There are not different approaches rather one is an extension of the other. Let us note that random projection of data that belong to a manifold are using, albeit without being stated as such, the fact that these geometric harmonics and random functions are incoherent with each other (not unlike the 1-d example featured here). Writing on Random Projections of a manifold in high dimension generally do not point this out because in this case, we either do not have the computational ability nor the interest to reconstruct the "original" dataset.

But why should we care about high dimensional signals in imagery for instance?

One should also note that sometimes, an image (2-D dataset) is not just a unrelated collection of (pixel) values which happen to be presented in a 2-d shape. Sometimes, one is interested in the fact that elements in that 2-D array have some underlying connection or statistics to each other. In the Machine Learning community interested in machine vision, one is generally trying to use that fact by projecting these 2-d information into an N-D space with N in the realm of 1000's. Akin to hyperspectral imaging, now every "pixels" contain thousands of information relating to their neighborhood. These superpixels are then projected back into low dimension using dimensionality reduction techniques such as geometric harmonics in order to bring about parameters like depth ( It is important to figure out the limitation of this type of exercise).

Why am I saying this ? Because it seems to me that while some would feel comfortable dealing with curvelets in two dimensional imaging application, it is also becoming more obvious that when performing random projections of these high dimensional datasets, one keeps the relevant data/statistics (see the hyperspectral imaging work of Coifman) and that it might become more interesting to project up these 2-D image first. At which point, either Geometrics Harmonics or Non-Negative Tensor Factorization might be the only way to go about finding the sparse dictionary of this high dimensional space.

A point I have not seen in the literature is the potentiality of dictionaries to be specific to the hardware gathering the data.

Let us finally note that in the case of random projections, these sparse dictionaries are really useful for the reconstruction of the signal, and in some cases we don't care as much even though it is the only way to figure out if we have kept that information through the random projection process.

Credit photo: NASA / JPL / U. Arizona, Active avalanche on Mars as caught by the Hirise Camera. Via the planetary society blog