高维情况下通过切片和傅立叶变换进行快速核求和
内容提要
本文综述随机傅里叶特征与签名核等核近似方法。针对签名核的计算瓶颈，提出基于随机傅里叶特征的加速方法，具有无偏估计与均匀逼近保证，计算复杂度随序列长度和数量线性增长；结合张量投影可获得更可扩展的时间序列特征，能处理多达百万级序列的数据集。Fastfood等方法可降低计算与存储成本，文中还讨论了近似误差与收敛性。
延伸解读
签名核加速的核心思路
文章针对签名核在序列数据上的计算瓶颈，提出基于随机傅里叶特征的加速方法。该方法在非欧几里得序列领域上构建无偏估计器，并给出均匀逼近保证，同时使计算复杂度随序列长度和数量保持线性。这意味着原本难以扩展的签名核，在理论保证下可应用于更大规模的时间序列任务。
可扩展性与精度权衡
结合张量投影的最新进展，文章得到两种更可扩展的时间序列特征，具有有利的集中性质，并在时间和内存上控制计算复杂度。实证结果显示，在中等规模数据集上，计算成本的降低几乎没有影响准确性，并且使处理高达一百万种时间序列的大型数据集成为可能。这提示读者关注近似方法在规模扩展时的实际精度表现。
相关近似方法的定位
文章还综述了Fastfood等核近似方法：Fastfood利用Hadamard矩阵和对角高斯矩阵替代高斯随机矩阵，将计算复杂度降至O(n log d)并仅需O(n)存储，同时保持无偏和低方差。这些方法为核方法的实际应用提供了可能性，也帮助读者理解随机傅里叶特征加速在更广泛核近似技术中的位置。
Q&A
签名核在计算上有什么瓶颈？
签名核虽然具有概率分析中的理论保证，但计算复杂度高，成为处理大规模序列数据时的严重瓶颈。
如何加速签名核的计算？
提出了一种基于随机傅里叶特征的方法，在序列的非欧几里得领域上进行签名核加速，并证明了无偏估计器的均匀逼近保证，同时保持计算复杂度随序列长度和数量线性增长。
随机傅里叶特征加速签名核后，计算复杂度如何？
计算复杂度在序列长度和数量上保持线性，结合张量投影后得到更可扩展的时间序列特征，在时间和内存上具有有利的计算复杂度。
Fastfood方法如何降低核方法的计算和存储成本？
Fastfood利用Hadamard矩阵和对角高斯矩阵代替高斯随机矩阵，将计算非线性基函数的时间复杂度降至O(n log d)，仅需O(n)存储空间，同时保证无偏和低方差。
这种加速方法能处理多大规模的数据集？
实证结果表明，计算成本的降低在中等规模数据集上几乎没有影响准确性，并且使得能够处理高达一百万种时间序列的大型数据集。
随机傅里叶特征逼近核函数时，误差和收敛性如何？
文章讨论了近似误差与收敛性，证明了所提出无偏估计器的均匀逼近保证，并指出更常用的RFF变体在高斯核中具有严格更高的方差且界限更糟糕。
