本文是 ICLR 2023 入选论文 On The Relative Error of Random Fourier Features for Preserving Kernel Distance 的解读。本论文由北京大学前沿计算研究中心程宽老师与姜少峰老师指导学生完成，提出了经典的 RFF 映射对于一大类核函数都能够有 JL-lemma 的效果，也给出了拉普拉斯核函数作为反例说明 RFF 映射的局限性，最后给出了一个高效处理拉普拉斯核函数的方法。

　　论文链接：https://arxiv.org/abs/2210.00244

　　核方法（kernel method）是机器学习中具有广泛应用的一种处理输入数据间非线性关系的方法，然而，经典核方法需要定义数据点两两之间的内积，导致了O(n^{2})的时间复杂度，在输入能够轻易达到百万量级的大数据时代，这一复杂度显然不能被接受，因此，如何将核方法在近似线性时间内完成始终是人们关注的方向。

　　2007年，Rachmi 和 Racht 观察到在适当的放缩下，对核函数做傅立叶变换所得到的函数可以被视为一个密度函数，由此，他们提出了经典的 Random Fourier Feature 方法（RFF），并证明了如果我们希望加性误差ε足够小，只需要将输入的维数放poly(1/ε) 倍即可。后续10年间，许多工作近一步分析了 RFF 方法逼近在实践和理论上的有效性，其中以2017年 Chen 和 Phillips 的工作为代表，他们指出对于经典的高斯核函数，RFF 事实上可以如 JL-lemma 一样保住输入数据点在核函数下的两两距离。

　　利用对于 RFF 映射中随机变量的高阶矩的进一步分析，本篇工作成功证明了在核函数为解析函数时，RFF 能够将数据点映射到polylogn维同时保持输入间的两两距离，这一分析的结论完全类比于 JL-lemma，同时在我们的认识中，这也是第一篇指出 RFF 对于这一类核函数的目标纬度可以不依赖输入维度的工作。

　　因此，我们可以将 RFF 映射代入 Makarychev 等人在2019年提出的处理 k-clustering 问题的框架，指出 RFF 在一个不依赖于输入个数和维度的相当低维度就能保证 kernel k-clustering 的值。

　　另一方面，我们也证明了对于另一个经典的核函数 Laplacian kernel，RFF 的目标纬度必须依赖于输入间的最近距离，这一出人意料的反例也说明了 RFF 方法的局限性。

　　最后，本篇工作给出了一种在 RFF 基础上进行适当改变以处理 Laplacian kernel 的算法，它在随机数据点上的表现显著优于 SVD 和直接使用 JL-lemma 的效果。