Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
The problem of quickly estimating the best \(k\)-term Fourier representation for a given periodic function \(f:\;[0,2\pi]\to \mathbb C\) is studied. Solving this problem requires the identification of \(k\) of the largest magnitude Fourier series coefficients of \(f\) in worst case \(k^2\cdot\log^{O(1)}N\) time. Randomized sublinear-time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, have been developed for solving this problem (Gilbert et al. 2002, 2005). These methods were implemented as the Ann Arbor fast Fourier transform (AAFFT) and empirically evaluated by \textit{M. A. Iwen, A. Gilbert} and \textit{M. Strauss} [Commun. Math. Sci. 5, No. 4, 981--998 (2007; Zbl 1134.65093)]. In this paper, the authors present a new implementation, called the Gopher fast Fourier transform (GFFT), of more recently developed sparse Fourier transform techniques (cf. [\textit{M. A. Iwen}, Found. Comput. Math. 10, No. 3, 303--338 (2010; Zbl 1230.65145); Appl. Comput. Harmon. Anal. 34, No. 1, 57--82 (2013; Zbl 1260.65115)]). Experiments indicate that GFFT is faster than AAFFT.
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
- Nearly optimal sparse Fourier transform
- scientific article; zbMATH DE number 6796498
- (Nearly) sample-optimal sparse Fourier transform
- Improved approximation guarantees for sublinear-time Fourier algorithms
- A deterministic sparse FFT for functions with structured Fourier sparsity
- Deterministic sparse sublinear FFT with improved numerical stability
- The sparse Fourier transform: theory and practice
- High-dimensional sparse Fourier algorithms
- A Sparse Spectral Method for Homogenization Multiscale Problems
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Chebyshev and Fourier spectral methods.
- Combinatorial Algorithms for Compressed Sensing
- Combinatorial sublinear-time Fourier algorithms
- Compressed sensing
- Compressed sensing and best \(k\)-term approximation
- Compressive sensing and structured random matrices
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
- Empirical evaluation of a sub-linear time sparse DFT algorithm
- Fast Fourier Transforms for Nonequispaced Data
- scientific article; zbMATH DE number 5485456 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 1380579 (Why is no real title available?)
- scientific article; zbMATH DE number 774007 (Why is no real title available?)
- Iterative hard thresholding for compressed sensing
- Learning Decision Trees Using the Fourier Spectrum
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Near-optimal sparse fourier representations via sampling
- On sparse reconstruction from Fourier and Gaussian measurements
- On the design of deterministic matrices for fast recovery of Fourier compressible functions
- Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
- Randomized Interpolation and Approximation of Sparse Polynomials
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Stable signal recovery from incomplete and inaccurate measurements
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- Deterministic sparse FFT for M-sparse vectors
- Improved approximation guarantees for sublinear-time Fourier algorithms
- A deterministic sparse FFT for functions with structured Fourier sparsity
- 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
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- Sparse fast DCT for vectors with one-block support
- Real sparse fast DCT for vectors with short support
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- Empirical evaluation of a sub-linear time sparse DFT algorithm
- Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
- On Performance of Sparse Fast Fourier Transform and Enhancement Algorithm
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- scientific article; zbMATH DE number 6796498 (Why is no real title available?)
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- Nonlinear approximation in bounded orthonormal product bases
- Combinatorial sublinear-time Fourier algorithms
This page was built for publication: Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376358)
