A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees

DOI10.1007/s00041-018-9616-4zbMath1431.65253arXiv1706.02740OpenAlexW2624724935MaRDI QIDQ2420230

Sami Merhi, Andrew J. Christlieb, Ruochuan Zhang, Mark A. Iwen

Publication date: 5 June 2019

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

fast Fourier transformsdiscrete Fourier transformssparse approximationcompressive sensingsparse Fourier transformsnonequispaced Fourier transforms

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Numerical methods for trigonometric approximation and interpolation (65T40) Approximation algorithms (68W25)

Related Items (10)

Performance of the multiscale sparse fast Fourier transform algorithm ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ High-dimensional sparse Fourier algorithms ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time ⋮ Deterministic sparse sublinear FFT with improved numerical stability ⋮ A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size ⋮ Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables ⋮ Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares ⋮ A note on the high-dimensional sparse Fourier transform in the continuous setting*

Uses Software

• NFFT
• NFFT3
• Sparse FFT small support

Cites Work

• Unnamed Item
• Unnamed Item
• A multiscale sub-linear time Fourier algorithm for noisy data
• A deterministic sparse FFT algorithm for vectors with small support
• A mathematical introduction to compressive sensing
• Rapidly computing sparse Legendre expansions via sparse Fourier transforms
• Combinatorial sublinear-time Fourier algorithms
• A note on fast Fourier transforms for nonequispaced grids
• Fast Fourier transforms for nonequispaced data. II
• Improved approximation guarantees for sublinear-time Fourier algorithms
• On the fast Fourier transform of functions with singularities
• A deterministic sparse FFT for functions with structured Fourier sparsity
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Explicit universal sampling sets in finite vector spaces
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions
• Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier Transforms
• Compressed sensing and best 𝑘-term approximation
• Fast Fourier Transforms for Nonequispaced Data
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Nearly optimal sparse fourier transform

This page was built for publication: A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees