非均匀 FFT 有多种技术，最有效的技术都适合您的情况：准均匀样本。基本思想是通过针对高斯的局部卷积将不均匀采样的源涂抹到稍微精细（“过采样”）的均匀网格上。然后可以在过采样的均匀网格上运行标准 FFT，然后可以撤消针对高斯的卷积。好的实现是维中的标准 FFT 贵几倍接近 4 或 5。$C^d$$d$$C$

我推荐阅读Greengard 和 Lee的《加速非均匀快速傅里叶变换》 。

当源和/或评估点稀疏时，还存在快速，即或更快的技术，并且还存在对更一般的积分算子的推广，例如傅立叶积分算子。如果您对这些技术感兴趣，我推荐通过蝶形算法进行稀疏傅立叶变换和傅立叶积分算子计算的快速蝶形算法。与标准 FFT 相比，这些技术所付出的代价要高得多。免责声明：我的顾问撰写/共同撰写了这两篇论文，我花了相当多的时间来并行化这些技术。$O(N^d \log N)$

重要的一点是，所有上述技术都是近似值，可以以更长的运行时间为代价获得任意精确，而标准 FFT 算法是精确的。

在信号处理中，通过在采样前通过低通滤波器发送信号来避免混叠。Jack Poulson 已经解释了一种使用截断高斯函数作为低通滤波器的非均匀 FFT 技术。截断高斯的一个不方便的特点是，即使您已经决定了 FFT 的网格间距（=信号处理中的采样率），您仍然有两个自由参数：高斯的宽度和截断半径。

因此，我更喜欢宽度为两个网格单元的“帽子”功能作为低通滤波器。这具有第零次傅立叶阶是精确的效果，并且较低的傅立叶阶将二次收敛。“hat”函数的傅里叶变换很容易计算（它是 sinc 函数的平方），这简化了在 FFT 之后撤消卷积。请注意，“帽子”函数是（居中的）晶胞的特征函数与其自身的卷积。通过将晶胞与其自身进行多次卷积，并使用结果函数而不是“帽子”函数，可以实现任何所需的收敛速度。

如果您对软件感兴趣，我可以推荐 NFFT 库（C 语言，带有 MATLAB 接口），可以在此处找到。请注意，同样的开发人员还有一个用于并行 FFT 计算的 PFFT 库，甚至还有一个用于并行非等空间 FFT 的 PNFFT库。

除了接受的答案。这是 Greengard 和 Lee 方法的开源实现的链接：https ://finufft.readthedocs.io/en/latest/ 它包含 C、fortran、MATLAB、octave 和 python 的包装器。我相信 FINUFFT 是用 C++ 编写的。

它在 NYU Courant 研究所、SFU、Flatiron 研究所（显然）、德克萨斯大学奥斯汀分校和佛罗里达州立大学进行维护和使用。至少这些是我所知道的。

我自己使用的是旧版本，因为我很懒。见：https ://cims.nyu.edu/cmcl/nufft/nufft.html