# nufft

Nonuniform fast Fourier transform

## 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. Compute the nonuniform fast Fourier transform Y.

t = [0:300 500.5:700.5];
S = 2*sin(0.1*pi*t) + sin(0.02*pi*t);
X = S + rand(size(t));
Y = nufft(X,t);

Plot the absolute value of the transform as a function of the default frequencies.

n = length(t);
f = (0:n-1)/n;
plot(f,abs(Y))

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, 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).

Data Types: double | single

Query points, 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).

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.

## References

[1] 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.

[2] 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.