A multiscale sub-linear time Fourier algorithm for noisy data

DOI10.1016/j.acha.2015.04.002zbMath1403.42006arXiv1304.4517OpenAlexW2964061529MaRDI QIDQ262947

David Lawlor, Yang Wang, Andrew J. Christlieb

Publication date: 4 April 2016

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

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

zbMATH Keywords

Fourier analysisfast Fourier algorithmsmultiscale algorithms

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items (16)

System identification in dynamical sampling ⋮ A deterministic sparse FFT algorithm for vectors with small support ⋮ Sparse high-dimensional FFT based on rank-1 lattice sampling ⋮ Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Performance of the multiscale sparse fast Fourier transform algorithm ⋮ Nonlinear approximation in bounded orthonormal product bases ⋮ A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees ⋮ Rapidly computing sparse Legendre expansions via sparse Fourier transforms ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ High-dimensional sparse Fourier algorithms ⋮ Sparse fast DCT for vectors with one-block support ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Deterministic sparse sublinear FFT with improved numerical stability ⋮ Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables ⋮ Real sparse fast DCT for vectors with short support ⋮ A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions

Uses Software

• FFTW
• EMD

Cites Work

• Unnamed Item
• Combinatorial sublinear-time Fourier algorithms
• The earth mover's distance as a metric for image retrieval
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
• Solving Hidden Number Problem with One Bit Oracle and Advice
• A/D conversion with imperfect quantizers
• Near-optimal sparse fourier representations via sampling
• Learning Decision Trees Using the Fourier Spectrum
• Randomized Interpolation and Approximation of Sparse Polynomials
• Rapid Computation of the Discrete Fourier Transform
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Nearly optimal sparse fourier transform

This page was built for publication: A multiscale sub-linear time Fourier algorithm for noisy data