The FFT is used widely for computing the Fourier transform (FT) at
uniformly- spaced frequency locations. However, in many imaging
applications one needs nonuniform frequency sampling. Several papers have
described fast approximations for the nonuniform FT based on interpolating
an oversampled FFT. We present a method for the nonuniform FT that is
optimal in a min-max sense. The proposed method minimizes the worst-case
approximation error over all unit-norm signals. Unlike some previous
methods for the nonuniform FT, the proposed method easily generalizes to
multidimensional signals. We illustrate applications of this method in
computed tomography and magnetic resonance imaging.
|