非均匀FFT技术咨询：频域非均匀采样算法及计算效率疑问

1. 核心算法列举 #

• 非均匀快速傅里叶变换（NUFFT）：这是适配非均匀频域采样的主流框架，可完全自定义频域采样点分布——在低频区域设置密集采样点，高频区域稀疏采样，直接完成时域到目标非均匀频域的变换计算。
• Chirp Z变换（CZT）：传统CZT针对弧线均匀采样，但可通过调整参数将采样点集中在低频段，实现“低频密、高频疏”的非均匀采样效果。它通过线性调频信号把任意采样点的DFT转化为卷积运算，灵活度很高。
• 加权FFT插值法：基于标准FFT的结果，通过sinc插值、最小二乘插值等方法，重采样得到低频密集、高频稀疏的频域点。这种方法实现简单，属于FFT的后处理方案，不算原生非均匀FFT算法，但能快速满足需求。
• 稀疏FFT：如果目标频域点整体相对于全频域是稀疏的（你的场景符合这一点），可利用信号稀疏性只计算需要的频域点，跳过全频域FFT计算，效率优势明显。

2. 计算效率与预计算支持 #

• NUFFT：复杂度为O(N log N + M log M)（N为时域点数，M为非均匀频域点数），效率接近标准FFT。支持预计算插值核函数和旋转因子，固定采样分布时，预计算一次后重复调用的速度会大幅提升。
• CZT：复杂度为O((N + L) log(N + L))（L为采样点数），和FFT处于同一量级。完全支持预计算chirp因子，采样分布固定时，预计算后后续计算效率很高。
• 加权FFT插值法：依赖标准FFT的O(N log N)计算，后续插值复杂度为O(N*K)（K为目标频域点数）。若K远小于N，效率尚可，但整体不如NUFFT和CZT。可预计算插值核（如sinc权重）来优化插值步骤。
• 稀疏FFT：复杂度为O(K log N)（K为需计算的频域点数），当K远小于N时，效率远超标准FFT。支持预计算采样矩阵和相关因子，固定采样分布时可复用预计算结果。

整体来看，NUFFT和CZT是最贴合你需求的算法，它们的计算效率与FFT相当，且都支持预计算因子来优化重复计算的性能。

内容的提问来源于stack exchange，提问作者wimalopaan