Interpolation

Let $N = (N_{1}, \dots, N_{d})^{⊤} \in 2 N^{d}$ . For given samples $(x_{j}, y_{j}) \in T^{d} \times C, j = 0, \dots, M - 1$ , the index set $I_{N}^{d} := {- \frac{N_{1}}{2}, \dots, \frac{N_{1}}{2} - 1} \times \dots \times {- \frac{N_{d}}{2}, \dots, \frac{N_{d}}{2} - 1}$ , of frequencies, we construct a $d$ -variate trigonometric polynomial $f (x) := \sum_{k \in I_{N}^{d}} {\hat{f}}_{k} e^{2 π i k x}$ such that $f (x_{j}) \approx y_{j}, j = 0, \dots, M - 1$ . Turning this into matrix vector notation, we aim to solve the system of linear equations $\begin{matrix} (1) & A \hat{f} \approx y \end{matrix}$ for the unknown vector of Fourier coefficients $\hat{f} := ({\hat{f}}_{k})_{k \in I_{N}^{d}} \in C^{N^{d}}$ . We denote the vector of the given sample values by $y := (y_{j})_{j = 0, \dots, M - 1} \in C^{M}$ and the nonequispaced Fourier matrix by $A := {(e^{2 π i k x_{j}})}_{j = 0, \dots, M - 1; k \in I_{N}^{d}} \in C^{M \times N^{d}} .$

We focus on the under-determined and consistent linear system $A \hat{f} = y$ , i.e., we expect to interpolate the given data $y_{j} \in C$ , $j = 0, \dots, M - 1$ , exactly.

In particular, we incorporate damping factors ${\hat{w}}_{k} > 0$ , $k \in I_{N}^{d}$ , and consider the optimal interpolation problem $\begin{matrix} (2) & ‖ \hat{f} ‖_{{\hat{W}}^{- 1}}^{2} = \sum_{k \in I_{N}^{d}} \frac{| {\hat{f}}_{k} |^{2}}{{\hat{w}}_{k}} \overset{\hat{f}}{\to} min subject to A \hat{f} = y, \end{matrix}$ where $\hat{W} := d i a g ({\hat{w}}_{k})_{k \in I_{N}^{d}}$ .

This library of C functions computes approximations of (2) with the CGNE method.

The algorithms are implemented by Stefan Kunis in ./solver. Related paper are

Kunis, S. and Potts, D.
Stability Results for Scattered Data Interpolation by Trigonometric Polynomials.
SIAM J. Sci. Comput. 29, 1403 - 1419, (full paper ps, pdf) 2007