A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
From MaRDI portal
Publication:2118948
Abstract: In this paper a sublinear time algorithm is presented for the reconstruction of functions that can be represented by just few out of a potentially large candidate set of Fourier basis functions in high spatial dimensions, a so-called high-dimensional sparse fast Fourier transform. In contrast to many other such algorithms, our method works for arbitrary candidate sets and does not make additional structural assumptions on the candidate set. Our transform significantly improves upon the other approaches available for such a general framework in terms of the scaling of the sample complexity. Our algorithm is based on sampling the function along multiple rank-1 lattices with random generators. Combined with a dimension-incremental approach, our method yields a sparse Fourier transform whose computational complexity only grows mildly in the dimension and can hence be efficiently computed even in high dimensions. Our theoretical analysis establishes that any Fourier -sparse function can be accurately reconstructed with high probability. This guarantee is complemented by several numerical tests demonstrating the high efficiency and versatile applicability for the exactly sparse case and also for the compressible case.
Recommendations
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- (Nearly) sample-optimal sparse Fourier transform
- scientific article; zbMATH DE number 6770709
- Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- High-dimensional sparse Fourier algorithms
- A deterministic sparse FFT for functions with structured Fourier sparsity
- A sparse data fast fourier transform (SDFFT)
- Deterministic sparse FFT for \(M\)-sparse vectors
- Optimized Spectrum Permutation for the Multidimensional Sparse FFT
Cites work
- scientific article; zbMATH DE number 5764870 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 7053345 (Why is no real title available?)
- A multiscale sub-linear time Fourier algorithm for noisy data
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices
- Combinatorial Algorithms for Compressed Sensing
- Combinatorial sublinear-time Fourier algorithms
- Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform
- Explicit estimates of some functions over primes
- Explicit universal sampling sets in finite vector spaces
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- High-dimensional sparse Fourier algorithms
- Improved approximation guarantees for sublinear-time Fourier algorithms
- Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials
- Multiscale high-dimensional sparse Fourier algorithms for noisy data
- Near-optimal sparse fourier representations via sampling
- Nearly optimal sparse Fourier transform
- Nonequispaced Hyperbolic Cross Fast Fourier Transform
- On sparse reconstruction from Fourier and Gaussian measurements
- Parameter estimation for multivariate exponential sums
- Probability Inequalities for Sums of Bounded Random Variables
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- Sparse multidimensional exponential analysis with an application to radar imaging
- Sparsity and incoherence in compressive sampling
- Stable and Robust Sampling Strategies for Compressive Imaging
- Time bounds for selection
Cited in
(7)- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- A note on the high-dimensional sparse Fourier transform in the continuous setting
- High-dimensional sparse Fourier algorithms
- Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
- Optimized Spectrum Permutation for the Multidimensional Sparse FFT
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- Nonlinear approximation in bounded orthonormal product bases
This page was built for publication: A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118948)
