A deterministic sparse FFT for functions with structured Fourier sparsity
From MaRDI portal
Publication:2000485
approximation algorithmsstructured sparsitydeterministic constructionssparse Fourier transform (SFT)
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)
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 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} 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.
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
Cites work
- scientific article; zbMATH DE number 6770709 (Why is no real title available?)
- (Nearly) sample-optimal sparse Fourier transform
- A deterministic sparse FFT algorithm for vectors with small support
- A mathematical introduction to compressive sensing
- A multiscale sub-linear time Fourier algorithm for noisy data
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- A sparse fast Fourier algorithm for real non-negative vectors
- An adaptive sublinear-time block sparse Fourier transform
- Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals
- Combinatorial sublinear-time Fourier algorithms
- Deterministic sparse FFT for M-sparse vectors
- Empirical evaluation of a sub-linear time sparse DFT algorithm
- Explicit constructions of RIP matrices and related problems
- Explicit universal sampling sets in finite vector spaces
- Improved approximation guarantees for sublinear-time Fourier algorithms
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Multiplicative number theory. I. Classical theory
- Near-optimal sparse fourier representations via sampling
- Nearly optimal sparse Fourier transform
- On the design of deterministic matrices for fast recovery of Fourier compressible functions
- Prony methods for recovery of structured functions
- Randomized interpolation and approximation of sparse polynomials stPreliminary version
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid
Cited in
(17)- A note on the high-dimensional sparse Fourier transform in the continuous setting
- Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
- Sparse fast trigonometric transforms
- 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
- Deterministic sparse FFT for M-sparse vectors
- 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
- 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
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- The uniform sparse FFT with application to PDEs with random coefficients
- Real sparse fast DCT for vectors with short support
- Optimized Spectrum Permutation for the Multidimensional Sparse FFT
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)
