Direct inversion of the NUDFT-I

As we can see, the NUDFT-I is characterized by ${\displaystyle \mathbf {D} }$ and hence the ${\displaystyle N}$ ${\displaystyle {z_{k}}}$ points. If we further factorize ${\displaystyle \det(\mathbf {D} )}$, we can see that ${\displaystyle \mathbf {D} }$ is nonsingular provided the ${\displaystyle N}$ ${\displaystyle {z_{k}}}$ points are distinct. If ${\displaystyle \mathbf {D} }$ is nonsingular, we can get a unique inverse NUDFT-I as follows:

${\displaystyle \mathbf {x} =\mathbf {D^{-1}} \mathbf {X} }$.

Given ${\displaystyle \mathbf {X} {\text{ and }}\mathbf {D} }$, we can use Gaussian elimination to solve for ${\displaystyle \mathbf {x} }$. However, the complexity of this method is ${\displaystyle O(N^{3})}$. To solve this problem more efficiently, we first determine ${\displaystyle X(z)}$ directly by polynomial interpolation:

${\displaystyle {\hat {X}}[k]=X(z_{k}),\quad k=0,1,...,N-1}$.

Then ${\displaystyle x[n]}$ are the coefficients of the above interpolating polynomial.

Expressing ${\displaystyle X(z)}$ as the Lagrange polynomial of order ${\displaystyle N-1}$, we get

${\displaystyle X(z)=\sum _{k=0}^{N-1}{\frac {L_{k}(z)}{L_{k}(z_{k})}}{\hat {X}}[k],}$

where ${\displaystyle \{L_{i}(z)\}_{i=0,1,...,N-1}}$ are the fundamental polynomials:

${\displaystyle L_{k}(z)=\prod _{i\neq k}(1-z_{i}z^{-1}),\quad k=0,1,...,N-1}$.

Expressing ${\displaystyle X(z)}$ by the Newton interpolation method, we get

${\displaystyle X(z)=c_{0}+c_{1}(1-z_{0}z^{-1})+c_{2}(1-z_{0}z^{-1})(1-z_{1}z^{-1})+\cdots +c_{N-1}\prod _{k=0}^{N-2}(1-z_{k}z^{-1}),}$

where ${\displaystyle c_{j}}$ is the divided difference of the ${\displaystyle j}$th order of ${\displaystyle {\hat {X}}[0],{\hat {X}}[1],...,{\hat {X}}[j]}$ with respect to ${\displaystyle z_{0},z_{1},...,z_{j}}$:

${\displaystyle c_{0}={\hat {X}}[0],}$

${\displaystyle c_{1}={\frac {{\hat {X}}[1]-c_{0}}{1-z_{0}z_{1}^{-1}}},}$

${\displaystyle c_{2}={\frac {{\hat {X}}[2]-c_{0}-c_{1}(1-z_{0}z^{-1})}{(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})}},}$

${\displaystyle \vdots }$

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 ${\displaystyle \{c_{j}\}}$:

${\displaystyle \mathbf {L} \mathbf {c} =\mathbf {X} }$

where

${\displaystyle \mathbf {X} ={\begin{bmatrix}{\hat {X}}[0]\\{\hat {X}}[1]\\\vdots \\{\hat {X}}[N-1]\end{bmatrix}},\quad \mathbf {c} ={\begin{bmatrix}c_{0}\\c_{1}\\\vdots \\c_{N-1}\end{bmatrix}},{\text{ and}}\quad \mathbf {L} ={\begin{bmatrix}1&0&0&0&\cdots &0\\1&(1-z_{0}z_{1}^{-1})&0&0&\cdots &0\\1&(1-z_{0}z_{2}^{-1})&(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&(1-z_{0}z_{N-1}^{-1})&(1-z_{0}z_{N-1}^{-1})(1-z_{1}z_{N-1}^{-1})&\cdots &\prod _{k=0}^{N-2}(1-z_{k}z_{N-1}^{-1})\end{bmatrix}}.}$

By the above equation, ${\displaystyle \{c_{j}\}}$ can be computed within ${\displaystyle O(N^{2})}$ operations. In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by

${\displaystyle L_{k+1}(z)={\frac {(1-z_{k+1}z^{-1})}{(1-z_{k}z^{-1})}}L_{k}(z),\quad k=0,1,...,N-1}$.