有人知道多相重采样算法的近似计算复杂度吗？
我试图找到一个很好的论据来更喜欢 Scipy 的多相重采样而不是 FFT 重采样方法。在它的文档中resample_poly()说：
当样本数量很大并且是素数时，或者当样本数量很大并且上下共享一个很大的最大公分母时，这种多相方法可能会比 scipy.signal.resample 中的傅里叶方法更快。
我的数据符合这些标准。我从 10kHz 到 300Hz 重新采样 15 个通道 * 30k-50k 个样本，实践表明它比 FFT 方法快得多。
然而，我想在这些标准上有一个可参考的来源。
我发现了几篇关于FFT 算法计算复杂性的O(n*log(n))论文n=n_channel*n_samples。
10 kHz -> 300 Hz 是具有相对良性因素的合理重采样：
这意味着您将插值 3 并抽取 100。这正是您使用以下方法实现的目标resample_poly：
请记住，要在没有混叠的情况下进行 100 次抽取，您需要将信号过滤到，这可能需要相当多的滤波器抽头。遗憾的是，您丢弃了在以下抽取步骤中过滤的 100 个样本中的 99 个。
使用多相技术，您可以巧妙地重新排列滤波器抽头，这样您甚至不需要进行这 99 次计算 - 并通过抽取因子（此处为 100）减少抽取滤波器的工作量。
这基本上是通过将您的长滤波器“去交错”到 100 个分离集来实现的，形成原始滤波器的 100 个多相分量。如果您将输入样本放入所有这些部分过滤器中，并正确总结这些组件过滤器的输出样本，您将得到完全相同的过滤器。这实际上只是一种以不同方式“排列”过滤器的方式。但是，如果您知道要丢弃哪些输出样本，则可以省略将每个输入样本推入 100 个多相滤波器组件中的 99 个 - 这样您就可以将输入样本“循环”到每个多相滤波器组件。这样可以节省 99% 的计算量！
但是上采样 3 呢？好吧，多相有理重采样器的另一个美丽方面是，您可以显示“首先插值 3，通过滤波器消除图像，然后应用滤波器以避免混叠，然后丢弃的顺序100 个样本中的 99 个”可以重新排序以抽取过滤器插值。这太棒了，因为：
除了前面提到的必要操作数量的显着减少之外，请记住，即使对于较短的多相分量滤波器，您也可以应用 FFT 滤波器，如果它们足够长以便这样做的话；根据我的经验，对于像你这样温和的利率，通常情况并非如此。比较Tom Rondeau关于 FFT FIR 滤波器与多相 FIR 比较的帖子。
通常，FFT 滤波器的优点在于您可以减少将一段信号与滤波器抽头向量进行卷积所需的操作次数。另一方面，在计算 FFT 时，您可以购买具有完全非线性内存访问的算法优雅。现在，如果您的滤波器很长，那么您的 FFT 也必须很长，并且您的 CPU 无法将所有信号向量和抽头向量都保存在本地缓存中。经验法则说，在现代 x86 计算机上，一次从 RAM 中提取的值相当于 200 到 500 次浮点运算[需要引用] 。
但是，即使在非 FFT FIR 滤波器中您需要处理的操作量要大得多，您的内存访问（如果您的 FIR 实现不是完全脑死）本质上是线性的——而且您的 CPU 及其内存控制器非常擅长获取线性内存，甚至预取它。因此，这在很长一段时间内都对您有利，直到 FFT 滤波器的复杂性优势真正击败了幼稚 FIR 的废话。
这种线性的另一个方面是使用 SIMD 指令更容易矢量化——如果你想对 scipy 感到失望，安装 GNU Radio（如果你在当前的 Linux 发行版或 OS X 上很容易，在 Windows 上仍然可行），运行volk_profile（需要一段时间才能找到适合您机器的最佳 SIMD 实现），然后使用以下流程图测量重采样吞吐量：
它每秒为我处理 500 万个样本。Scipy 并没有接近这一点。