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

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

Ingrid Daubechies, Jing Zou, Anna C. Gilbert, 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

complexitynumerical examplesrandomized algorithmFast Fourier transformsublinear algorithmsparse Fourier representation

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical methods for discrete and fast Fourier transforms (65T50) Numerical methods for trigonometric approximation and interpolation (65T40) Randomized algorithms (68W20)

Related Items

Matrix sparsification and the sparse null space problem, Random sampling of sparse trigonometric polynomials, A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing, Effective band-limited extrapolation relying on Slepian series and \(\ell^1\) regularization, Superfast Fourier transform using QTT approximation, Three novel edge detection methods for incomplete and noisy spectral data, 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