Nearly optimal sparse Fourier transform
From MaRDI portal
Abstract: We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: * An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and * An O(k log n log(n/k))-time randomized algorithm for general input signals. Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = n^{Omega(1)}. We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least Omega(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.
Recommendations
Cited in
(57)- Sard-optimal prefilters for the fast wavelet transform
- Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile
- Deterministic sparse FFT for M-sparse vectors
- Superfast Fourier transform using QTT approximation
- Improved approximation guarantees for sublinear-time Fourier algorithms
- The partial fast Fourier transform
- A deterministic sparse FFT for functions with structured Fourier sparsity
- Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
- High-dimensional sparse Fourier algorithms
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- Quantum learning of concentrated Boolean functions
- A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
- Vibration analysis of cyclic symmetrical systems by quantum algorithms
- Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling
- A sparse fast Fourier algorithm for real non-negative vectors
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- 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
- A multiscale sub-linear time Fourier algorithm for noisy data
- Faster sparse multivariate polynomial interpolation of straight-line programs
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- A deterministic sparse FFT algorithm for vectors with small support
- Shearlets and Optimally Sparse Approximations
- What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- Reconstruction of sparse Legendre and Gegenbauer expansions
- Tighter Fourier transform lower bounds
- Sparse Fourier Transform via Butterfly Algorithm
- scientific article; zbMATH DE number 1555403 (Why is no real title available?)
- The sparse Fourier transform: theory and practice
- Sparse Discrete Fractional Fourier Transform and Its Applications
- Detecting the large entries of a sparse covariance matrix in sub-quadratic time
- Approximation and Compression With Sparse Orthonormal Transforms
- Optimized Spectrum Permutation for the Multidimensional Sparse FFT
- On Performance of Sparse Fast Fourier Transform and Enhancement Algorithm
- An adaptive sublinear-time block sparse Fourier transform
- Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
- Two new results about quantum exact learning
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- Dimension-independent sparse Fourier transform
- Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- scientific article; zbMATH DE number 6796498 (Why is no real title available?)
- (Nearly) sample-optimal sparse Fourier transform
- Applications of classical approximation theory to periodic basis function networks and computational harmonic analysis
- scientific article; zbMATH DE number 7053345 (Why is no real title available?)
- Performance of the multiscale sparse fast Fourier transform algorithm
- Nonlinear approximation in bounded orthonormal product bases
- Deterministic sparse Fourier transform with an _ guarantee
- Sparse recovery for orthogonal polynomial transforms
- Sparse graph signals -- uncertainty principles and recovery
- On Fourier analysis of sparse Boolean functions over certain abelian groups
- Optimal Extrapolation Bounds for Sparse Fourier Sums
- What's the frequency, Kenneth?: sublinear Fourier sampling off the grid
- A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
- Sparse generalized Fourier transforms
- Combinatorial sublinear-time Fourier algorithms
This page was built for publication: Nearly optimal sparse Fourier transform
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415501)
