数学笔记：FFT（快速傅里叶变换）_快速傅里叶变换fft公式-程序员宅基地

技术标签：矩阵线性代数数学知识整理

0 前言

FFT是一个很厉害的算法，几乎任何和信号处理有关的算法都依赖于FFT

0.1 引入：多项式的系数表示法

我们从一个简单的问题中引入FFT：

给定两个多项式，我们希望去计算二者的乘积

中学的时候我们学过，展开相乘就可以了

但是在计算机里面，一个很重要的问题是，如何存储一个多项式？

显然，最自然的方法就是存储多项式的系数，我们把系数映射到一个列表中，这样列表中第k个数字正好对应第k阶系数——>这种表示方法，即是多项式的系数表示法

一般来说，给定两个d阶的多项式，二者的乘积应该是2d阶的多项式，所以如果用naive的乘法分配律来计算，时间复杂度应该是 $\large O(d^2)$ 【多项式A中的每一项都会跟多项式B中的所有项分别相乘】

那么问题来了，这个算法可以更快一点吗？

0.2 多项式的数值表示法

我们知道，任意的d阶多项式，可以由d+1个点唯一确定

即对于一个p阶多项式

p+1个点确定了之后，多项式的系数可以唯一确定

证明如下：

我们将这d+1个点带入多项式中，得到d+1个方程

将其转化为矩阵&向量的形式

我们可以发现，只要这d+1个x不一样，那么矩阵始终可逆（该矩阵对应的行列式为范德蒙行列式）

于是我们得到了多项式的两种表示方法：

利用值表示法，多项式乘法就变得很简单：

我们知道了乘法之后的阶数为4维，于是我们分别在A(x)和B(x)上取5个点，然后将对应每个点的两个值相乘，得到C在每个点的函数值。然后根据前面的证明，我们知道，这五个点唯一决定了这个乘积多项式的系数

于是我们不难发现，使用值表示法之后，计算多项式乘法的时间，从原来的 $\large O(d^2)$ 缩短至O(d)

0.3 多项式乘法的框架

于是我们就可以得到多项式乘法的新框架了：

给定两个d阶多项式，我们已经知道了值表示法计算多项式乘法计算多项式乘法更快，所以我们可以先计算两个多项式在2d+1个点上的值

然后将函数值一对一对乘起来，从而得到乘出来的多项式的值表示

然后，最后一步需要做的是，把值表示转换回系数表示

但问题在于，我们如何把系数形式转换成值表示形式？与此同时，如何把值表示形式转化为系数表示形式？这个就是FFT考虑的内容了

1 求值 evaluation

我们先关注从系数表示到值表示的方向

给定d阶多项式和n个点(n≥d+1)，我们想计算多项式在这n个点上的值，最简单粗暴的方法就是随便挑选n个点，一个一个地计算函数值

但是这样的问题在于，每一个点的计算都是O(d)的时间复杂度，加起来的时间复杂度还是 $\large O(nd)\ge O(d^2)$ ——>这样的话，相当于啥都没做

对于奇函数和偶函数，我们可以取一对一对的相反数，这样可以减少一半的采样点

对于一般的函数，我们可以将其分成奇函数+偶函数的形式

然后我们将奇函数的x提出来，得到两个偶函数的形式

我们将两部分都看成 $\large x^2$ 的函数，于是可以发现Pe和Po的阶数都降到了原先的一半

那么，对于 $\large P_e(x^2)$ 和 $\large P_o(x^2)$ ，这两个又是两个求值问题

而我们一开始取的是一对一对的相反数，所以这里只剩下一半的点了(n/2)

2.1 FFT总结？

我们可以看出来，这是一个递归的思想

总结一下就是，我们想计算多项式P在n个点上的值，这n个点是一对一对的相反数

我们将多项式分成两个部分（两个阶为n/2-1的多项式），每个多项式只需要求n/2个点的值

我们只需要递归地求解这两个分多项式的值，就可以得到原多项式的n个值

如果这一切可行，那么我们的时间复杂度是O(nlogn)【每一层对应点的值相乘还是n，只不过现在从上到下，每一层阶数减半，故只有logn层】

2.2 引入复数的概念

但是至此为止，还是有一个小问题，就是从第一次迭代开始， $\large P_e(x^2)$ 和 $\large P_o(x^2)$ 只能取正值，但我们希望新的求指点也可以是相反数

于是我们在这里引入了复数的概念

1的n次方根，用图像表示，可以解释为在复平面上沿着单位元等距排布的一系列点，其中任意两点之间的夹角为 $\large \frac{2\pi}{n}$

2.2.1 欧拉公式

用欧拉公式，可以很简单地表达这些点：

所以我们找的值就是1，ω，... $\large \omega^{n-1}$

2.3 FFT总结！

FFT算法的输入是多项式的n个系数 $\large p_0,\dots,p_{n-1}$ ,其中n是2的幂（也可以不是，只不过复杂一些）
我们取 $\large \omega=e^{\frac{2\pi i}{n}}$ 为1的n次方根（最底层的递归情况是P(1))
递归的主要命令，就是把多项式拆分成奇函数和偶函数的部分，两部分分别调用函数。此时两个子多项式函数都是n/2阶的，所以对应的求值点是1的n/2次方根
我们假设得到的两部分结果为ye和yo，那么我们可以把这两部分函数值结合一下，计算出原多项式函数在对应点的函数值

结合的核心思想是利用正负对，不过这里我们是n次方根，所以稍作修改

与此同时，我们知道 $\large -\omega^j=\omega^{j+\frac{n}{2}}$ ，于是再做修改

同时，我们又有

于是进一步，可以写成

2.4 FFT伪代码

2.5 用公式表达FFT和iFFT

已知一个序列 $(x_0,\cdots,x_{N-1})$ ,我们可以用 $\lfloor N/2 \rfloor +1$ 个傅里叶系数表示，其中第k项为

3 interpolation 差值

实际上差值和求值是紧密联系的，我们之间将求值问题表示为矩阵-向量乘积

因为FFT中的x是1的n次方根，所以可以改写为

这个矩阵被称为离散傅里叶变换矩阵DFT

而我们的差值，即取逆即可

参考资料：The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? - YouTube

本文链接：https://blog.csdn.net/qq_40206371/article/details/123243309

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

手把手教你安装Eclipse最新版本的详细教程（非常详细，非常实用）_eclipse安装教程-程序员宅基地

文章浏览阅读4.4k次，点赞2次，收藏16次。写这篇文章的由来是因为后边要用这个工具，但是由于某些原因有部分小伙伴和童鞋们可能不会安装此工具，为了方便小伙伴们和童鞋们的后续学习和不打击他们的积极性，因为80%的人都是死在工具的安装这第一道门槛上，这门槛说高也不高说低也不是太低。所以就抽时间水了这一篇文章。_eclipse安装教程

分享11个web前端开发实战项目案例+源码_前端项目实战案例-程序员宅基地

文章浏览阅读4.1w次，点赞12次，收藏193次。小编为大家收集了11个web前端开发，大企业实战项目案例+5W行源码！拿走玩去吧！1）小米官网项目描述：首先选择小米官网为第一个实战案例，是因为刚开始入门，有个参考点，另外站点比较偏向目前的卡片式设计，实现常见效果。目的为学者练习编写小米官网，熟悉div+css布局。学习资料的话可以加下web前端开发学习裙：600加上610再加上151自己去群里下载下。项目技术：HTML+CSS+Div布局2）迅雷官网项目描述：此站点特效较多，所以通过练习编写次站点，学生可以更多练习CSS3的新特性过渡与动画的实_前端项目实战案例

计算质数-埃里克森筛法（间隔黄金武器）-程序员宅基地

文章浏览阅读73次。素数，不同的质数，各种各样的问题总是遇到的素数。以下我们来说一下求素数的一种比較有效的算法。就是筛法。由于这个要求得1-n区间的素数仅仅须要O（nloglogn）的时间复杂度。以下来说一下它的思路。思路：如今又1-n的数字。素数嘛就是除了1和本身之外没有其它的约数。所以有约数的都不是素数。我们从2開始往后遍历，是2的倍数的都不是素数。所以我们把他们划掉然后如...

探索Keras DCGAN：深度学习中的创新图像生成-程序员宅基地

文章浏览阅读532次，点赞9次，收藏14次。探索Keras DCGAN：深度学习中的创新图像生成项目地址:https://gitcode.com/jacobgil/keras-dcgan在数据驱动的时代，图像生成模型已经成为人工智能的一个重要领域。其中，Keras DCGAN 是一个基于 Keras 的实现，用于构建和训练 Deep Convolutional Generative Adversarial Networks（深度卷积生...

org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):_spring-could org.apache.ibatis.binding.bindingexce-程序员宅基地

文章浏览阅读116次。今天在搭建springcloud项目时，发现如上错误，顺便整理一下这个异常：1. mapper.xml的命名空间（namespace）是否跟mapper的接口路径一致<mapper namespace="com.baicun.springcloudprovider.mapper.SysUserMapper">2.mapper.xml接口名是否和mapper.java接..._spring-could org.apache.ibatis.binding.bindingexception: invalid bound state

四种高效数据库设计思想——提高查询效率_数据库为什么能提高效率-程序员宅基地

文章浏览阅读1.1k次。四种高效数据库设计思想——提高查询效率：设计数据库表结构时，我们首先要按照数据库的三大范式进行建立数据。1. 1NF每列不可拆分2. 2NF确保每个表只做一件事情3. 3NF满足2NF，消除表中的依赖传递。三大范式的出现是在上世纪70年代，由于内存资源比较昂贵，所以严格按照三大范式进行数据库设计。而如今内存变得越来越廉价，在考虑效率和内存的基础上我们可以做出最优选择以达到最高效率。_数据库为什么能提高效率

随便推点

什么是配置_基于配置是什么意思-程序员宅基地

文章浏览阅读1.6k次。应用程序在启动和运行的时候往往需要读取一些配置信息，配置基本上伴随着应用程序的整个生命周期，比如：数据库连接参数、启动参数等。配置主要有以下几个特点：配置是独立于程序的只读变量配置对于程序是只读的，程序通过读取配置来改变自己的行为，但是程序不应该去改变配置配置伴随应用的整个生命周期配置贯穿于应用的整个生命周期，应用在启动时通过读取配置来初始化，在运行时根据配置调整行为。比如：启动时需要读取服务的端口号、系统在运行过程中需要读取定时策略执行定时任务等。配置可以有多种加载方式常见的有程序内部_基于配置是什么意思

二、使用GObject——一个简单类的实现-程序员宅基地

文章浏览阅读170次。Glib库实现了一个非常重要的基础类--GObject，这个类中封装了许多我们在定义和实现类时经常用到的机制：引用计数式的内存管理对象的构造与析构通用的属性（Property）机制 Signal的简单使用方式很多使用GObject..._

golang 定时任务处理-程序员宅基地

文章浏览阅读6.3k次，点赞2次，收藏9次。在 golang 中若写定时脚本，有两种实现。一、基于原生语法组装func DocSyncTaskCronJob() { ticker := time.NewTicker(time.Minute * 5) // 每分钟执行一次 for range ticker.C { ProcTask() }}func ProcTask() { log.Println("hello world")}二、基于 github 中封装的 cron 库实现package taskimport (_golang 定时任务