High-dimensional sparse FFT based on sampling along multiple rank-1 lattices

DOI10.1016/j.acha.2020.11.002zbMath1467.65120arXiv1711.05152OpenAlexW3108275699MaRDI QIDQ2659735

Daniel Potts, Lutz Kämmerer, Toni Volkmer

Publication date: 26 March 2021

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.05152

zbMATH Keywords

FFTmultivariate trigonometric polynomialsapproximation of multivariate functionslattice rulesparse fast Fourier transformmultiple rank-1 lattices

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items

Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Nonlinear approximation in bounded orthonormal product bases ⋮ On the reconstruction of functions from values at subsampled quadrature points ⋮ Approximation of High-Dimensional Periodic Functions with Fourier-Based Methods ⋮ Efficient multivariate approximation on the cube ⋮ 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 ⋮ 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 ⋮ The uniform sparse FFT with application to PDEs with random coefficients ⋮ A note on the high-dimensional sparse Fourier transform in the continuous setting* ⋮ A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions

Uses Software

• FFTW
• MPAWL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse high-dimensional FFT based on rank-1 lattice sampling
• A mathematical introduction to compressive sensing
• Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension
• Multidimensional pseudo-spectral methods on lattice grids
• Lattice algorithms for multivariate \(L_{\infty}\) approximation in the worst-case setting
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Reconstruction of periodic functions of several variables with respect to the values in the nodes of number-theoretic nets
• Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials
• Improved approximation guarantees for sublinear-time Fourier algorithms
• The fast Fourier transform and fast wavelet transform for patterns on the torus
• Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform
• Explicit universal sampling sets in finite vector spaces
• Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness
• Parameter estimation for multivariate exponential sums
• Lattice rule algorithms for multivariate approximation in the average case setting
• Reconstructing Multivariate Trigonometric Polynomials from Samples Along Rank-1 Lattices
• Computational Methods for the Fourier Analysis of Sparse High-Dimensional Functions
• (Nearly) Sample-Optimal Sparse Fourier Transform
• Nearly optimal sparse fourier transform
• High-dimensional integration: The quasi-Monte Carlo way
• Compressed sensing