nufftn

N-D nonuniform fast Fourier transform

Syntax

Y = nufftn(X,t)

Y = nufftn(X,t,f)

Y = nufftn(X)

Description

Y = nufftn(X,t) returns the nonuniform discrete Fourier transform (NUDFT) along each dimension of an N-D array X using the sample points t.

Y = nufftn(X,t,f) computes the NUDFT using the sample points t and query points f. To specify f without specifying sample points, use nufftn(X,[],f).

Y = nufftn(X) returns the N-D discrete Fourier transform of X.

Examples

Nonuniform Sample Points

Create a 3-D signal X sampled at unevenly spaced points t in each dimension. Compute the nonuniform fast Fourier transform Y.

t = [1:10 11:2:29]';
x = t;
y = t';
z = reshape(t,[1 1 20]);
X = cos(2*pi*0.01*x) + sin(2*pi*0.02*y) + cos(2*pi*0.03*z);
Y = nufftn(X,{t,t,t});

Input Arguments

X — Input array

vector | matrix | multidimensional array

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

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

t — Sample points

vector | matrix | cell array of vectors

Sample points, specified as a vector, matrix, or cell array of vectors for each dimension of the input array X.

When specified as a vector or matrix, the number of rows of t must equal the number of elements in X. When no query points are specified, the transform is computed at N evenly spaced query points in each dimension, where N = ceil(numel(X).^(1/D)) and D is the number of columns in t. The output Y is a D-dimensional array of length N in each dimension.

When t is specified as a cell array of D vectors, the length of each vector must equal the length of the corresponding dimension of X.

Data Types: double | single

f — Query points

vector | matrix | cell array of vectors

Query points, specified as a vector, matrix, or cell array of vectors for each dimension of the input array X. When specified as a matrix, f must be an M-by-k array, where k is greater than or equal to the number of dimensions D defined by the sample points.

When f is specified as a cell array of D vectors, the length of each dimension of the output Y is equal to the length of the corresponding vector in the cell array.

To specify f without specifying sample points, use nufftn(X,[],f).

Data Types: double | single

Extended Capabilities

Thread-Based Environment

Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

Version History

Introduced in R2020a

R2023b: Further improved performance with nonuniform sample points or query points

The nufftn function shows improved performance when operating on either nonuniformly spaced sample points or nonuniformly spaced query points.

For example, this code constructs a 262,144-by-3 matrix of nonuniform sample points t and calculates the nonuniform discrete Fourier transform along each dimension of a 64-by-64-by-64 array. The code is about 3.3x faster than in the previous release.

function timingSamplePoints
rng default
t = rand(64^3,3);
X = rand(64,64,64);
tic
  Y = nufftn(X,t);
toc
end

The approximate execution times are:

R2023a: 0.40 s

R2023b: 0.12 s

The code was timed on a Windows^® 10, Intel^® Xeon^® CPU E5-1650 v4 @ 3.60 GHz test system by calling the timingSamplePoints function.

As another example, this code constructs a 262,144-by-3 matrix of nonuniform query points f and calculates the nonuniform discrete Fourier transform along each dimension of a 64-by-64-by-64 array. The code is about 1.6x faster than in the previous release.

function timingQueryPoints
rng default
f = rand(64^3,3);
X = rand(64,64,64);
tic
  Y = nufftn(X,[],f);
toc
end

The approximate execution times are:

R2023a: 0.40 s

R2023b: 0.25 s

The code was timed on a Windows 10, Intel Xeon CPU E5-1650 v4 @ 3.60 GHz test system by calling the timingQueryPoints function.

R2022a: Improved performance with nonuniform sample points or query points

The nufftn function shows improved performance when operating on either nonuniformly spaced sample points or nonuniformly spaced query points.

For example, this code constructs a 32768-by-3 matrix of nonuniform sample points t and calculates the nonuniform discrete Fourier transform along each dimension of a 32-by-32-by-32 array. It runs about 14.5x faster than in the previous release:

function timingSamplePoints
rng default
t = rand(32^3,3);
X = rand(32,32,32);
tic;
  Y = nufftn(X,t);
toc
end

The approximate execution times are:

R2021b: 2.76 s

R2022a: 0.19 s

The code was timed on a Windows 10, Intel Xeon CPU E5-1650 v4 @ 3.60 GHz test system by calling the timingSamplePoints function.

As another example, this code constructs a 65536-by-3 matrix of nonuniform query points f and calculates the nonuniform discrete Fourier transform along each dimension of a 64-by-32-by-32 array. It runs about 42.6x faster than in the previous release:

function timingQueryPoints
rng default
f = rand(64*32*32,3);
X = rand(64,32,32);
tic;
  Y = nufftn(X,[],f);
toc
end

The approximate execution times are:

R2021b: 4.26 s

R2022a: 0.10 s

The code was timed on a Windows 10, Intel Xeon CPU E5-1650 v4 @ 3.60 GHz test system by calling the timingQueryPoints function.