Fast and Accurate Partial Fourier Transform for Time Series Data

给定一个时间序列向量，我们如何有效地检测异常?一种广泛使用的方法是利用快速傅里叶变换(FFT)计算傅里叶系数，取前几个系数，丢弃剩下的小系数，重构原始时间序列，找到误差较大的点。尽管广泛使用，该方法需要计算所有的傅里叶系数，如果输入长度很大或需要执行许多FFT操作，这可能是很麻烦的。在本文中，我们提出了部分傅里叶变换(PFT)，一个高效和精确的算法，只计算部分傅里叶系数。PFT利用多项式近似部分旋转因子(三角常数)，从而减少了混合了许多旋转因子的计算复杂度。我们推导了PFT的渐近时间复杂度与输入输出大小和公差有关。我们还表明，PFT提供了一种设置任意逼近误差界的选项，这是有用的，特别是当快速计算是最重要的。实验结果表明，PFT优于目前最先进的算法，在足够小的输出尺寸下，具有一个数量级的加速，而不牺牲精度。此外，我们通过解释股价数据中的异常，证明了PFT在真实世界异常检测中的准确性和有效性

背景

实验结果表明，PFT优于最先进的FFT库、FFTW[7]和Intel Math Kernel库以及Pruned FFTW，在不牺牲精度的前提下提高了一个数量级的速度。

问题：

面临的挑战：

1）如何为指定的输出提取必要的信息

2）如何降低近似成本?

3）我们如何进一步减少数值计算?

PROPOSED METHOD

该算法的关键是利用多项式函数逼近部分平滑(振荡较小)的twiddle factors ，减少了由于混合了多个twiddle factors 而导致的DFT计算复杂度。控制多项式的阶，产生微调的输入范围，同时估计近似的边界。

我们的第一个目标是找到具有小振荡的twiddle factors的集合。这可以通过像Cooley-Tukey算法那样稍微调整DFT的求和和分割求和来实现。接下来，利用适当的基指数函数，我们给出了twiddle factors的显式逼近

1）Smooth Twiddle Factors

从这个意义上说，可以用多项式函数来近似(2)中的第一个twiddle factors集合，从而降低了由于两个旋调因子集合混合而产生的计算复杂度

Arbitrarily Centered Target Ranges

考虑更加一般的范围