A deterministic sparse FFT algorithm for vectors with small support

DOI10.1007/s11075-015-0028-0zbMath1341.65056arXiv1504.02214OpenAlexW3098475203MaRDI QIDQ281476

Katrin Wannenwetsch, Gerlind Plonka-Hoch

Publication date: 11 May 2016

Published in: Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

discrete Fourier transformsparse Fourier reconstructionsublinear sparse FFT

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items (11)

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 ⋮ Deterministic sparse FFT for \(M\)-sparse vectors ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ High-dimensional sparse Fourier algorithms ⋮ Sparse fast DCT for vectors with one-block support ⋮ Deterministic sparse sublinear FFT with improved numerical stability ⋮ Sparse FFT small support ⋮ Real sparse fast DCT for vectors with short support ⋮ A sparse fast Fourier algorithm for real non-negative vectors

Cites Work

• A multiscale sub-linear time Fourier algorithm for noisy data
• Combinatorial sublinear-time Fourier algorithms
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Calculating the Maximum Modulus of a Polynomial Using Steckin's Lemma
• Prony methods for recovery of structured functions
• (Nearly) Sample-Optimal Sparse Fourier Transform
• Nearly optimal sparse fourier transform

This page was built for publication: A deterministic sparse FFT algorithm for vectors with small support