---
tag: NY851TZ24X
kind: concept
name: Non-uniform discrete Fourier transform
msc: [65T50, 65T40]
sources:
  - url: https://en.wikipedia.org/wiki/Non-uniform_discrete_Fourier_transform
same_as:
  wikidata: Q7049066
  wikipedia: Non-uniform discrete Fourier transform
---

## Summary

The non-uniform discrete Fourier transform (NUDFT) is a variant of the [[discrete Fourier transform|TST0GH66A5]].
In it the sample points, the frequencies, or both are not equally spaced.
It evaluates finite sums $\sum_n x_n e^{-2\pi i p_n f_k}$ with arbitrary real $p_n$ and $f_k$.
Such data arise in medical imaging, astronomy and spectral methods, where measurements are not taken on a regular grid.
Fast approximate algorithms for it are called non-uniform FFTs.

## Explanations

### L1 human

The ordinary discrete Fourier transform assumes the signal was sampled at evenly spaced times.
Real measurements often come at irregular times or positions, for instance along spiral paths in an MRI scanner.
The non-uniform transform uses the same kind of sum, but with the actual sample positions in the exponent.
For example, samples at times $0$, $0.3$ and $0.7$ give the coefficient $X_k = x_0 + x_1 e^{-0.6\pi i k} + x_2 e^{-1.4\pi i k}$ at frequency $k$.
The loss of regular spacing means the clever factorizations of the FFT no longer apply directly.