A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
From MaRDI portal
Publication:2118948
DOI10.1007/S11075-021-01162-1zbMATH Open1491.65177arXiv2006.13053OpenAlexW3036122956MaRDI QIDQ2118948FDOQ2118948
Toni Volkmer, Lutz Kämmerer, Felix Krahmer
Publication date: 23 March 2022
Published in: Numerical Algorithms (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2006.13053
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
multivariate trigonometric polynomialsapproximation of multivariate functionslattice rulehigh-dimensional sparse fast Fourier transformmultiple rank-1 lattices
Trigonometric approximation (42A10) Numerical methods for discrete and fast Fourier transforms (65T50)
Cites Work
- Nonequispaced Hyperbolic Cross Fast Fourier Transform
- Probability Inequalities for Sums of Bounded Random Variables
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparsity and incoherence in compressive sampling
- A multiscale sub-linear time Fourier algorithm for noisy data
- Near-optimal sparse fourier representations via sampling
- Title not available (Why is that?)
- Nearly optimal sparse fourier transform
- Title not available (Why is that?)
- Combinatorial sublinear-time Fourier algorithms
- On sparse reconstruction from Fourier and Gaussian measurements
- Stable and Robust Sampling Strategies for Compressive Imaging
- Improved approximation guarantees for sublinear-time Fourier algorithms
- Time bounds for selection
- Parameter estimation for multivariate exponential sums
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- Combinatorial Algorithms for Compressed Sensing
- Explicit estimates of some functions over primes
- Sparse Multidimensional Exponential Analysis with an Application to Radar Imaging
- Title not available (Why is that?)
- Explicit universal sampling sets in finite vector spaces
- Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials
- Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices
- Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- High-dimensional sparse Fourier algorithms
- 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
- Multiscale high-dimensional sparse Fourier algorithms for noisy data
Cited In (3)
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)
