Fourier transform in 3 dimensions on a non uniform grid in matlab

Question

I need to calculated a 3D Fourier transform of a structures I have their [x,y,z] coordinates. I thought of interpolating to a uniform grid of the smallest spacing between the points and use fft, but that turned to be impractical in memory, so fft can't be used. A sample from my [x,y,z] data is:

xyz=[ 23.1860   44.9710    5.9280
      25.5370   44.0090    4.9960
      24.5030   44.5890    6.2280
      20.0150   46.4080    7.9110
      24.9910   44.6760    7.5330
       4.8660   44.7120    8.6830
      36.7170   33.7440    6.5570
      11.1510   40.0590    5.8120
      29.2550   34.8750   10.0850
       5.4230   48.8200   12.7380
      38.2020   35.7590    1.3260 ];

Would appreciate your advise

Answer 1

I've not used this myself, but consider using the NFFT posted on Chemnitz University of Technology Department of Mathematics site. It reduces the O(N^2) requirement to just O(NlogN) as in the FFT case. Also, it now includes Matlab classes to interface with the mex files.

You can download some examples on the site that show to to interact with MATLAB and the faq has instructions on how to use in Windows+MATLAB (if you are).

NFFT requires the initialization of a plan and precomputes several things to increase performance. It looks like it will take some effort to get familiar with but may be very helpful to you.

It is licensed under the GPL.

Answer 2

Unfortunately, the algorithms that make the FFT so efficient simply don't apply to the non-uniform case. Whereas the FFT is O(N log N), the non-uniform case is typically O(N^2) (as far as I'm aware). All of the NUFFT techniques that I'm aware of essentially rely on interpolation, so you're unlikely to find a fundamentally different way of doing it.

What is your grid geometry (I can't eyeball the arrays you've supplied for spacing patterns)? If one or two of the dimensions are uniform, you could apply the 1 or 2D FFT on those independently, and then interpolate solely for the third dimension. Many problems in spherical coordinates effectively do this: they use the FFT along lines of constant latitude, because the latitudes are usually spaced non-uniformly to use Gaussian quadrature, while the longitudes are uniform.

Greengard, L., & Lee, J. Y. (2004). Accelerating the nonuniform fast Fourier transform. SIAM review, 46(3), 443-454.