Title :
Nonuniform fast Fourier transforms using min-max interpolation
Author :
Fessler, Jeffrey A. ; Sutton, Bradley P.
Author_Institution :
Dept. of Electr. Eng., Comput. Sci. & Biomed. Eng., Michigan Univ., Ann Arbor, MI, USA
fDate :
2/1/2003 12:00:00 AM
Abstract :
The fast Fourier transform (FFT) is used widely in signal processing for efficient computation of the FT of finite-length signals over a set of uniformly spaced frequency locations. However, in many applications, one requires nonuniform sampling in the frequency domain, i.e., a nonuniform FT. Several papers have described fast approximations for the nonuniform FT based on interpolating an oversampled FFT. This paper presents an interpolation method for the nonuniform FT that is optimal in the min-max sense of minimizing the worst-case approximation error over all signals of unit norm. The proposed method easily generalizes to multidimensional signals. Numerical results show that the min-max approach provides substantially lower approximation errors than conventional interpolation methods. The min-max criterion is also useful for optimizing the parameters of interpolation kernels such as the Kaiser-Bessel function.
Keywords :
fast Fourier transforms; frequency-domain analysis; interpolation; minimax techniques; multidimensional signal processing; signal sampling; FFT; Kaiser-Bessel function; frequency domain; min-max interpolation; multidimensional signals; nonuniform FT; nonuniform fast Fourier transforms; nonuniform sampling; signal processing; worst-case approximation error; Approximation error; Fast Fourier transforms; Frequency domain analysis; Image reconstruction; Interpolation; Iterative methods; Magnetic resonance imaging; Multidimensional signal processing; Multidimensional systems; Nonuniform sampling;
Journal_Title :
Signal Processing, IEEE Transactions on
DOI :
10.1109/TSP.2002.807005