Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
DOI10.1007/s43670-021-00018-yzbMath1478.65143arXiv2012.09889OpenAlexW3117717272MaRDI QIDQ2073139
Craig Gross, Toni Volkmer, Lutz Kämmerer, Mark A. Iwen
Publication date: 27 January 2022
Published in: Sampling Theory, Signal Processing, and Data Analysis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.09889
fast Fourier transformsfast algorithmsapproximation algorithmssparse Fourier transformsmultivariate Fourier approximationrank-1 lattices
Numerical methods for discrete and fast Fourier transforms (65T50) Algorithms for approximation of functions (65D15) Numerical methods for trigonometric approximation and interpolation (65T40) Fourier series and coefficients in several variables (42B05) Complexity and performance of numerical algorithms (65Y20)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A multiscale sub-linear time Fourier algorithm for noisy data
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- A mathematical introduction to compressive sensing
- Multidimensional pseudo-spectral methods on lattice grids
- Combinatorial sublinear-time Fourier algorithms
- Reconstruction of periodic functions of several variables with respect to the values in the nodes of number-theoretic nets
- Deterministic sparse FFT for \(M\)-sparse vectors
- Numerical Fourier analysis
- Improved approximation guarantees for sublinear-time Fourier algorithms
- 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
- Sparse fast DCT for vectors with one-block support
- Real sparse fast DCT for vectors with short support
- 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
- Explicit universal sampling sets in finite vector spaces
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- Reconstructing Multivariate Trigonometric Polynomials from Samples Along Rank-1 Lattices
- Compressed sensing and best 𝑘-term approximation
- Function integration, reconstruction and approximation using rank-$1$ lattices
- Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
This page was built for publication: Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
