在matlab中非均匀网格上的3维傅里叶变换

Question

我需要计算我有[x,y,z]坐标的结构的3D傅里叶变换.我想到内插到点之间最小间距的均匀网格并使用fft,但这在内存中变得不切实际,因此fft无法使用.来自我的[x,y,z]数据的样本是:

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 ];

非常感谢您的建议

Answer 1

不幸的是,使FFT如此有效的算法不适用于非均匀情况.尽管FFT是O(N log N),但非均匀情况通常是O(N ^ 2)(据我所知).我所知道的所有NUFFT技术基本上都依赖于插值,所以你不太可能找到一种根本不同的方法.

你的网格几何是什么(我无法看到你为间距模式提供的数组)？如果一个或两个维度是均匀的,您可以单独对这些维度应用1或2D FFT,然后仅针对第三维进行插值.球坐标中的许多问题有效地做到了这一点:它们沿着恒定纬度的线使用FFT,因为纬度通常非均匀地间隔以使用高斯正交,而经度是均匀的.

Greengard,L.,&Lee,JY(2004).加速非均匀快速傅里叶变换.SIAM评论,46(3),443-454.

Answer 2

我自己没有用过这个,但考虑使用在开姆尼茨理工大学数学系网站上发布的NFFT.与FFT情况一样,它将O(N ^ 2)要求降低到O(NlogN).此外,它现在包括与mex文件接口的Matlab类.

您可以在网站上下载一些示例,以便与MATLAB进行交互,并且faq有关于如何在Windows + MATLAB中使用的说明(如果您有).

NFFT需要初始化计划并预先计算几项以提高性能.看起来需要花些精力才能熟悉,但可能对您非常有帮助.

它是根据GPL许可的.