In applied mathematics, the nonuniform discrete Fourier transform (NDFT) of a signal is a type of Fourier transform, related to a discrete Fourier transform or discretetime Fourier transform, but in which the input signal is not sampled at equallyspaced intervals. As a result of this, the computed Discrete Fourier Transform can also consist of unevenly sampled frequency values. It is however also possible to compute uniformly sampled frequency values from an unevenly sampled input signal.
As a generalized approach for nonuniform sampling, NDFT can help us to get the information of a finite length signal in frequency domain at any frequency. It can also be used to design the FIR filters as the role of DFT, no matter it's 1D or 2D.
One of the reason to adopt NDFT is that most signals have their energy distributed nonuniformly in the frequency domain. Therefore, a nonuniform sampling scheme could be more convenient and useful in lots of applications of Digital Signal Processing (DSP). For example, NDFT provides a variable spectral resolution controlled by the users.
Note that NDFT reduces to DFT when the sampling points are located on the unit circle at equally spaced angles.
1D NDFT
Definition
1D NDFT of a sequence x[n] of length N is^{[1]}
 X(z_k)=X(z)_{z=z_k}=\sum_{n=0}^{N1}x[n]z_k^{n},\quad k=0, 1, ..., N1,
where X(z) is the ztransform of x[n], and \{z_i\}_{i=0, 1, ..., N1} are arbitrarily distinct points in the zplane.
Expressing the above as matrix, we get
 \mathbf{X}=\mathbf{D}\mathbf{x}
where
 \mathbf{X}=\begin{bmatrix} X(z_0)\\ X(z_1)\\ \vdots\\ X(z_{N1}) \end{bmatrix},\quad \mathbf{x}=\begin{bmatrix} x[0]\\ x[1]\\ \vdots\\ x[N1] \end{bmatrix},\text{ and}\quad \mathbf{D}=\begin{bmatrix} 1 & z_0^{1} & z_0^{2} & \cdots & z_0^{(N1)}\\ 1 & z_1^{1} & z_1^{2} & \cdots & z_1^{(N1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & z_{N1}^{1} & z_{N1}^{2} & \cdots & \cdots & z_{N1}^{(N1)} \end{bmatrix}.
As we can see, the NDFT is characterized by \mathbf{D} and hence the N {z_k} points. If we further factorize det(\mathbf{D}), we can see that \mathbf{D} is nonsingular provided the N {z_k} points are distinct. If \mathbf{D} is nonsingular, we can get a unique inverse NDFT as following:
 \mathbf{x}=\mathbf{D^{1}}\mathbf{X}
Given \mathbf{X}\text{ and }\mathbf{D}, we can use Gaussian elimination to solve \mathbf{x}. However, the complexity of this method is O(N^3). To solve this problem more efficiently, we first determine X(z) directly by polynomial interpolation
 \hat X [k]=X(z_k),\quad k=0, 1, ..., N1,
then x[n] is the coefficients of the above interpolating polynomial which can be solved more efficiently. This is illustrated in the next subsection.
Solving The Inverse NDFT
Expressing X(z) as the Lagrange polynomial of order N1, we get
 X(z)=\sum_{k=0}^{N1}\frac{L_k(z)}{L_k(z_k)}\hat X [k],
where \{L_i(z)\}_{i=0, 1, ..., N1} are the fundamental polynomials:
 L_k(z)=\prod_{i\ne k}(1z_iz^{1}),\quad k=0, 1, ..., N1
Expressing X(z) by Newton interpolation method, we get
 X(z)=c_0 + c_1(1z_0z^{1}) + c2(1z_0z^{1})(1z_1z^{1}) + ... + C_{N1}\prod_{k=0}^{N2}(1z_kz^{1}),
where c_j is the divided difference of the jth order of \hat X [0], \hat X [1], ..., \hat X [j] with respect to z_0, z_1, ..., z_j:
 c_0 = \hat X [0],
 c_1 = \frac{\hat X [1]c_0}{1z_0z_1^{1}},
 c_2 = \frac{\hat X [2]c_0c_1(1z_0z^{1})}{(1z_0z_2^{1})(1z_1z_2^{1})},

 \vdots
The disadvantage of Lagrange representation is that any additional point included will increase the order of the interpolating polynomial, leading to the need of recomputing all the fundamental polynomials. However, any additional point included in Newton representation only require one more term.
We can use a lower triangular system to solve \{c_j\}:
 \mathbf{L}\mathbf{c}=\mathbf{X}
where
 \mathbf{X}=\begin{bmatrix} \hat X [0]\\ \hat X [1]\\ \vdots\\ \hat X [N1] \end{bmatrix},\quad \mathbf{c}=\begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_{N1} \end{bmatrix},\text{ and}\quad \mathbf{L}=\begin{bmatrix} 1 & 0 & 0 & 0 & \cdots & 0\\ 1 & (1z_0z_1^{1}) & 0 & 0 & \cdots & 0\\ 1 & (1z_0z_2^{1}) & (1z_0z_2^{1})(1z_1z_2^{1}) & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & (1z_0z_{N1}^{1}) & (1z_0z_{N1}^{1})(1z_1z_{N1}^{1}) & \cdots & \prod_{k=0}^{N2}(1z_kz_{N1}^{1}) \end{bmatrix}.
By the above equation, \{c_j\} can be computed within O(N^3) operations. In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by
 L_{k+1}(z) = \frac{(1z_{k+1}z^{1})}{(1z_kz^{1})}L_k(z),\quad k=0, 1, ..., N1
2D NDFT
2D NDFT of a sequence x[n_1,n_2] of size N_1\times N_2 is^{[2]}
 \hat X(z_{1k},z_{2k})=\sum_{n_1=0}^{N_11}\sum_{n_2=0}^{N_21}x[n_1,n_2]z_{1k}^{n_1}z_{2k}^{n_2},\quad k=0, 1, ..., N_1N_21,
where \hat X(z_{1k},z_{2k}) is the 2D ztransform of x[n_1,n_2], and (z_{1k},z_{2k}) are arbitrarily distinct N_1N_2 points in the 4D (z_1,z_2) space.
As in the 1D case, we can express the above equation as
 \mathbf{\hat X} = \mathbf{D}\mathbf{X},
and the matrix \mathbf{D} is also depends only on the choice of those sampling points. However, even if those sampling points are distinct, \mathbf{D} could still be singular. No rules for determining whether the matrix is nonsingular or not have been found. Therefore, for all implementation of 2D NDFT, we just check det(\mathbf{D}) for a specific set of sampling points. In general, the complexity of 2D NDFT O(N_1^3N_2^3).
Applications
The applications of NDFT are:
 Digital filter design
 Spectral analysis
 Antenna array design
 Antenna pattern synthesis with prescribed nulls
 Decoding of dualtone multifrequency(DTMF) signals
 Dualtone multifrequency tone detection
External links
Notes
References
 F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 325 360.
