A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing

DOI10.1016/J.ACHA.2006.04.003MaRDI QIDQ861809zbMATH OpenOpenAlexFDO

Authors Jing Zou

Publication date 2 February 2007

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.acha.2006.04.003

zbMATH Keywords

optimal B-term Fourier representation of signalsparse Fourier transform for nonequispaced datasublinear randomized algorithm

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Randomized algorithms (68W20) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16) Numerical methods for discrete and fast Fourier transforms (65T50)

Recommendations

• Nearly optimal sparse Fourier transform
• Combinatorial sublinear-time Fourier algorithms
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• (Nearly) sample-optimal sparse Fourier transform
• Improved approximation guarantees for sublinear-time Fourier algorithms

Cites work

• scientific article; zbMATH DE number 236854 (Why is no real title available?)
• A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid
• Accelerating the Nonuniform Fast Fourier Transform
• Decoding by Linear Programming
• Efficient numerical methods in non-uniform sampling theory
• Fast Approximate Fourier Transforms for Irregularly Spaced Data
• Geometric approach to error-correcting codes and reconstruction of signals
• Near-optimal sparse fourier representations via sampling
• On numerical methods for discrete least-squares approximation by trigonometric polynomials
• Random Sampling of Multivariate Trigonometric Polynomials
• Random sampling of sparse trigonometric polynomials
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Stability Results for Scattered Data Interpolation by Trigonometric Polynomials
• Stable recovery of sparse overcomplete representations in the presence of noise
• Stable signal recovery from incomplete and inaccurate measurements
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis

Cited in

(4)

• What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid
• Three novel edge detection methods for incomplete and noisy spectral data
• What's the frequency, Kenneth?: sublinear Fourier sampling off the grid
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit

This page was built for publication: A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing

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