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.
Definition.
The "nonuniform discrete Fourier transform" transforms a sequence of formula_1 complex numbers formula_2 into another sequence of complex numbers formula_3 defined by
where formula_4 are sample points and formula_5 are frequencies. Note that if formula_6 and formula_7, then equation () reduces to the discrete Fourier transform. There are three types of NUDFTs.
A similar set of NUDFTs can be defined by substituting formula_14 for formula_15 in equation ().
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.
Multidimensional NUDFT.
The multidimensional NUDFT converts a formula_16-dimensional array of complex numbers formula_17 into another formula_16-dimensional array of complex numbers formula_19 defined by
where formula_21 are sample points, formula_22 are frequencies, and formula_23 and formula_24 are formula_16-dimensional vectors of indices from 0 to formula_26. The multidimensional NUDFTs of types I, II, and III are defined analogously to the 1D case.
Relationship to Z-transform.
The NUDFT can be expressed as a Z-transform. The NUDFT of a sequence formula_27 of length formula_1 is
where formula_30 is the Z-transform of formula_27, and formula_32 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
Direct inversion of the NUDFT.
As we can see, the NUDFT is characterized by formula_35 and hence the formula_1 formula_37 points. If we further factorize formula_38, we can see that formula_35 is nonsingular provided the formula_1 formula_37 points are distinct. If formula_35 is nonsingular, we can get a unique inverse NUDFT as follows:
Given formula_44, we can use Gaussian elimination to solve for formula_45. However, the complexity of this method is formula_46. To solve this problem more efficiently, we first determine formula_30 directly by polynomial interpolation:
Then formula_27 are the coefficients of the above interpolating polynomial.
Expressing formula_30 as the Lagrange polynomial of order formula_51, we get
where formula_53 are the fundamental polynomials:
Expressing formula_30 by the Newton interpolation method, we get
where formula_57 is the divided difference of the formula_58th order of formula_59 with respect to formula_60:
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 formula_65:
where
By the above equation, formula_65 can be computed within formula_69 operations. In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by
Nonuniform fast Fourier transform.
While a naive application of equation () results in an formula_69 algorithm for computing the NUDFT, formula_72 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, min-max interpolation, and low-rank approximation. 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. Software libraries for performing NUFFTs are available in 1D, 2D, and 3D.
Applications.
The applications of the NUDFT include: