CS: Sparse Recovery Experiments: RIP-1 matrices, Sparse Matching Pursuit and Countmin compared to L1-magic and GPSR.

Piotr Indyk and Radu Berinde just made live a wiki on Sparse Recovery Experiments. As noted in the introduction:

This page contains the Matlab/C toolkit we used to get experimental results for sparse recovery using sparse matrices, reported in ^BGIKS08,^BIR08 and ^BI08. The code provides the following functionality: 

(i) given an n-dimensional vector x, compute its m-dimensional sketch Ax, where A is an mxn sketch matrix, m much less than n, and 

(ii) given a sketch Ax, recover a k-sparse approximation x* of x. In addition, the code provides subroutines for generating test vectors x and sparse matrices A.

The toolkit supports the following recovery algorithms: Sparse Matching Pursuit (SMP), Countmin and L1 minimization (although one needs to download either l1-magic or GPSR to use the last option).

These are important experiments as they show the capability of RIP-1 measurement matrices and the attendant specific recovery algorithms (Sparse Matching Pursuit and Countmin). I am adding the link to the measurement matrix section as well as the reconstruction section of the big picture. One of the findings is that the recovery might be much faster for a dedicated matching pursuit algorithm but one needs a higher number of measurements to have the same probability of reconstruction as compared to other algorithms like GPSR and l1-magic. And so while this finding may look like a bad thing, let us also look at the positive side of things: If implemented on hardware, these sparse RIP-1 matrices would seem to provide an advantage in terms of a small dynamic range.