Non-uniform discrete Fourier transform

In applied mathematics, the nonuniform discrete Fourier transform (NUDFT or NDFT) of a signal is a type of Fourier transform, related to a discrete Fourier transform or discrete-time Fourier transform, but in which the input signal is not sampled at equally spaced points or frequencies (or both). It is a generalization of the shifted DFT. It has important applications in signal processing, magnetic resonance imaging, and the numerical solution of partial differential equations. As a generalized approach for nonuniform sampling, the NUDFT allows one to obtain frequency domain information of a finite length signal at any frequency. One of the reasons to adopt the NUDFT is that many signals have their energy distributed nonuniformly in the frequency domain. Therefore, a nonuniform sampling scheme could be more convenient and useful in many digital signal processing applications. For example, the NUDFT provides a variable spectral resolution controlled by the user. The nonuniform discrete Fourier transform transforms a sequence of complex numbers into another sequence of complex numbers defined by where are sample points and are frequencies. Note that if and , then equation () reduces to the discrete Fourier transform. There are three types of NUDFTs. The nonuniform discrete Fourier transform of type I (NUDFT-I) uses uniform sample points but nonuniform (i.e. non-integer) frequencies . This corresponds to evaluating a generalized Fourier series at equispaced points. It is also known as NDFT. The nonuniform discrete Fourier transform of type II (NUDFT-II) uses uniform (i.e. integer) frequencies but nonuniform sample points . This corresponds to evaluating a Fourier series at nonequispaced points. It is also known as adjoint NDFT. The nonuniform discrete Fourier transform of type III (NUDFT-III) uses both nonuniform sample points and nonuniform frequencies . This corresponds to evaluating a generalized Fourier series at nonequispaced points. It is also known as NNDFT. A similar set of NUDFTs can be defined by substituting for in equation ().