Fast discrete algorithms for sparse Fourier expansions of high dimensional functions
From MaRDI portal
Publication:2655801
The authors develop a fast algorithm for computing the sparse Fourier expansion of a \(d\)-variate function \(f\) with Sobolev regularity of order \(s>0\). In a sparse Fourier expansion, the frequency vectors of the \(d\)-variate exponentials form a so-called hyperbolic cross. Using a sparse multiscale Lagrange interpolation method, the authors design a quadrature scheme for evaluating the corresponding Fourier coefficients of \(f\). Further they show that this method gives optimal approximation order \({\mathcal O}(n^{-s})\) for the sparse Fourier expansion of \(f\), where \(n\) is the order of the univariate trigonometric polynomial used to construct the sparse Fourier expansion, and requires \({\mathcal O}(n\,(\log\, n)^{2d-1})\) multiplications to compute all the needed Fourier coefficients of \(f\). Numerical examples are presented for \(d\in \{2,\,3,\,4,\,8\}\).
Recommendations
- Computational methods for the Fourier analysis of sparse high-dimensional functions
- Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- Fast sparse nonlinear Fourier expansions of high dimensional functions
- Fast evaluation of trigonometric polynomials from hyperbolic crosses
Cites work
- A construction of interpolating wavelets on invariant sets
- A construction of refinable sets for interpolating wavelets
- A Fast Fourier–Galerkin Method for Solving Singular Boundary Integral Equations
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Efficient quadrature of highly oscillatory integrals using derivatives
- Fast Algorithms for Periodic Spline Wavelets on Sparse Grids
- Fast Algorithms for Spherical Harmonic Expansions
- Fast Boolean approximation methods for solving integral equations in high dimensions
- Fourier transform on sparse grids: Code design and the time dependent Schrödinger equation
- Fouriertransform on sparse grids with hierarchical bases
- High dimensional polynomial interpolation on sparse grids
- Higher order sparse grid methods for elliptic partial differential equations with variable coefficients
- scientific article; zbMATH DE number 4015366 (Why is no real title available?)
- scientific article; zbMATH DE number 4129404 (Why is no real title available?)
- scientific article; zbMATH DE number 4205063 (Why is no real title available?)
- scientific article; zbMATH DE number 5190601 (Why is no real title available?)
- scientific article; zbMATH DE number 66109 (Why is no real title available?)
- scientific article; zbMATH DE number 3481186 (Why is no real title available?)
- scientific article; zbMATH DE number 1301767 (Why is no real title available?)
- scientific article; zbMATH DE number 1049042 (Why is no real title available?)
- scientific article; zbMATH DE number 783551 (Why is no real title available?)
- scientific article; zbMATH DE number 914714 (Why is no real title available?)
- Hyperbolic cross and the complexity of the approximate solution of Fredholm integral equations of the second kind with differentiable kernels
- Information complexity of multivariate Fredholm integral equations in Sobolev classes
- Lattice Methods for Multiple Integration: Theory, Error Analysis and Examples
- On quadrature methods for highly oscillatory integrals and their implementation
- On the numerical quadrature of highly-oscillating integrals I: Fourier transforms
- On the numerical quadrature of highly-oscillating integrals II: Irregular oscillators
- Optimized tensor-product approximation spaces
- Procedures for Computing One- and Two-Dimensional Integrals of Functions with Rapid Irregular Oscillations
- Sparse approximation of singularity functions
- Sparse grids
- Strang Splitting for the Time-Dependent Schrödinger Equation on Sparse Grids
- Two‐Scale Boolean Galerkin Discretizations for Fredholm Integral Equations of the Second Kind
Cited in
(27)- A fast discrete spectral method for stochastic partial differential equations
- A fully discrete fast Fourier-Galerkin method solving a boundary integral equation for the biharmonic equation
- The numerical integration scheme for a fast Petrov-Galerkin method for solving the generalized airfoil equation
- Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
- A fast Fourier-Galerkin method solving a system of integral equations for the biharmonic equation
- Computing the Newton potential in the boundary integral equation for the Dirichlet problem of the Poisson equation
- Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform
- 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
- Fast Fourier-Galerkin methods for first-kind logarithmic-kernel integral equations on open arcs
- A fast solver for the Hilbert-type singular integral equations based on the direct Fourier spectral method
- Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids
- From high oscillation to rapid approximation. III: Multivariate expansions
- Fast Fourier-Galerkin methods for nonlinear boundary integral equations
- Sparse Evaluation of Compositions of Functions Using Multiscale Expansions
- Orthogonal polynomial expansions on sparse grids
- Fast sparse nonlinear Fourier expansions of high dimensional functions
- Grouped transformations and regularization in high-dimensional explainable ANOVA approximation
- Fast discrete Fourier transform on generalized sparse grids
- Computational methods for the Fourier analysis of sparse high-dimensional functions
- B-spline quasi-interpolation on sparse grids
- A fully discrete high-order fast multiscale Galerkin method for solving boundary integral equations in a domain with corners
- Interpolation lattices for hyperbolic cross trigonometric polynomials
- A fast numerical solution for the first kind boundary integral equation for the Helmholtz equation
- A fast solver for boundary integral equations of the modified Helmholtz equation
- Fast Fourier-Galerkin methods for solving singular boundary integral equations: Numerical integration and precondition
- Approximation of high-dimensional kernel matrices by multilevel circulant matrices
This page was built for publication: Fast discrete algorithms for sparse Fourier expansions of high dimensional functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2655801)
