Stability Results for Random Sampling of Sparse Trigonometric Polynomials

DOI10.1109/TIT.2008.2006382MaRDI QIDQ3604925zbMATH OpenFDO

Authors Holger Rauhut

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609630

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Trigonometric approximation (42A10) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Numerical methods for discrete and fast Fourier transforms (65T50) Sampling theory in information and communication theory (94A20)

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.

Recommendations

• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Random sampling of sparse trigonometric polynomials
• Deterministic sampling of sparse trigonometric polynomials
• Stable signal recovery from incomplete and inaccurate measurements
• Sparsity and incoherence in orthogonal matching pursuit

Cited in

(19)

• Compressive Sensing
• The road to deterministic matrices with the restricted isometry property
• Sparse approximation of fitting surface by elastic net
• Sparse approximate solution of partial differential equations
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Spark-level sparsity and the _1 tail minimization
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Embracing off-the-grid samples
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• Probabilistic spherical Marcinkiewicz-Zygmund inequalities
• Sparse high-dimensional FFT based on rank-1 lattice sampling
• Sparse approximate solution of fitting surface to scattered points by MLASSO model
• Restricted isometries for partial random circulant matrices
• Random sampling and reconstruction of sparse time- and band-limited signals
• Random sampling of sparse trigonometric polynomials
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• The restricted isometry property for time-frequency structured random matrices
• On the impossibility of uniform sparse reconstruction using greedy methods
• Deterministic sampling of sparse trigonometric polynomials

Describes a project that uses

Uses Software

• OEIS
• CVX

This page was built for publication: Stability Results for Random Sampling of Sparse Trigonometric Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604925)