Filtered Kernel Interpolation for the Approximation of Higher-Dimensional Periodic Functions with good lattice points

  • Griebel, Michael (Uni Bonn, INS)

Please login to view abstract download link

We consider the numerical approximation of $d$-dimensional periodic functions on the unit cube with bounded mixed derivatives of order $s$. The underlying function space is a Korobov space, and is a reproducing kernel Hilbert space with kernel $K_s$. Numerical quadrature in this setting can be performed using $N$ sampling points generated by suitable lattice rules. In particular, rank-1 lattice rules achieve a worst-case quadrature error of order $O(N^{-s+\delta}), \forall \delta>0$. However, when the same rank-1 lattice points are employed for kernel-based $L_2$-approximation, the $L_2$-convergence deteriorates significantly to essentially $O(N^{-s/2})$, up to logarithmic factors. The underlying reason is aliasing. This issue can be mitigated by least-squares and kernel-based subsampling techniques. There, a randomly selected subset of points from a good lattice rule is used for kernel interpolation. These methods are (nearly) optimal in a certain sense. Nevertheless, both its theoretical analysis and its practical realization are rather involved. In particular, the computational cost scales like $r N\log N$, where $r$ denotes the number of iterations required to solve the linear system associated with the kernel interpolation matrix, and the logarithmic factor arises from the use of the FFT. Moreover, this approach can be extended naturally to weighted Korobov spaces. As an alternative, we propose the use of a filtered reproducing kernel. In this approach, the Mercer expansion of $K_s$ is truncated appropriately using a hyperbolic cross index set of truncation level $l$, with $l$ chosen such that $l\approx N/2$. Denoting the resulting filtered kernel by $K_s^l$, the corresponding kernel interpolant achieves a worst-case error of order $O(N^{-s})$, again up to logarithmic terms. The filtered kernel interpolation approach can likewise be generalized to weighted spaces $H^s_{mix,per, \gamma}((0,1)^d)$. In this case, the truncation procedure must be adapted carefully to the decay properties of the weight sequence, leading to anisotropic hyperbolic cross index sets. This yields strong tractability, and logarithmic factors and dimension-dependent constants hidden in the $O$-notation can be eliminated. In this talk, we discuss the filtered kernel interpolation method, its algorithmic realization, and its computational complexity, and we present results from numerical experiments.