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 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 (NUDFT) transforms a sequence of N {\displaystyle N} complex numbers x 0 , … , x N − 1 {\displaystyle x_{0},\ldots ,x_{N-1}} into another sequence of complex numbers X 0 , … , X N − 1 {\displaystyle X_{0},\ldots ,X_{N-1}} defined by
where p 0 , … , p N − 1 ∈ [ 0 , 1 ] {\displaystyle p_{0},\ldots ,p_{N-1}\in [0,1]} are sample points and f 0 , … , f N − 1 ∈ [ 0 , N ] {\displaystyle f_{0},\ldots ,f_{N-1}\in [0,N]} are frequencies. Note that if p n = n / N {\displaystyle p_{n}=n/N} and f k = k {\displaystyle f_{k}=k} , then equation (1) reduces to the discrete Fourier transform. The NUDFT defines a linear operator. Fast numerical algorithms for evaluating this operator are known as the nonuniform fast Fourier transform (NUFFT).
Terminology and conventions Two related but distinct conventions are used in the literature to classify nonuniform Fourier transforms:
In harmonic analysis and signal processing, NUDFTs are commonly described from a series-evaluation viewpoint, in which transform types are distinguished by whether the sample locations or the frequencies are nonuniform. In numerical analysis and scientific computing, particularly in the context of NUFFT algorithms and software libraries, transforms are classified by the mapping direction between uniform and nonuniform representations, reflecting linear-operator structure and adjoint relationships.
NUDFT types The nonuniform discrete Fourier transform of type I (NUDFT-I) uses uniform sample points p n = n / N {\displaystyle p_{n}=n/N} but nonuniform (i.e. non-integer) frequencies f k {\displaystyle f_{k}} . This corresponds to evaluating a generalized Fourier series at equispaced points. It is also known as NDFT.. It is sometimes called forward NDFT and corresponds to NUFFT Type II (uniform to nonuniform) in the operator-based convention. The nonuniform discrete Fourier transform of type II (NUDFT-II) uses uniform (i.e. integer) frequencies f k = k {\displaystyle f_{k}=k} but nonuniform sample points p n {\displaystyle p_{n}} . This corresponds to evaluating a Fourier series at nonequispaced points. It is also known as adjoint NDFT or NUFFT Type I (nonuniform to uniform). The nonuniform discrete Fourier transform of type III (NUDFT-III) uses both nonuniform sample points p n {\displaystyle p_{n}} and nonuniform frequencies f k {\displaystyle f_{k}} . This corresponds to evaluating a generalized Fourier series at nonequispaced points. It is also known as NNDFT or NUFFT Type III (nonuniform to nonuniform).
Adjoint relationship In the operator-based convention in NUFFT, the Type I and Type II transforms are adjoint to each other in the sense of linear operators. Specifically, the NUFFT Type I transform is the Hermitian adjoint of the NUFFT Type II transform with respect to the standard inner products on the corresponding discrete spaces, up to scaling factors. A similar family of NUDFTs can be defined by substituting − i {\displaystyle -i} for + i {\displaystyle +i} in equation (1). 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.
… excerpt ends here. Continue reading the full article.
