Empirical evaluation of a sub-linear time sparse DFT algorithm

DOI10.4310/CMS.2007.V5.N4.A13MaRDI QIDQ2477145zbMATH OpenFDO

Authors Yanyan Li

Publication date 13 March 2008

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.cms/1199377561

zbMATH Keywords

numerical examplesalgorithmrandom samplingfast Fourier transformcompressive sensingfast approximate discrete Fourier transformfrequency-sparse signalssub-linear time algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Numerical methods for discrete and fast Fourier transforms (65T50)

Recommendations

• Nearly optimal sparse Fourier transform
• A multiscale sub-linear time Fourier algorithm for noisy data
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• (Nearly) sample-optimal sparse Fourier transform
• Combinatorial sublinear-time Fourier algorithms

Cited in

(13)

• A multiscale sub-linear time Fourier algorithm for noisy data
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• Nonlinear approximation in bounded orthonormal product bases
• On Performance of Sparse Fast Fourier Transform and Enhancement Algorithm
• A deterministic sparse FFT for functions with structured Fourier sparsity
• Combinatorial sublinear-time Fourier algorithms
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• 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 harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• Performance of the multiscale sparse fast Fourier transform algorithm
• Rapidly computing sparse Legendre expansions via sparse Fourier transforms

This page was built for publication: Empirical evaluation of a sub-linear time sparse DFT algorithm

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