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,[1] magnetic resonance imaging,[2] and the numerical solution of partial
differential equations.[3]

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 transforms a sequence of complex numbers into another sequence of complex numbers
defined by

(1)
 

   
 

where are sample points and are frequencies. Note that if and , then equation (1)
reduces to the discrete Fourier transform. There are three types of NUDFTs.[4]

The nonuniform discrete Fourier transform of type I (NUDFT-I) uses uniform sample points but nonuniform (i.e. non-integer)
frequencies . This corresponds to evaluating a generalized Fourier series at equispaced points. It is also known as NDFT.[5]
The nonuniform discrete Fourier transform of type II (NUDFT-II) uses uniform (i.e. integer) frequencies but nonuniform sample
points . 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 and nonuniform frequencies
. 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 for 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.

Multidimensional NUDFT
The multidimensional NUDFT converts a -dimensional array of complex numbers into another -dimensional array of complex numbers defined
by

where are sample points, are frequencies, and and

are -dimensional vectors of indices from 0 to . The multidimensional NUDFTs of types I, II, and III are
defined analogously to the 1D case.[4]

Relationship to Z-transform
The NUDFT-I can be expressed as a Z-transform.[6] The NUDFT-I of a sequence of length is

where is the Z-transform of , and 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

where
Direct inversion of the NUDFT-I

As we can see, the NUDFT-I is characterized by and hence the points. If we further factorize , we can see that is nonsingular provided
the points are distinct. If is nonsingular, we can get a unique inverse NUDFT-I as follows:

Given , we can use Gaussian elimination to solve for . However, the complexity of this method is . To solve this problem more
efficiently, we first determine directly by polynomial interpolation:

Then are the coefficients of the above interpolating polynomial.

Expressing as the Lagrange polynomial of order , we get

where are the fundamental polynomials:

Expressing by the Newton interpolation method, we get

where is the divided difference of the th order of with respect to :

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 :

where

By the above equation, can be computed within operations. In this way Newton interpolation is more efficient than Lagrange Interpolation
unless the latter is modified by
 .

Nonuniform fast Fourier transform

While a naive application of equation (1) results in an algorithm for computing the NUDFT, 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,[7][8][9][10] min-max interpolation,[2] and low-rank approximation.[11] 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.[4] Software libraries for performing NUFFTs are
available in 1D, 2D, and 3D.[12][13][14][15]

Applications
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

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

References
1. Bagchi, Sonali; Mitra, Sanjit K. (1999). The Nonuniform Discrete 8. Dutt, Alok; Rokhlin, Vladimir (November 1993). "Fast Fourier
Fourier Transform and Its Applications in Signal Processing. Transforms for Nonequispaced Data". SIAM Journal on
Boston, MA: Springer US. ISBN 978-1-4615-4925-3. Scientific Computing. 14 (6): 1368–1393. doi:10.1137/0914081
2. Fessler, J.A.; Sutton, B.P. (February 2003). "Nonuniform fast (https://doi.org/10.1137%2F0914081).
fourier transforms using min-max interpolation". IEEE 9. Potts, Daniel; Steidl, Gabriele (January 2003). "Fast Summation
Transactions on Signal Processing. 51 (2): 560–574. at Nonequispaced Knots by NFFT". SIAM Journal on Scientific
Bibcode:2003ITSP...51..560F (https://ui.adsabs.harvard.edu/ab Computing. 24 (6): 2013–2037.
s/2003ITSP...51..560F). doi:10.1109/TSP.2002.807005 (https://d doi:10.1137/S1064827502400984 (https://doi.org/10.1137%2FS
oi.org/10.1109%2FTSP.2002.807005). hdl:2027.42/85840 (http 1064827502400984).
s://hdl.handle.net/2027.42%2F85840). 10. Boyd, John P (December 1992). "A fast algorithm for
3. Lee, June-Yub; Greengard, Leslie (June 2005). "The type 3 Chebyshev, Fourier, and sinc interpolation onto an irregular
nonuniform FFT and its applications". Journal of Computational grid" (https://deepblue.lib.umich.edu/bitstream/2027.42/29694/1/
Physics. 206 (1): 1–5. Bibcode:2005JCoPh.206....1L (https://ui.a 0000026.pdf) (PDF). Journal of Computational Physics. 103 (2):
dsabs.harvard.edu/abs/2005JCoPh.206....1L). 243–257. Bibcode:1992JCoPh.103..243B (https://ui.adsabs.har
doi:10.1016/j.jcp.2004.12.004 (https://doi.org/10.1016%2Fj.jcp.2 vard.edu/abs/1992JCoPh.103..243B). doi:10.1016/0021-
004.12.004). 9991(92)90399-J (https://doi.org/10.1016%2F0021-9991%289
4. Greengard, Leslie; Lee, June-Yub (January 2004). "Accelerating 2%2990399-J). hdl:2027.42/29694 (https://hdl.handle.net/2027.4
the Nonuniform Fast Fourier Transform". SIAM Review. 46 (3): 2%2F29694).
443–454. Bibcode:2004SIAMR..46..443G (https://ui.adsabs.harv 11. Ruiz-Antolín, Diego; Townsend, Alex (20 February 2018). "A
ard.edu/abs/2004SIAMR..46..443G). CiteSeerX 10.1.1.227.3679 Nonuniform Fast Fourier Transform Based on Low Rank
(https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.227. Approximation" (https://repositorio.unican.es/xmlui/bitstream/han
3679). doi:10.1137/S003614450343200X (https://doi.org/10.113 dle/10902/13767/ANonuniform.pdf) (PDF). SIAM Journal on
7%2FS003614450343200X). Scientific Computing. 40 (1): A529–A547. arXiv:1701.04492 (htt
5. Plonka, Gerlind; Potts, Daniel; Steidl, Gabriele; Tasche, Manfred ps://arxiv.org/abs/1701.04492). doi:10.1137/17M1134822 (http
(2019). Numerical Fourier Analysis. Birkhäuser. s://doi.org/10.1137%2F17M1134822). hdl:10902/13767 (https://
doi:10.1007/978-3-030-04306-3 (https://doi.org/10.1007%2F978 hdl.handle.net/10902%2F13767).
-3-030-04306-3). ISBN 978-3-030-04306-3. 12. "NUFFT page" (https://cims.nyu.edu/cmcl/nufft/nufft.html).
6. Marvasti, Farokh (2001). Nonuniform Sampling: Theory and cims.nyu.edu.
Practice. New York: Springer. pp. 325–360. ISBN 978-1-4615- 13. "NFFT" (http://www.nfft.org/). www.nfft.org.
1229-5. 14. "MikaelSlevinsky/FastTransforms.jl" (https://github.com/MikaelSl
7. Dutt, Alok (May 1993). Fast Fourier Transforms for evinsky/FastTransforms.jl). GitHub. 2019-02-13.
Nonequispaced Data (https://cpsc.yale.edu/sites/default/files/file 15. "chebfun/chebfun" (https://github.com/chebfun/chebfun). GitHub.
s/tr981.pdf) (PDF) (PhD). Yale University. 2019-02-07.

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Non-uniform_discrete_Fourier_transform&oldid=1070910523"