A deterministic sparse FFT for functions with structured Fourier sparsity

DOI10.1007/S10444-018-9626-4zbMATH Open1458.42002arXiv1705.05256OpenAlexW2614914956MaRDI QIDQ2000485FDOQ2000485

M. A. Iwen, Sina Bittens, Ruochuan Zhang

Publication date: 28 June 2019

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: In this paper a deterministic sparse Fourier transform algorithm is presented which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. These functions include, e.g., the oft-considered set of block frequency sparse functions of the form ${\displaystyle }$f(x) = sum^{n}_{j=1} sum^{B-1}_{k=0} c_{omega_j + k} e^{i(omega_j + k)x},~~{ omega_1, dots, omega_n } subset left(-leftlceil frac{N}{2} ight ceil, leftlfloor frac{N}{2} ight floor ight]capmathbb{Z}${\displaystyle }$ as a simple subclass. Theoretical error bounds in combination with numerical experiments demonstrate that the newly proposed algorithms are both fast and robust to noise. In particular, they outperform standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions of the type above.

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

Recommendations

• A deterministic sparse FFT algorithm for vectors with small support
• Combinatorial sublinear-time Fourier algorithms
• Sparse fast trigonometric transforms
• Deterministic sparse FFT for \(M\)-sparse vectors
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees

zbMATH Keywords

approximation algorithmsstructured sparsitydeterministic constructionssparse Fourier transform (SFT)

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Trigonometric approximation (42A10) Approximation algorithms (68W25) Trigonometric interpolation (42A15) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16) Trigonometric series of special types (positive coefficients, monotonic coefficients, etc.) (42A32) Numerical methods for discrete and fast Fourier transforms (65T50)

Cites Work

• A deterministic sparse FFT algorithm for vectors with small support
• A mathematical introduction to compressive sensing
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• A multiscale sub-linear time Fourier algorithm for noisy data
• What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
• Multiplicative number theory. I. Classical theory
• Near-optimal sparse fourier representations via sampling
• Nearly optimal sparse fourier transform
• Combinatorial sublinear-time Fourier algorithms
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Prony methods for recovery of structured functions
• (Nearly) Sample-Optimal Sparse Fourier Transform
• Explicit constructions of RIP matrices and related problems
• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Rapidly computing sparse Legendre expansions via sparse Fourier transforms
• On the design of deterministic matrices for fast recovery of Fourier compressible functions
• An adaptive sublinear-time block sparse fourier transform
• Explicit universal sampling sets in finite vector spaces
• A sparse fast Fourier algorithm for real non-negative vectors
• Deterministic sparse FFT for \(M\)-sparse vectors
• Title not available (Why is that?)
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

Cited In (14)

• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
• Sparse fast DCT for vectors with one-block support
• A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
• 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
• 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
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• The uniform sparse FFT with application to PDEs with random coefficients
• Real sparse fast DCT for vectors with short support
• A note on the high-dimensional sparse Fourier transform in the continuous setting*
• Optimized Spectrum Permutation for the Multidimensional Sparse FFT

Uses Software

• SFFT
• Sparse FFT small support

This page was built for publication: A deterministic sparse FFT for functions with structured Fourier sparsity

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