A deterministic sparse FFT for functions with structured Fourier sparsity
From MaRDI portal
Publication:2000485
approximation algorithmsdeterministic constructionssparse Fourier transform (SFT)structured sparsity
Trigonometric approximation (42A10) 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) Approximation algorithms (68W25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
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
- (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
- scientific article; zbMATH DE number 6770709 (Why is no real title available?)
- 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
(19)- Deterministic sparse FFT for M-sparse vectors
- 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
- The uniform sparse FFT with application to PDEs with random coefficients
- A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
- Sparse fast DCT for vectors with one-block support
- Real sparse fast DCT for vectors with short support
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
- Optimized Spectrum Permutation for the Multidimensional Sparse FFT
- A note on the high-dimensional sparse Fourier transform in the continuous setting
- Sparse fast trigonometric transforms
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- SCAN-MUSIC: an efficient super-resolution algorithm for large-scale single snapshot line spectral estimation
- Sparse spectral methods for solving high-dimensional and multiscale elliptic PDEs
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)
