Compressed Sensing: The Framework

[Update: This entry is now superseeded by this more complete web page trying to build the Big Picture on Compressed Sensing (also here) ]

Sometimes I lose track of this, but Compressed Sensing is really about acquiring a sparse signal with the help of an incoherent basis. While much of the emphasis is rightfully about reconstruction work, we are beginning to see the emergence of other tools that complete this framework. Two other stages are emerging:

• the search for bases or dictionaries in which a set of signals are sparse in and,
• specific incoherent measurements tools.

Algorithms already implemented that find sparse dictionaries are presented in:

• Multiscale sparse image representation with learned dictionaries
• Efficient sparse coding algorithms
• Non-negative Sparse Modeling of Textures (NMF)
  

Knowledge of specific domain signals enables the ability to build these hopefully small dictionaries. The next step will almost certainly bring about techniques that find elements within a manifold as opposed to a full set of functions, some sort of Data Driven Dictionary.

Non Adaptive Measurement codes/matrices (the first four are pasted from Terry Tao site):

Random Fourier Ensemble: The signal is a discrete function f on Z/NZ, and the measurements are the Fourier coefficients at a randomly selected set Omega of frequencies of size M ( A is an M x N matrix.)

Gaussian ensemble: A is an M x N matrix (M x N Gaussian variables).

Bernoulli ensemble: A is an M x N matrix (M x N Bernoulli variables).

Gaussian ensemble: A is an m x n matrix (m > n) whose measurement coefficients are Gaussian variables.

Other recent implementations achieving specific goals (sparsity,....)

• Sparse Measurement Matrix (implementation is mine, but real code available from the authors).
• Noiselets
• Random Filters (from here)
  

Obviously, with the advent of Data Driven Dictionnaries, we will have specific domain specific measurement matrix methods. Also, I am sure I am missing some implementation from the sketching world and I guess I should also list the adaptive schemes.

Reconstruction codes - Matching Pursuit/Greedy, Basis Pursuit/Linear Programming, Bayesian -

• l1-Magic
• SparseLab
• GPSR
• ell-1 LS: Simple Matlab Solver for ell-1-Regularized Least Squares Problems
• sparsify
• MPTK: Matching Pursuit Toolkit
• Bayesian Compressive Sensing
• SPGL1: A solver for large scale sparse reconstruction
• FPC
• Chaining Pursuit
• Regularized OMP
• TwIST
• Lp_re, Reweighted Lp - This my implementation but a better one might be available from the authors.
  

Eventually, the end point is the birth of specific hardware implementations of these schemes ([L1], [L2],[L3],[L4],[L5],[L6], [7], [8]). The most salient features of the random or noiselet measurements is that one can foresee a hardware implementation without having to know the decomposing sparse basis since there is a high probability that these two will be incoherent with each other.

[ Update: some of the homemade codes are here]



Credit: I have cut and pasted section of this entry directly from the Rice repository, Terry Tao site. NASA Mars rover Opportunity on Sol 1432.