non-uniform discrete Fourier transform

The nonuniform discrete Fourier transform transforms a sequence of $N$ complex numbers $x\_0,\; \backslash ldots,\; x\_\{N-1\}$ into another sequence of complex numbers $X\_0,\; \backslash ldots,\; X\_\{N-1\}$ defined by

{{NumBlk|:|$X\_k\; =\; \backslash sum\_\{n=0\}^\{N-1\}\; x\_n\; e^\{-2\backslash pi\; i\; p\_n\; f\_k\},\; \backslash quad\; 0\; \backslash leq\; k\; \backslash leq\; N-1,$|{{EquationRef|1}}}}

where $p\_0,\; \backslash ldots,\; p\_\{N-1\}\; \backslash in\; [0,1]$ are sample points and $f\_0,\; \backslash ldots,\; f\_\{N-1\}\; \backslash in\; [0,N]$ are frequencies. Note that if $p\_n\; =\; n/N$ and $f\_k\; =\; k$, then equation ({{EquationNote|1}}) reduces to the discrete Fourier transform. There are three types of NUDFTs.{{cite journal|last1=Greengard|first1=Leslie|last2=Lee|first2=June-Yub|title=Accelerating the Nonuniform Fast Fourier Transform|journal=SIAM Review|date=January 2004|volume=46|issue=3|pages=443–454|doi=10.1137/S003614450343200X|bibcode=2004SIAMR..46..443G|citeseerx=10.1.1.227.3679}} Note that these types are not universal and different authors will refer to different types by different numbers.

• The nonuniform discrete Fourier transform of type I (NUDFT-I) uses uniform sample points $p\_n\; =\; n/N$ but nonuniform (i.e. non-integer) frequencies $f\_k$. This corresponds to evaluating a generalized Fourier series at equispaced points. It is also known as NDFT{{cite book|last1=Plonka|first1=Gerlind |author1-link=Gerlind Plonka|last2=Potts|first2=Daniel |last3=Steidl|first3=Gabriele|author3-link=Gabriele Steidl |last4=Tasche|first4=Manfred |title=Numerical Fourier Analysis |publisher=Birkhäuser |date=2019 |isbn=978-3-030-04306-3 |doi=10.1007/978-3-030-04306-3}} or forward NDFT {{cite web |last1=PyNUFFT Services |title=Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation |url=https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html |website=pynufft.readthedocs.io |access-date=27 February 2024}}{{cite web |last1=The Simons Foundation |title=Mathematical definitions of transforms — finufft 2.2.0 documentation |url=https://finufft.readthedocs.io/en/latest/math.html#math |website=finufft.readthedocs.io |access-date=27 February 2024}}
• The nonuniform discrete Fourier transform of type II (NUDFT-II) uses uniform (i.e. integer) frequencies $f\_k\; =\; k$ but nonuniform sample points $p\_n$. This corresponds to evaluating a Fourier series at nonequispaced points. It is also known as adjoint NDFT.
• The nonuniform discrete Fourier transform of type III (NUDFT-III) uses both nonuniform sample points $p\_n$ and nonuniform frequencies $f\_k$. This corresponds to evaluating a generalized Fourier series at nonequispaced points. It is also known as NNDFT.

A similar set of NUDFTs can be defined by substituting $-i$ for $+i$ in equation ({{EquationNote|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.

The multidimensional NUDFT converts a $d$-dimensional array of complex numbers $x\_\{\backslash mathbf\{n\}\}$ into another $d$-dimensional array of complex numbers $X\_\{\backslash mathbf\{k\}\}$ defined by

:$X\_\{\backslash mathbf\{k\}\}\; =\; \backslash sum\_\{\backslash mathbf\{n\}=\backslash mathbf\{0\}\}^\{\backslash mathbf\{N\}-1\}\; x\_\{\backslash mathbf\{n\}\}\; e^\{-2\backslash pi\; i\; \backslash mathbf\{p\}\_\{\backslash mathbf\{n\}\}\; \backslash cdot\; \backslash boldsymbol\{f\}\_\{\backslash mathbf\{k\}\}\}$

where $\backslash mathbf\{p\}\_\{\backslash mathbf\{n\}\}\; \backslash in\; [0,1]^d$ are sample points, $\backslash boldsymbol\{f\}\_\{\backslash mathbf\{k\}\}\; \backslash in\; [0,N\_1]\; \backslash times\; [0,N\_2]\; \backslash times\; \backslash cdots\; \backslash times\; [0,N\_d]$ are frequencies, and $\backslash mathbf\{n\}\; =\; (n\_1,n\_2,\backslash ldots,n\_d)$ and $\backslash mathbf\{k\}\; =\; (k\_1,k\_2,\backslash ldots,k\_d)$ are $d$-dimensional vectors of indices from 0 to $\backslash mathbf\{N\}-1\; =\; (N\_1-1,N\_2-1,\backslash ldots,N\_d-1)$. The multidimensional NUDFTs of types I, II, and III are defined analogously to the 1D case.

The NUDFT-I can be expressed as a Z-transform.{{cite book|last1=Marvasti|first1=Farokh|title=Nonuniform Sampling: Theory and Practice|date=2001|publisher=Springer|location=New York|isbn=978-1-4615-1229-5|pages=325–360}} The NUDFT-I of a sequence $x[n]$ of length $N$ is

:$X(z\_k)=X(z)|\_\{z=z\_k\}=\backslash sum\_\{n=0\}^\{N-1\}x[n]z\_k^\{-n\},\backslash quad\; k=0,\; 1,\; ...,\; N-1,$

where $X(z)$ is the Z-transform of $x[n]$, and $\backslash \{z\_i\backslash \}\_\{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.

Expressing the above as a matrix, we get

:$\backslash mathbf\{X\}=\backslash mathbf\{D\}\backslash mathbf\{x\}$

where

:$$

\mathbf{X}=\begin{bmatrix}

X(z_0)\\

X(z_1)\\

\vdots\\

X(z_{N-1})

\end{bmatrix},\quad

\mathbf{x}=\begin{bmatrix}

x[0]\\

x[1]\\

\vdots\\

x[N-1]

\end{bmatrix},\text{ and}\quad

\mathbf{D}=\begin{bmatrix}

1 & z_0^{-1} & z_0^{-2} & \cdots & z_0^{-(N-1)}\\

1 & z_1^{-1} & z_1^{-2} & \cdots & z_1^{-(N-1)}\\

\vdots & \vdots & \vdots & \ddots & \vdots\\

1 & z_{N-1}^{-1} & z_{N-1}^{-2} & \cdots & z_{N-1}^{-(N-1)}

\end{bmatrix}.

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

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

Given $\backslash mathbf\{X\}\backslash text\{\; and\; \}\backslash mathbf\{D\}$, we can use Gaussian elimination to solve for $\backslash 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:

:$\backslash hat\; X\; [k]=X(z\_k),\backslash quad\; k=0,\; 1,\; ...,\; N-1$.

Then $x[n]$ are the coefficients of the above interpolating polynomial.

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

:$X(z)=\backslash sum\_\{k=0\}^\{N-1\}\backslash frac\{L\_k(z)\}\{L\_k(z\_k)\}\backslash hat\; X\; [k],$

where $\backslash \{L\_i(z)\backslash \}\_\{i=0,\; 1,\; ...,\; N-1\}$ are the fundamental polynomials:

:$L\_k(z)=\backslash prod\_\{i\backslash ne\; k\}(1-z\_iz^\{-1\}),\backslash quad\; k=0,\; 1,\; ...,\; N-1$.

Expressing $X(z)$ by the Newton interpolation method, we get

:$X(z)=c\_0\; +\; c\_1(1-z\_0z^\{-1\})\; +\; c\_2(1-z\_0z^\{-1\})(1-z\_1z^\{-1\})\; +\; \backslash cdots\; +\; c\_\{N-1\}\backslash prod\_\{k=0\}^\{N-2\}(1-z\_kz^\{-1\}),$

where $c\_j$ is the divided difference of the $j$th order of $\backslash hat\; X\; [0],\; \backslash hat\; X\; [1],\; ...,\; \backslash hat\; X\; [j]$ with respect to $z\_0,\; z\_1,\; ...,\; z\_j$:

:$c\_0\; =\; \backslash hat\; X\; [0],$

:$c\_1\; =\; \backslash frac\{\backslash hat\; X\; [1]-c\_0\}\{1-z\_0z\_1^\{-1\}\},$

:$c\_2\; =\; \backslash frac\{\backslash hat\; X\; [2]-c\_0-c\_1(1-z\_0z^\{-1\})\}\{(1-z\_0z\_2^\{-1\})(1-z\_1z\_2^\{-1\})\},$

::$\backslash 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 $\backslash \{c\_j\backslash \}$:

:$\backslash mathbf\{L\}\backslash mathbf\{c\}=\backslash mathbf\{X\}$

where

:$$

\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 & \cdots & 0\\

1 & (1-z_0z_1^{-1}) & 0 & \cdots & 0\\

1 & (1-z_0z_2^{-1}) & (1-z_0z_2^{-1})(1-z_1z_2^{-1}) & \cdots & 0\\

\vdots & \vdots & \vdots & \ddots & \vdots\\

1 & (1-z_0z_{N-1}^{-1}) & (1-z_0z_{N-1}^{-1})(1-z_1z_{N-1}^{-1}) & \cdots & \prod_{k=0}^{N-2}(1-z_kz_{N-1}^{-1})

\end{bmatrix}.

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

:$L\_\{k+1\}(z)\; =\; \backslash frac\{(1-z\_\{k+1\}z^\{-1\})\}\{(1-z\_kz^\{-1\})\}L\_k(z),\backslash quad\; k=0,\; 1,\; ...,\; N-1$.

While a naive application of equation ({{EquationNote|1}}) results in an $O(N^2)$ algorithm for computing the NUDFT, $O(N\; \backslash log\; N)$ 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,{{cite thesis|type=PhD|last=Dutt|first=Alok|title=Fast Fourier Transforms for Nonequispaced Data|date=May 1993|publisher=Yale University|url=https://cpsc.yale.edu/sites/default/files/files/tr981.pdf}}{{cite journal|last1=Dutt|first1=Alok|last2=Rokhlin|first2=Vladimir|title=Fast Fourier Transforms for Nonequispaced Data|journal=SIAM Journal on Scientific Computing|date=November 1993|volume=14|issue=6|pages=1368–1393|doi=10.1137/0914081|bibcode=1993SJSC...14.1368D }}{{cite journal|last1=Potts|first1=Daniel|last2=Steidl|first2=Gabriele|author2-link= Gabriele Steidl |title=Fast Summation at Nonequispaced Knots by NFFT|journal=SIAM Journal on Scientific Computing|date=January 2003|volume=24|issue=6|pages=2013–2037|doi=10.1137/S1064827502400984|bibcode=2003SJSC...24.2013P }}{{cite journal|last1=Boyd|first1=John P|title=A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid|journal=Journal of Computational Physics|date=December 1992|volume=103|issue=2|pages=243–257|doi=10.1016/0021-9991(92)90399-J|bibcode=1992JCoPh.103..243B|url=https://deepblue.lib.umich.edu/bitstream/2027.42/29694/1/0000026.pdf|hdl=2027.42/29694|hdl-access=free}} min-max interpolation, and low-rank approximation.{{cite journal|last1=Ruiz-Antolín|first1=Diego|last2=Townsend|first2=Alex|title=A Nonuniform Fast Fourier Transform Based on Low Rank Approximation|journal=SIAM Journal on Scientific Computing|date=20 February 2018|volume=40|issue=1|pages=A529–A547|doi=10.1137/17M1134822|arxiv=1701.04492|bibcode=2018SJSC...40A.529R |url=https://repositorio.unican.es/xmlui/bitstream/handle/10902/13767/ANonuniform.pdf|hdl=10902/13767}} 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.{{cite web|title=NUFFT page|url=https://cims.nyu.edu/cmcl/nufft/nufft.html|website=cims.nyu.edu}}{{cite web|title=NFFT|url=http://www.nfft.org/|website=www.nfft.org|language=en}}{{cite web|title=MikaelSlevinsky/FastTransforms.jl|url=https://github.com/MikaelSlevinsky/FastTransforms.jl|website=GitHub|language=en|date=2019-02-13}}{{cite web|title=chebfun/chebfun|url=https://github.com/chebfun/chebfun|website=GitHub|language=en|date=2019-02-07}}

The applications of the NUDFT include:

• Digital signal processing
• Magnetic resonance imaging
• Numerical partial differential equations
• Semi-Lagrangian schemes
• Spectral methods
• Spectral analysis
• Digital filter design
• Antenna array design
• Detection and decoding of dual-tone multi-frequency (DTMF) signals

• Discrete Fourier transform
• Fast Fourier transform
• Least-squares spectral analysis
• Lomb–Scargle periodogram
• Spectral estimation
• Unevenly spaced time series

{{Reflist}}

• [http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/PIRODDI1/NUFT/NUFT.html Non-Uniform Fourier Transform: A Tutorial].
• [http://www-user.tu-chemnitz.de/~potts/nfft/guide3/html/index.html NFFT 3.0 – Tutorial]
• [https://cims.nyu.edu/cmcl/nufft/nufft.html NUFFT software library]

Category:Fourier analysis

Category:Transforms

Category:Digital signal processing