Inverse NDFT

In general there is no simple inversion formula, hence one deals with the following reconstruction or recovery problem. Given the values $f_j \in \mathbb{C}\; (j=0,\hdots,M-1)$ at non equispaced knots ${x}$$_j\; (j=0,\hdots,M-1)$, the aim is to reconstruct a trigonometric polynomial $f$ resp. its Fourier-coefficients $\hat f_{\mbox{\boldmath\scriptsize {${k}$}}}\;(\mbox{\boldmath {${k}$}} \in I_{\mbox{\boldmath\scriptsize {${N}$}}})$ with

$$f\left(\mbox{\boldmath {${x}$}}_j\right)=\sum_{\mbox{\boldmath\sc... ...ldmath {${A}$}} \mbox{\boldmath {${\hat f}$}} \approx \mbox{\boldmath {${f}$}}.$$

Often, the number of nodes $M$ and the dimension of the space of the polynomials $N_{\text{\tiny $\Pi$}}$ do not coincide, i.e., the matrix ${A}$ is rectangular. A standard method is to use the Moore-Penrose-pseudoinverse solution ${\hat f}$$^{\dagger}$ which solves the general linear least squares problem, see e.g. [3, p. 15],

$$\Vert \mbox{\boldmath {${\hat f}$}} \Vert _2 \rightarrow \min \quad \Vert \mbox{\boldmath {${f}$}} - \mbox{\boldmath {${A}$}} \mbox{\boldmath {${\hat f}$}} \Vert _2=\min \mbox{\boldmath {${f}$}} \in \mathbb{C}^{M}.$$

Of course, computing the pseudoinverse by the singular value decomposition is very expensive here and no practical way at all.

For a comparative low polynomial degree $N_{\text{\tiny $\Pi$}}<M$ the linear system ${A}$   ${\hat f}$$\approx$   ${f}$ is over-determined, so that in general the given data $f_j\in \mathbb{C},\;j=0,\hdots,M-1,$ will be only approximated up to the residual ${r}$$:=$${f}$$-$${A}$   ${\hat f}$. One considers the weighted approximation problem

$$\Vert \mbox{\boldmath {${f}$}} - \mbox{\boldmath {${A}$}} \mbox{\boldmath {${\hat f}$}} \Vert _{\mbox{\boldmath\scriptsize {${W}$}}} = \left(\sum_{j=0}... ...)^{1/2} \stackrel{\mbox{\boldmath\scriptsize {${\hat f}$}}}{\rightarrow} \min,$$

which may incorporate weights $w_j> 0$, ${W}$$:={\, \rm diag}(w_j)_{j=0,\ldots,M-1}$, to compensate for clusters in the sampling set ${\cal X}$. This problem is equivalent to the weighted normal equation of first kind

$$\mbox{\boldmath {${A}$}} ^{\rm H} \mbox{\boldmath {${W}$}} \mbox{\boldmath {${A}$}} \mbox{\boldmath {${\hat f}$}} = \mbox{\boldmath {${A}$}} ^{\rm H} \mbox{\boldmath {${W}$}} \mbox{\boldmath {${f}$}} .$$ (2.3)

For a comparative high polynomial degree $N_{\text{\tiny $\Pi$}}>M$ one expects to interpolate the given data $f_j\in \mathbb{C},\;j=0,\hdots,M-1,$ exactly. The (consistent) linear system ${A}$   ${\hat f}$$=$   ${f}$ is under-determined. One considers the damped minimisation problem

$$\Vert \mbox{\boldmath {${\hat f}$}} \Vert _{\mbox{\boldmath\scriptsize {${\hat W^{-1}}$}}} =\left(\... ...x{\boldmath {${A}$}} \mbox{\boldmath {${\hat f}$}} = \mbox{\boldmath {${f}$}},$$ (2.4)

which may incorporate 'damping factors' $\hat w_{\mbox{\boldmath\scriptsize {${k}$}}}> 0$, ${\hat W}$$:= {\, \rm diag}(\hat w_{\mbox{\boldmath\scriptsize {${k}$}}})_{\mbox{\boldmath\scriptsize {${k}$}}\in I_{\mbox{\boldmath\tiny {${N}$}}}}$. A smooth solution is favoured, i.e., a decay of the Fourier coefficients $\hat f_{\mbox{\boldmath\scriptsize {${k}$}}},\;\mbox{\boldmath {${k}$}}\in I_{\mbox{\boldmath\scriptsize {${N}$}}}$, for decaying damping factors $\hat w_{\mbox{\boldmath\scriptsize {${k}$}}}$. This problem is equivalent to the damped normal equation of second kind

$$\mbox{\boldmath {${A}$}} \mbox{\boldmath {${\hat W}$}} \mbox{\boldmath {${A}$}} ^{\rm H} \mbox{\boldmath {${\tilde f}$}} = \mbox{\boldmath {${f}$}} , \mbox{\boldmath {${\hat f}$}} = \mbox{\boldmath {${\hat W}$}} \mbox{\boldmath {${A}$}} ^{\rm H} \mbox{\boldmath {${\tilde f}$}} .$$ (2.5)