Compressed Sensing: Stability Results for Random Sampling of Sparse Trigonometric Polynomials, Please help support USQ math department

In How to wow your friends, I used a simple dirac-sine family of measurement - dictionary functions to produce a simple but very telling example of reconstruction in the Compressed Sensing framework. It used BP (Sedumi). Holger Rauhut studied a similar case with a greedy algorithm and compared it with BP in Stability Results for Random Sampling of Sparse Trigonometric Polynomials. The abstract reads:

Recently, it has been observed that a sparse trigonometric polynomial, i.e. having only a small number of non-zero coefficients, can be reconstructed exactly from a small number of random samples using Basis Pursuit (BP) or Orthogonal Matching Pursuit (OMP). In the present article it is shown that recovery by a BP variant is stable under perturbation of the samples values by noise. A similar partial result for OMP is provided. For BP in addition, the stability result is extended to (non-sparse) trigonometric polynomials that can be well-approximated by sparse ones. The theoretical findings are illustrated by numerical experiments.

The companion Matlab Software Package is in this archive: omp4nfft.zip. I wonder how this type of greedy scheme could be accelerated because of the results of Meyer and Mattei.

Terry Tao is making a case for supporting the University of South Queensland Math Department in face of deep cuts. For all of you who feel that math education is a core subject in our Information Society, please consider supporting signing his online petition.