Stability results for random sampling of sparse trigonometric polynomials

Abstract

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.

Slightly improved estimate for restricted isometry constants, some numerics added

References in corpus (5)

• Sparsity and Incoherence in Compressive Sampling
• Concentration around the mean for maxima of empirical processes
• Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
• Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit
• Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit

Cited by in corpus (4)

• Identification of Matrices having a Sparse Representation
• Weighted eigenfunction estimates with applications to compressed sensing
• Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit
• Compressive sensing: a paradigm shift in signal processing