# Fast Fourier transform at nonequispaced knots and applications

Daniel Potts
Technical University of Chemnitz
GERMANY

given at  strobl07 (18.06.07 10:45)
id:  659
length:  25min
status:  accepted
type:  talk
www:  http://www.tu-chemnitz.de/~potts
ABSTRACT:
We use the recently developed fast Fourier transform at
nonequispaced knots (NFFT) in a variety of applications.
The NFFT realises the fast computation of the sums
$$f(w_j) = \sum_{k\in [-N/2,N/2)^d\cap\mathbb Z^d} \hat f_k \; {\rm e}^{ -2 \pi \mbox{\rm \scriptsize{i}} k w_j} \qquad (j = 0,\ldots,M-1)$$
where $w_j \in [-1/2,1/2)^d$.
Software: http://www.tu-chemnitz.de/$\sim$potts/nfft

We discuss fast and reliable algorithm for the optimal interpolation of scattered data
on the torus ${\mathbb T}^d$ by multivariate trigonometric polynomials as well as the approximation problem.
The algorithm is based on a variant of the conjugate gradient method in
combination with the fast Fourier transforms for nonequispaced nodes.
We present a worst case analysis as well as results based on probabilistic arguments.
The main result is that under mild assumptions the total complexity for
solving the interpolation or approximation problem at $M$ arbitrary nodes is
of order ${\cal O}(N^d\log N+M)$.
Finally, we apply these methods in magnetic resonance imaging.
This talk based on joint results with S. Kunis (TU-Chemnitz), A. B\"ottcher (TU-Chemnitz) and H. Eggers
(Philips Hamburg).

Enter here the CODE for editing this talk:
If you have forgotten the CODE for your talk click here to send an email to the Webmaster!
NOTICE: In [EDIT-MODUS] you can also UPLOAD a presentation"