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. X k = ∑ n = 0 N − 1 x n e − 2 π i p n ω k , 0 ≤ k ≤ N − 1 , {displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-2pi ip_{n}omega _{k}},quad 0leq kleq N-1,}     (1) 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 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 } are sample points and ω 0 , … , ω N − 1 ∈ [ 0 , N ] {displaystyle omega _{0},ldots ,omega _{N-1}in } are frequencies. Note that if p n = n / N {displaystyle p_{n}=n/N} and ω k = k {displaystyle omega _{k}=k} , then equation (1) reduces to the discrete Fourier transform. There are three types of NUDFTs. Inverse NUDFTs are defined by substituting − i {displaystyle -i} for + i {displaystyle +i} in equation (1). The multidimensional NUDFT converts a d {displaystyle d} -dimensional array of complex numbers x n {displaystyle x_{mathbf {n} }} into another d {displaystyle d} -dimensional array of complex numbers X k {displaystyle X_{mathbf {k} }} defined by where p k ∈ [ 0 , 1 ] d {displaystyle mathbf {p} _{mathbf {k} }in ^{d}} are sample points, ω n ∈ [ 0 , N 1 ] × [ 0 , N 2 ] × ⋯ × [ 0 , N d ] {displaystyle {oldsymbol {omega }}_{mathbf {n} }in imes imes cdots imes } are frequencies, and n = ( n 1 , n 2 , … , n d ) {displaystyle mathbf {n} =(n_{1},n_{2},ldots ,n_{d})} and k = ( k 1 , k 2 , … , k d ) {displaystyle mathbf {k} =(k_{1},k_{2},ldots ,k_{d})} are d {displaystyle d} -dimensional vectors of indices from 0 to N − 1 = ( N 1 − 1 , N 2 − 1 , … , N d − 1 ) {displaystyle mathbf {N} -1=(N_{1}-1,N_{2}-1,ldots ,N_{d}-1)} . The multidimensional NUDFTs of types I, II, and III are defined analogously to the 1D case. The NUDFT can be expressed as a Z-transform. The NUDFT of a sequence x [ n ] {displaystyle x} of length N {displaystyle N} is where X ( z ) {displaystyle X(z)} is the Z-transform of x [ n ] {displaystyle x} , and { z i } i = 0 , 1 , . . . , N − 1 {displaystyle {z_{i}}_{i=0,1,...,N-1}} 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.