Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform

DOI10.1016/j.acha.2017.11.008zbMath1423.60012arXiv1703.07230OpenAlexW2607239408MaRDI QIDQ2330933

Lutz Kämmerer

Publication date: 23 October 2019

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

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

zbMATH Keywords

fast Fourier transformlattice rulemultiple rank-1 latticesparse multivariate trigonometric polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Numerical methods for discrete and fast Fourier transforms (65T50) Sampling theory in information and communication theory (94A20) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Related Items

High-dimensional sparse FFT based on sampling along multiple rank-1 lattices, Nonlinear approximation in bounded orthonormal product bases, A sparse FFT approach for ODE with random coefficients, Efficient multivariate approximation on the cube, Transformed rank-1 lattices for high-dimensional approximation, A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size, Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices, The uniform sparse FFT with application to PDEs with random coefficients, A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the stability of the hyperbolic cross discrete Fourier transform
• Reconstruction of periodic functions of several variables with respect to the values in the nodes of number-theoretic nets
• Fouriertransform on sparse grids with hierarchical bases
• Approximation of multivariate periodic functions by trigonometric polynomials based on sampling along rank-1 lattice with generating vector of Korobov form
• Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling
• Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness
• Approximate formulas for some functions of prime numbers
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Component-by-component construction of good lattice rules
• Reconstructing Hyperbolic Cross Trigonometric Polynomials by Sampling along Rank-1 Lattices
• The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials
• Quasi-Monte Carlo methods and pseudo-random numbers
• Probability Inequalities for Sums of Bounded Random Variables