Reconstruction of non-Cartesian data involves estimating values at regular grid-points from data points acquired at arbitrary points. A typical method of reconstruction involves non-uniform Fourier transform, which performs fast Fourier transform (FFT) and convolution-resampling¹. The computational cost increases dramatically from 2D to 3D and much work has been done to trade this off against accuracy^2-4.

The computational cost depends primarily on two parameters: the oversampling factor for the regular grid (u) and the window width used in the convolution (J). Reducing u reduces the cost of the FFT while reducing J reduces the cost of the convolution. Implementations typically use a convolution kernel that is separable along each dimension, which results in a total number of J^d convolution coefficients per data point, where d is the dimensionality. For 3D problem sizes typically encountered (see Table), the computational cost of the convolution-resampling can greatly exceed that of the FFT step.

The present study investigates the use of a radial convolution kernel, rather than separable, as a way of reducing the number of convolution coefficients and hence the overall computational cost of the non-uniform Fourier transform.

The methodology used here is similar to that described in Ref 2. The zeroth-order Kaiser-Bessel kernel was fine-tuned over its free parameter (alpha) for different J, u and convolution kernel type (f), which was calculated in two ways.

Separable: convolution coefficients were generated for the nearest J grid-points along each dimension as f(dx) × f(dy) × f(dz) at distances -J/2 < dx, dy, dz < J/2 from the sampled data point.

Radial: convolution coefficients were generated for grid-points within a radial distance dr = sqrt(dx² + dy² + dz²) < J/2 of the sampled data point according to f(dr).

Clearly the radial kernel only includes grid-points inside a sphere of radius J/2 whereas the separable kernel includes points with a cube of side J. The corresponding reduction in number of coefficients is around π/6 or ~50%. Convolutions were effected as a sparse matrix multiply and deapodisation was performed using the FFT of the kernel. All computations were performed in Matlab 2014b on a Xeon workstation.

To assess accuracy, k-space data were generated at uniform random sampling points for the 3D Shepp Logan phantom⁵ using a discrete Fourier transform (exact, slow) and the non-uniform Fourier transform (approximate, fast). The maximum percentage error between the two was the metric used to evaluate the accuracy of the latter.

The Figure shows the maximum percentage error as a function of the kernel parameter for radial and separable kernels. The vertical dashed line indicates the recommended value from Ref 2 (alpha = 2.34 × J). It can be seen that this parameter is suitable for both radial and separable kernels (note: the precise location of the minimum is dependent on the initialization of the random samples). It is also apparent that the radial kernel exhibits errors up to 2 times larger than the separable kernel for a given value of J.

To give a concrete comparison: with J = 5 (separable) the number of non-zeros in the convolution matrix is 125 000 000 and the minimum error is 0.0028%. With J = 5 (radial) the number of non-zeros is 65 447 671 and the minimum error is 0.0048%. With J = 4 (separable) the number of non-zeros is 64 000 000 and the minimum error is 0.034%. Hence, for the same number of coefficients, the error with the radial kernel is around 7 times lower.

Although the radial kernel has larger errors than the separable kernel, it benefits from a factor of 2 reduction in the computational cost of the convolution due to having half the number of coefficients. For values of J of practical interest (say J = 3–6) the radial kernel has roughly the same number of coefficients as a separable kernel of width J-1, while the error is several times lower. This indicates that the radial convolution kernel offers a favorable trade-off of accuracy and computation time for non-uniform Fourier transforms.