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.