# nufft

Nonuniform fast Fourier transform

Since R2020a

## Syntax

``Y = nufft(X,t)``
``Y = nufft(X,t,f)``
``Y = nufft(X,t,f,dim)``
``Y = nufft(X)``

## Description

example

````Y = nufft(X,t)` returns the nonuniform discrete Fourier transform (NUDFT) of `X` using the sample points `t`. If `X` is a vector, then `nufft` returns the transform of the vector.If `X` is a matrix, then `nufft` treats the columns of `X` as vectors and returns the transform of each column.If `X` is a multidimensional array, then `nufft` treats the values along the first array dimension whose size does not equal 1 as vectors and returns the transform of each vector. ```

example

````Y = nufft(X,t,f)` computes the NUDFT at the query points `f` using the sample points `t`. To specify `f` without specifying sample points, use `nufft(X,[],f)`.```
````Y = nufft(X,t,f,dim)` returns the NUDFT along dimension `dim`. For example, `nufft(X,t,f,2)` computes the transform of each row of a matrix `X`.```
````Y = nufft(X)` returns the discrete Fourier transform of `X`, and is equivalent to `fft(X)`.```

## Examples

collapse all

Create a signal `X` sampled at unevenly spaced points `t`. Plot the signal.

```t = [0:300 500.5:700.5]; S = 2*sin(2*pi*0.02*t) + sin(2*pi*0.1*t); X = S + rand(size(t)); plot(t,S)``` Find the nonuniform fast Fourier transform of the signal. When you use `nufft` without providing the frequencies as the third argument, `nufft` uses the default frequency scaling where the frequencies take the form `f(i) = (i-1)/n` for a signal length of `n`. Plot the absolute value of the transform as a function of the default frequencies.

```Y = nufft(X,t); n = length(t); f = (0:n-1)/n; plot(f,abs(Y))``` Create a time vector of nonuniform sampled points. Define a time duration of about 35 seconds with a sampling period `T` = 50 ms (or a sampling frequency `Fs` = 20 Hz) for the equivalent uniformly sampled data.

```T = 50e-3; % Sampling period of 50 ms for equivalent uniform samples Fs = 1/T; % Sampling frequency of 20 Hz for equivalent uniform samples t = [0:T:300*T 500.5*T:T/2:700.5*T];```

Create a signal `X` sampled at unevenly spaced points `t` with peak frequencies at 0.4 Hz and 2 Hz.

```S = 2*sin(2*pi*0.4*t) + sin(2*pi*2*t); % Signal with peak frequencies at 0.4 Hz and 2 Hz X = S + rand(size(t)); plot(t,S) xlabel("t (seconds)") ylabel("X(t)")``` Find the nonuniform fast Fourier transform of the signal. Use `nufft` without providing the frequencies as the third argument. In this case, `nufft` uses the default frequencies with the form `f(i) = (i-1)/n` for a signal length of `n`. The nonuniform discrete Fourier transform treats the nonuniform sample points `t` and frequencies `f` as if they have a sampling period of 1 s and a sampling frequency of 1 Hz for the equivalent uniformly sampled data. For this reason, include the scaling factor `T` to the time vector when using `nufft` to obtain the transform with correctly scaled units. Plot the absolute value of the transform as a function of the default frequencies that are scaled by `Fs`.

```Y = nufft(X,t/T); n = length(t); f = (0:n-1)/n*Fs; plot(f,abs(Y)) xlabel("f (Hz)") ylabel("abs(Y)(f)")``` When using `nufft`, you can also specify a nonuniform frequency vector or query points `f` as the third argument and the nonuniform time vector `t` as the second argument. Here, you do not need to rescale `t` and `f` when using `nufft`. Plot the absolute value of the transform as a function of the nonuniform frequencies.

```f = [0:0.5:n/4 n/3+1:n-120]/n*Fs; Y = nufft(X,t,f); plot(f,abs(Y)) xlabel("f (Hz)") ylabel("abs(Y)(f)")``` Define and label the frequencies of a range of musical tones.

```C3 = 440 / (2^(21/12)); nOctaves = 3; musicalTones = C3 * 2.^((0:(12*nOctaves-1))/12); toneNames = ["C";"C#";"D";"D#";"E";"F";"F#";"G";"G#";"A";"A#";"B"] + string(3:(3+nOctaves-1)); toneNames = categorical(toneNames, toneNames);```

Define the audio signal sampling frequency in Hz, the sample points `n`, and a signal containing a major chord `X`.

```fs = 16e3; n = 1:16000; X = 4*cos(2*pi*(440/fs)*n) + 2*cos(2*pi*(554.37/fs)*n) + 3*cos(2*pi*(659.2/fs)*n);```

Compute and plot the frequency components of the major chord.

```Y = nufft(X,[],musicalTones/fs); bar(toneNames(:),abs(Y))``` ## Input Arguments

collapse all

Input array, specified as a vector, matrix, or multidimensional array.

Data Types: `double` | `single` | `int8` | `int16` | `int32` | `uint8` | `uint16` | `uint32` | `logical`
Complex Number Support: Yes

Sample points or time vector, specified as a vector of length n, where n is the length of the operating dimension of the input array `X`. By default, the sample points vector is `0:(n-1)`.

When you use the default sample points `0:(n-1)`, `nufft` treats `t` and `f` as if they have a sampling period of 1 s and a sampling frequency of 1 Hz for the equivalent uniformly sampled data. For this reason, you might need to rescale your time and frequency vectors to obtain the Fourier transform with correctly scaled units. For example, see Nonuniform Sample Points With Time and Frequency Scaling.

Data Types: `double` | `single`

Query points or frequency vector, specified as a vector. By default, the query points vector is `(0:(n-1))/n`, where n is the length of the operating dimension of the input array `X`. To specify `f` without specifying sample points, use `nufft(X,[],f)`.

When you use the default query points `(0:(n-1))/n`, `nufft` treats `t` and `f` as if they have a sampling period of 1 s and a sampling frequency of 1 Hz for the equivalent uniformly sampled data. For this reason, you might need to rescale your time and frequency vectors to obtain the Fourier transform with correctly scaled units. For example, see Nonuniform Sample Points With Time and Frequency Scaling.

Data Types: `double` | `single`

Dimension to operate along, specified as a positive integer scalar. The default is the first array dimension whose size does not equal 1.

Data Types: `double` | `single` | `int8` | `int16` | `int32` | `int64` | `uint8` | `uint16` | `uint32` | `uint64` | `logical`

collapse all

### Nonuniform Discrete Fourier Transform of Vector

For a vector X of length n, sample points t, and frequencies f, the nonuniform discrete Fourier transform of X is defined as

`$Y\left(k\right)=\sum _{j=1}^{n}X\left(j\right){e}^{-2\pi i\text{\hspace{0.17em}}t\left(j\right)\text{\hspace{0.17em}}f\left(k\right)}$`

where k = 1, 2, …, m. When t = 0, 1, …, n-1 and f = (0, 1, …, n-1)/n (defaults for `nufft`), the formula is equivalent to the uniform discrete Fourier transform used by the `fft` function.

 Potter, Samuel F., Nail A. Gumerov, and Ramani Duraiswami. “Fast Interpolation of Bandlimited Functions.” In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 4516–20. New Orleans, LA: IEEE, 2017. https://doi.org/10.1109/ICASSP.2017.7953011.

 Dutt, A., and V. Rokhlin. “Fast Fourier Transforms for Nonequispaced Data.” SIAM Journal on Scientific Computing 14, no. 6 (November 1993): 1368–93. https://doi.org/10.1137/0914081.