Non-uniform discrete Fourier transform

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

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.
  • 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.
  • 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.

Inverse NUDFTs are defined by substituting for in equation (1).

Multidimensional NUDFT[edit]

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[edit]

The NUDFT can be expressed as a Z-transform.[5] The NUDFT 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[edit]

As we can see, the NUDFT 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 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[edit]

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,[6][7][8] min-max interpolation,[9] and low-rank approximation.[10] 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.[11][12][13][14]

Applications[edit]

The applications of the NUDFT include:

See also[edit]

References[edit]

  1. ^ Bagchi, Sonali; Mitra, Sanjit K. (1999). The Nonuniform Discrete Fourier Transform and Its Applications in Signal Processing. Boston, MA: Springer US. ISBN 978-1-4615-4925-3. 
  2. ^ Fessler, J.A.; Sutton, B.P. (February 2003). "Nonuniform fast fourier transforms using min-max interpolation". IEEE Transactions on Signal Processing. 51 (2): 560–574. doi:10.1109/TSP.2002.807005. 
  3. ^ Lee, June-Yub; Greengard, Leslie (June 2005). "The type 3 nonuniform FFT and its applications". Journal of Computational Physics. 206 (1): 1–5. doi:10.1016/j.jcp.2004.12.004. 
  4. ^ a b c Greengard, Leslie; Lee, June-Yub (January 2004). "Accelerating the Nonuniform Fast Fourier Transform". SIAM Review. 46 (3): 443–454. doi:10.1137/S003614450343200X. 
  5. ^ Marvasti, Farokh (2001). Nonuniform Sampling: Theory and Practice. New York: Springer. pp. 325–360. ISBN 978-1-4615-1229-5. 
  6. ^ Dutt, A.; Rokhlin, V. (November 1993). "Fast Fourier Transforms for Nonequispaced Data". SIAM Journal on Scientific Computing. 14 (6): 1368–1393. doi:10.1137/0914081. 
  7. ^ Potts, Daniel; Steidl, Gabriele (January 2003). "Fast Summation at Nonequispaced Knots by NFFT". SIAM Journal on Scientific Computing. 24 (6): 2013–2037. doi:10.1137/S1064827502400984. 
  8. ^ Boyd, John P (December 1992). "A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid". Journal of Computational Physics. 103 (2): 243–257. doi:10.1016/0021-9991(92)90399-J. 
  9. ^ Fessler, J.A.; Sutton, B.P. (February 2003). "Nonuniform fast fourier transforms using min-max interpolation". IEEE Transactions on Signal Processing. 51 (2): 560–574. doi:10.1109/TSP.2002.807005. 
  10. ^ Ruiz-Antolín, Diego; Townsend, Alex (20 February 2018). "A Nonuniform Fast Fourier Transform Based on Low Rank Approximation". SIAM Journal on Scientific Computing. 40 (1): A529–A547. arXiv:1701.04492Freely accessible. doi:10.1137/17M1134822. 
  11. ^ "NUFFT page". cims.nyu.edu. 
  12. ^ "NFFT". www.nfft.org. 
  13. ^ "MikaelSlevinsky/FastTransforms.jl". GitHub. 
  14. ^ "chebfun/chebfun". GitHub. 

External links[edit]