Least squares

Let $\mathit{N}=(N_1,\dots ,N_d{)}^{\mathrm{\top }}\in 2{\mathbb{N}}^d$. For given samples $({\mathit{x}}_j,y_j)\in {\mathbb{T}}^d\times \mathbb{C},j=0,\dots ,M-1$, the index set $I_{\mathit{N}}^d:=\{-\frac{N_1}{2},\dots ,\frac{N_1}{2}-1\}\times \cdots \times \{-\frac{N_d}{2},\dots ,\frac{N_d}{2}-1\}$, of frequencies, we construct a $d$-variate trigonometric polynomial $$f\left(\mathit{x}\right):=\sum _{\mathit{k}\in I_{\mathit{N}}^d}{\hat{f}}_{\mathit{k}}{\mathrm{e}}^{2\pi \mathrm{i}\mathit{k}\mathit{x}}$$ such that $f({\mathit{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{array}{}\text{(1)}& \mathit{A}\hat{\mathit{f}}\approx \mathit{y}\end{array}$$ for the unknown vector of Fourier coefficients $\hat{\mathit{f}}:=({\hat{f}}_{\mathit{k}}{)}_{\mathit{k}\in I_{\mathit{N}}^d}\in {\mathbb{C}}^{N^d}$. We denote the vector of the given sample values by $\mathit{y}:=(y_j{)}_{j=0,\dots ,M-1}\in {\mathbb{C}}^M$ and the nonequispaced Fourier matrix by $$\mathit{A}:={\left({\mathrm{e}}^{2\pi \mathrm{i}\mathit{k}{\mathit{x}}_j}\right)}_{j=0,\dots ,M-1;\mathit{k}\in I_{\mathit{N}}^d}\in {\mathbb{C}}^{M\times N^d}.$$ For $|I_{\mathit{N}}^d|<M$, the linear system (1) is over-determined, so that in general the given data $\mathit{y}$ will be only approximated up to a residual $\mathit{r}:=\mathit{y}-\mathit{A}\hat{\mathit{f}}$. In order to compensate for clusters in the sampling set $\mathcal{X}$, it is useful to incorporate weights $w_j>0$ and to consider the weighted approximation problem $$\begin{array}{}\text{(2)}& \Vert \mathit{y}-\mathit{A}\hat{\mathit{f}}{\Vert }_{\mathit{W}}^2=\sum _{j=0}^{M-1}{w}_j|y_j-f({\mathit{x}}_j){|}^2\stackrel{\hat{\mathit{f}}}{\to }min,\end{array}$$ where $\mathit{W}:=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(w_j{)}_{j=0,\dots ,M-1}$. This library of C functions computes approximations of (2) with the CGNR 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