A multiscale sub-linear time Fourier algorithm for noisy data

DOI10.1016/J.ACHA.2015.04.002MaRDI QIDQ262947zbMATH OpenOpenAlexFDO

Authors David Lawlor, Yang Wang, Andrew 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

fast Fourier algorithmsFourier analysismultiscale 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)

Abstract: We extend the recent sparse Fourier transform algorithm of (Lawlor, Christlieb, and Wang, 2013) to the noisy setting, in which a signal of bandwidth N is given as a superposition of k << N frequencies and additive noise. We present two such extensions, the second of which exhibits a novel form of error-correction in its frequency estimation not unlike that of the beta-encoders in analog-to-digital conversion (Daubechies et al, 2006). The algorithm runs in time O(k log(k) log(N/k)) on average, provided the noise is not overwhelming. The error-correction property allows the algorithm to outperform FFTW, a highly optimized software package for computing the full discrete Fourier transform, over a wide range of sparsity and noise values, and is to the best of our knowledge novel in the sparse Fourier transform context.

Recommendations

• Multiscale high-dimensional sparse Fourier algorithms for noisy data
• Nearly optimal sparse Fourier transform
• Combinatorial sublinear-time Fourier algorithms
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• scientific article; zbMATH DE number 7053345

Cites work

• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• A/D conversion with imperfect quantizers
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Combinatorial sublinear-time Fourier algorithms
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• Learning Decision Trees Using the Fourier Spectrum
• Near-optimal sparse fourier representations via sampling
• Nearly optimal sparse Fourier transform
• Randomized Interpolation and Approximation of Sparse Polynomials
• Rapid Computation of the Discrete Fourier Transform
• Solving Hidden Number Problem with One Bit Oracle and Advice
• The earth mover's distance as a metric for image retrieval
• What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid

Cited in

(18)

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

Describes a project that uses

Uses Software

• EMD
• FFTW

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

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