DFTS on irregular grids : the anterpolated DFT
Loading...
Authors
Henson, Van Emden
Subjects
Advisors
Date of Issue
1992
Date
1992
Publisher
Monterey, CA; Naval Postgraduate School
Language
en_US
Abstract
In many instances the discrete Fourier transform (DFT) is desired for a data set that occurs on an irregular grid. Commonly the data are interpolated to a regular grid, and a fast Fourier transform (FFT) is then applied. A drawback to this approach is that typically the data have unknown smoothness properties, so that the error in the interpolation is unknown. An alternative method is presented, based upon multilevel integration techniques introduced by A. Brandt. In this approach, the kernel, e(-iwt), is interpolated to the irregular grid, rather than interpolating the data to the regular grid. This may be accomplished by pre-multiplying the data by the adjoint of the interpolation matrix (a process dubbed anterpolation), producing a new regular-grid function, and then applying a standard FFT to the new function. Since the kernel is C infinity the operation may be carried out to any preselected accuracy. A simple optimization problem can be solved to select the problem parameters in an efficient way. If the requirements of accuracy are not strict, or if a small bandwidth is of interest, the method can be used in place of an FFT even when the data are regularly spaced.
Type
Technical Report
Description
Series/Report No
Department
Dept. of Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
NPS-MA-92-006
Sponsors
Funder
Format
14 p. ; 28 cm.