Trigonometric interpolation on lattice grids (Q285296)

Let \(\Omega\) be a set of \(N\) grid points \(x_j \in [0,\,1)^s\). The authors interpolate an \(s\)-variate, \(1\)-periodic function \(f\) by an \(s\)-variate trigonometric polynomial such that \[ f(x_j)=\sum_{k\in S}c_k\,\exp(2\pi i\,k\cdot x_j)\quad (j=1,\dots,N), \] where \(k\in S\subset\mathbb Z^s\) are multi-indices and \(|S|=N\). The Lagrange functions \(L_j\) of \(\Omega\) with respect to the interpolation space \(\mathcal H_S=\mathrm{span}\{\exp(2\pi i\,k\cdot x):\,k\in S\}\) are functions of \(\mathcal H_S\) with \(L_j(x_k)=\delta_{j,k}\) for \(j,k=1,\dots, N\). The Lebesgue constant of \(\Omega\) and \(\mathcal H_S\) is defined as \(H=\max \{\sum_{j=1}^N |L_j(x)|:x \in [0,1]^s\}\). In this paper, the authors construct non-aliasing interpolation spaces and Lagrange functions for lattice grids in \([0,1)^s\). A simple greedy algorithm allows to embed the hyperbolic cross as a subspace in the interpolation spaces. Both lattice grids and sparse grids seem to have quasi-optimal Lebesgue constants. The quality of lattice interpolation appears to be better than sparse grid interpolation, as shown by numerical tests for dimensions \(s=2\) and \(s=3\). For the interpolation on lattice grids, the fast Fourier transform can be applied.