Improved sparse fourier approximation results: faster implementations and stronger guarantees
Explore this paper's citation graph
Summary
It is proved the existence of sublinear-time Las Vegas Fourier Transforms which improve on the recent deterministic Fourier approximation results of Iwen for Fourier compressible functions by guaranteeing accurate answers while using an asymptotically near-optimal number of function evaluations.
- Type
- article
- Published
- 2013-06-01
- Cited by
- 21
- References
- 42
- OpenAlex
- https://openalex.org/W1977453732
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:14072563
Keywords
Fourier transform, Mathematics, Sublinear function, Fourier series, Fourier inversion theorem
References
- Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.
- Compressed Sensing
- Theoretical Foundations and Numerical Methods for Sparse Recovery
- Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms
- Randomized Interpolation and Approximation of Sparse Polynomials
- Chebyshev and Fourier Spectral Methods
- A Sparse Spectral Method for Homogenization Multiscale Problems
- One sketch for all: fast algorithms for compressed sensing
- Improved time bounds for near-optimal sparse Fourier representations
- Empirical evaluation of a sub-linear time sparse DFT algorithm
- Combinatorial Algorithms for Compressed Sensing
- Near-optimal sparse fourier representations via sampling
- Compressed sensing and best k-term approximation
- Combinatorial Sublinear-Time Fourier Algorithms
- On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions
- Learning decision trees using the Fourier spectrum
- An algorithm for the machine calculation of complex Fourier series
- Theory of computing: a scientific perspective
- Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit
- Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
Cited by
- Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms
- Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- A Non-sparse Tutorial on Sparse FFTs
- A deterministic sparse FFT for functions with structured Fourier sparsity
- A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees
- Deterministic sparse FFT for M-sparse vectors
- Sparse fast DCT for vectors with one-block support
- Real sparse fast DCT for vectors with short support
- Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables
- Inverting Spectrogram Measurements via Aliased Wigner Distribution Deconvolution and Angular Synchronization
- Sparse Fast Trigonometric Transforms
- 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
- A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
- Deterministic Sparse Sublinear FFT with Improved Numerical Stability
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- Nonlinear approximation in bounded orthonormal product bases
- SUB-LINEAR SPARSE FOURIER TRANSFORM ALGORITHM
- Random Sampling in Bounded Orthonormal Systems