看看 OpenAI 的数学，据称可以计算更快的傅里叶变换

大家好，argmin 读者！今天的文章着眼于 OpenAI 数学存储库的一部分，该存储库声称可以计算更快的傅里叶变换。它比平常更具技术性，但我尝试为需要信号处理或计算复杂性进修课程的人们添加一些教程材料。快速傅里叶变换是数字信号处理领域最重要的创新之一，也是我最喜欢的算法之一。 FFT 是一种提取信号频率内容的快速方法，让您可以快速分析、过滤和操纵不同频谱频段的频率。傅立叶变换通过简单的点积计算每个频带中的能量。让 x 表示您的输入，长度为 n 的样本数组，f 表示频率。然后，f 处 x 中的频率内容量可以通过以下公式计算： 对于数字信号，一点数学表明您只需计算 n 个这些点积（频率 2𝜋/n 的每个倍数一个）即可了解所有频率内容。简单地说，这需要每个频率进行 n 次乘法和加法。因此，计算整个傅里叶变换似乎需要 n 2 算术运算。快速傅立叶变换是 James Cooley 和 John Tukey 在 1965 年设计的一种巧妙的递归过程。其主要思想是，可以通过对输入向量进行混洗、在混洗后的分量上计算两个长度为 n/2 的傅里叶变换，然后使用原子算术运算重新组合输出来计算长度为 n 的傅里叶变换。洗牌和重组需要线性数量的算术运算。迭代地重复此过程，即 log 2 (n) 次，计算完整的离散傅里叶变换。通过簿记，FFT 可以用少于 5 n log2 n 次算术运算来计算长度为 n 的傅里叶变换。具体来说，当 n 为 1,000 时，n^2 为 1,000,000，5 * n log n 约为 50,000，加速了 20 倍。当n为1,000,000时，加速比为10,000倍。这些加速可能是可计算变换与不受信号处理应用程序约束的变换之间的差异。自从 FFT 发明以来，人们一直在寻找更快的傅里叶变换。一个问题是你能走多快。看起来您可能至少需要 n 次运算来计算 FFT，因为仅需要 n 步才能将其写下来。 FFT 比合理速度限制慢 5*log 2 (n) 倍，并且 5*log 2 (n) 因子可能很大。当 n 为一万亿时，它是 200。你能采取一些巧妙的措施来减少 200 的前因数吗？好吧，你瞧，在 OpenAI 上周在数学界发表的大量论文中，他们声称拥有更快的傅里叶变换。他们的区别性命名“main.pdf”的主要主张是我对这里发生的事情很感兴趣。理论上，log(n) 项比标准 FFT 中的项小一点点。我读过这篇论文吗？当然不是。 OpenAI 也没有人读过这篇论文，那我为什么要读呢？我做了世界上所有其他数学家对 AI slop 数学所做的事情：我将其反馈到 slop 机器中，并使用聊天机器人界面运行信息检索会话以提取显着事实。拟人化地说：我问 ChatGPT 它对自己的输出有何看法。这就是我们现在进行数学研究的方式。真是一个世界啊。不幸的是，我没有找到更快的傅里叶变换。相反，我发现，当形式主义变得如此脱离现实时，应用数学理论内部就会出现腐烂现象，以至于“突破”只不过是数学家无法用自然语言正确指定游戏规则的产物。首先，“大O”表示法被滥用，以至于变得毫无意义。让我们回顾一下这个定义，作为一名本科生，它给我留下了深刻的印象。如果存在整数 N 和常量 C，则算法的运行时间为 T(n) = O(F(n))，也就是说，只要 n 很大，算法实际采取的步数上限为常量乘以某个方便函数 F(n)。 F(n) 通常是熟悉且可解释的东西，例如多项式或指数函数。这种表示法表明我们只关心计算量很大时会发生什么。我们关心计算时间的渐近增长率。所有常数都是等效的。 Big-O 表示法对于算法会计中的快捷方式很有用，但它也允许显着的逻辑惰性。如果我们想要一个实际上更快的 FFT，我们需要一个对于合理大小的 n 需要少于 50n 次操作的算法。但 O(n) 并不意味着 50 n。它可能意味着 10 80 n。这将被视为“线性时间”算法。需要 n + 10 80 的算法也被认为是大 O 体系中的线性时间算法。仅当 n 大于 10 80 时具有线性时间保证的算法也被视为线性时间。 10 80 大约等于