Inverse NDFT

Next: NFFT Up: NDFT Previous: Equispaced knots

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 $_j\; (j=0,\hdots,M-1)$ , the aim is to reconstruct a trigonometric polynomial resp. its Fourier-coefficients $\hat f_{\mbox{\boldmath\scriptsize {${k}$}}}\;(\mbox{\boldmath {${k}$}} \in I_{\mbox{\boldmath\scriptsize {${N}$}}})$ with

$\displaystyle 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 and the dimension of the space of the polynomials $N_{\text{\tiny $\Pi$}}$ do not coincide, i.e., the matrix 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],

$\displaystyle \Vert$ $\displaystyle \mbox{\boldmath {${\hat f}$}}$ $\displaystyle \Vert _2 \rightarrow \min$ subject to $\displaystyle \quad \Vert$ $\displaystyle \mbox{\boldmath {${f}$}}$ $\displaystyle -$ $\displaystyle \mbox{\boldmath {${A}$}}$ $\displaystyle \mbox{\boldmath {${\hat f}$}}$ $\displaystyle \Vert _2=\min$ for $\displaystyle \mbox{\boldmath {${f}$}}$ $\displaystyle \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 ${\hat f}$ $\approx$ 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 ${\hat f}$ . One considers the weighted approximation problem

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

which may incorporate weights , $:={\, \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

$\displaystyle \mbox{\boldmath {${A}$}}$ $\displaystyle ^{\rm H}$ $\displaystyle \mbox{\boldmath {${W}$}}$ $\displaystyle \mbox{\boldmath {${A}$}}$ $\displaystyle \mbox{\boldmath {${\hat f}$}}$ $\displaystyle =$ $\displaystyle \mbox{\boldmath {${A}$}}$ $\displaystyle ^{\rm H}$ $\displaystyle \mbox{\boldmath {${W}$}}$ $\displaystyle \mbox{\boldmath {${f}$}}$ $\displaystyle .$

(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 ${\hat f}$ is under-determined. One considers the damped minimisation problem

$\displaystyle \Vert$ $\displaystyle \mbox{\boldmath {${\hat f}$}}$ $\displaystyle \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

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

(2.5)

Next: NFFT Up: NDFT Previous: Equispaced knots

Stefan Kunis 2004-09-03