In applied mathematics, the non-uniform 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 has important applications in signal processing,[1] magnetic resonance imaging,[2] and the numerical solution of partial differential equations.
[3] 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.
into another sequence of complex numbers
, then equation (1) reduces to the discrete Fourier transform.
A similar set of NUDFTs can be defined by substituting
Unlike in the uniform case, however, this substitution is unrelated to the inverse Fourier transform.
The inversion of the NUDFT is a separate problem, discussed below.
-dimensional array of complex numbers
The multidimensional NUDFTs of types I, II, and III are defined analogously to the 1D case.
are arbitrarily distinct points in the z-plane.
Note that the NUDFT reduces to the DFT when the sampling points are located on the unit circle at equally spaced angles.
Expressing the above as a matrix, we get where As we can see, the NUDFT-I is characterized by
is nonsingular, we can get a unique inverse NUDFT-I as follows: Given
To solve this problem more efficiently, we first determine
directly by polynomial interpolation: Then
are the coefficients of the above interpolating polynomial.
are the fundamental polynomials: Expressing
by the Newton interpolation method, we get where
: The disadvantage of the Lagrange representation is that any additional point included will increase the order of the interpolating polynomial, leading to the need to recompute all the fundamental polynomials.
However, any additional point included in the Newton representation only requires the addition of one more term.
We can use a lower triangular system to solve
In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by While a naive application of equation (1) results in an
algorithms based on the fast Fourier transform (FFT) do exist.
Such algorithms are referred to as NUFFTs or NFFTs and have been developed based on oversampling and interpolation,[9][10][11][12] min-max interpolation,[2] and low-rank approximation.
[13] In general, NUFFTs leverage the FFT by converting the nonuniform problem into a uniform problem (or a sequence of uniform problems) to which the FFT can be applied.
[4] Software libraries for performing NUFFTs are available in 1D, 2D, and 3D.