Improved approximation guarantees for sublinear-time Fourier algorithms
From MaRDI portal
Abstract: In this paper modified variants of the sparse Fourier transform algorithms from [14] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented.
Recommendations
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Combinatorial sublinear-time Fourier algorithms
- Nearly optimal sparse Fourier transform
- scientific article; zbMATH DE number 55678
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
Cited in
(33)- A note on the high-dimensional sparse Fourier transform in the continuous setting
- On the Fourier Extension of Nonperiodic Functions
- scientific article; zbMATH DE number 7053345 (Why is no real title available?)
- Sparse fast DCT for vectors with one-block support
- Nonlinear approximation in bounded orthonormal product bases
- Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
- A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
- A deterministic sparse FFT for functions with structured Fourier sparsity
- A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
- Combinatorial sublinear-time Fourier algorithms
- A tighter bound for FFd algorithm
- Deterministic sparse FFT for M-sparse vectors
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- High-dimensional sparse Fourier algorithms
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
- A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
- 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
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- The uniform sparse FFT with application to PDEs with random coefficients
- Real sparse fast DCT for vectors with short support
- A deterministic sparse FFT algorithm for vectors with small support
- System identification in dynamical sampling
- Performance of the multiscale sparse fast Fourier transform algorithm
- A sparse fast Fourier algorithm for real non-negative vectors
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- Upper and Lower Bounds on Time-Space Tradeoffs for Computations with Embedded Fast Fourier Transforms
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
This page was built for publication: Improved approximation guarantees for sublinear-time Fourier algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1762319)
