We consider the fast evaluation of trigonometric polynomials from so-called hyperbolic crosses. In multivariate approximation one has to deal with the so called `curse of dimensionality', i.e., the number of degrees of freedom for representing an approximation of a function with a prescribed accuracy depends exponentially on the dimensionality of the considered problem. This obstacle can be circumvented to some extend by the interpolation on sparse grids and the related approximation on hyperbolic cross points in the Fourier domain, see, e.g., [58,54,9].
Instead of approximating a Fourier series on the standard tensor product grid
with
degrees of freedom, it can be
approximated with only
degrees of freedom from the
hyperbolic cross
![]() |
The nonequispaced sparse discrete Fourier transform (NSDFT) is the evaluation of
![]() |