Compressed Sensing: Utilizing Sparsity in Compressed Sensing Reconstruction Algorithms

I have tried the Sparse Measurement Matrices of Radu Berinde and Piotr Indyk on a restricted set of examples. It seems to work as well as random Gaussian matrices. I have implemented a function that implements these matrices here. I used both l1-Magic and the re-weighted Lp reconstruction techniques and both yield similar results. However, currently none of the solvers take advantage of the fact that these matrices are sparse. For the re-weighted Lp technique, one can speed up the reconstruction fairly easily using the sparse function of Matlab since the full algorithm implementation takes about 10 lines. But we also know that the re-reweighted Lp scheme is also slow, so the generic question is, besides L1-Magic (for which Radu Berinde and Piotr Indyk have done an implementation)

How can any of the current reconstruction solvers listed below utilize the sparsity of the measurement matrices ?

• SparseLab
• GPSR
• ell-1 LS: Simple Matlab Solver for ell-1-Regularized Least Squares Problems
• sparsify
• SPGL1: A solver for large scale sparse reconstruction
• Regularized OMP
• TwIST

[Update: Duh, the answer is simple, instead of defining the matrix, one has to define a way to compute Ax and A'x through a function handle. Most of these softwares handle this. It goes to say I should not be posting late at night]

Source: Rice Compressed Sensing repository