Toni Volkmer: Taylor and rank-1 lattice based nonequispaced fast Fourier transform

Author(s):

Toni Volkmer

Title:

Toni Volkmer: Taylor and rank-1 lattice based nonequispaced fast Fourier transform

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 05, 2013

Mathematics Subject Classification:

65T50

[Discrete and fast Fourier transforms]

Abstract:

The nonequispaced fast Fourier transform (NFFT) allows the fast approximate evaluation of trigonometric polynomials with frequencies supported on full box-shaped grids at arbitrary sampling nodes. Due to the curse of dimensionality, the total number of frequencies and thus, the total arithmetic complexity can already be very large for small refinements at medium dimensions. In this paper, we present an approach for the fast approximate evaluation of trigonometric polynomials with frequencies supported on an arbitrary subset of the full grid at arbitrary sampling nodes, which is based on Taylor expansion and rank-1 lattice methods. For the special case of symmetric hyperbolic cross index sets in frequency domain, we present error estimates and numerical results.

Keywords:

nonequispaced fast Fourier transform, NFFT, FFT, rank-1 lattice, Taylor expansion

Language:

English

Publication time:

02/2013