Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis

DOI10.1016/j.jcp.2005.06.005zbMath1085.65128arXivmath/0411102MaRDI QIDQ2572217

Ingrid Daubechies, Anna C. Gilbert, Jing Zou, Martin J. Strauss

Publication date: 16 November 2005

Published in: Journal of Computational Physics (Search for Journal in Brave)

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

zbMATH Keywords

complexity; numerical examples; randomized algorithm; Fast Fourier transform; sublinear algorithm; sparse Fourier representation

Mathematics Subject Classification ID

42A10: Trigonometric approximation

65T50: Numerical methods for discrete and fast Fourier transforms

65T40: Numerical methods for trigonometric approximation and interpolation

68W20: Randomized algorithms

Related Items

Effective band-limited extrapolation relying on Slepian series and \(\ell^1\) regularization, Three novel edge detection methods for incomplete and noisy spectral data, Random sampling of sparse trigonometric polynomials, A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing, Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit

Uses Software

• FFTW

Cites Work

• Unnamed Item
• Unnamed Item
• Implementation issues in the Fourier transform algorithm
• A Sparse Spectral Method for Homogenization Multiscale Problems
• Near-optimal sparse fourier representations via sampling
• Randomized Interpolation and Approximation of Sparse Polynomials