Next: NFFT
Up: NDFT
Previous: Equispaced knots
In general there is no simple inversion formula, hence one deals with the following reconstruction or recovery problem.
Given the values
at non equispaced knots
![$ {x}$](img41.png)
, the aim
is to reconstruct a trigonometric polynomial
resp. its Fourier-coefficients
with
Often, the number of nodes
and the dimension of the space of the polynomials
do not coincide, i.e., the matrix
is rectangular. A standard
method is to use the Moore-Penrose-pseudoinverse solution
![$ {\hat f}$](img70.png)
which solves the general linear least squares problem, see e.g.
[3, p. 15],
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
the linear
system
![$ {\hat f}$](img70.png)
is over-determined, so that in general
the given data
will be only approximated
up to the residual
![$ {r}$](img101.png)
![$ :=$](img102.png)
![$ {f}$](img99.png)
![$ -$](img103.png)
. One considers the
weighted approximation problem
which may incorporate weights
,
![$ {W}$](img106.png)
,
to compensate for clusters in the sampling set
.
This problem is equivalent to the weighted normal equation of first kind
For a comparative high polynomial degree
one expects to interpolate the
given data
exactly. The (consistent)
linear system
![$ {\hat f}$](img70.png)
is under-determined. One considers the
damped minimisation problem
which may incorporate 'damping factors'
,
![$ {\hat W}$](img115.png)
. A smooth solution is favoured, i.e.,
a decay of the Fourier coefficients
, for
decaying damping factors
. This problem is equivalent to the
damped normal equation of second kind
Next: NFFT
Up: NDFT
Previous: Equispaced knots
Stefan Kunis
2004-09-03