快速傅里叶变换

模长的定义：

Z=\left[ \begin{array}{ccc} z_1 \\ z_2 \\ ... \\ z_n \end{array} \right] 每个 z 都是复数， Z 向量在 C^n 空间中，而不是 R^n 空间中，那么它的模是什么？

用 Z^TZ 是不可以的，因为如果是这样子相乘，比如向量是 \left[ \begin{array}{ccc} 1 & i \end{array} \right]\left[ \begin{array}{ccc} 1 \\ i \\ \end{array} \right]=1^2+i^2=0 但是模的长度不能是0，所以这种相乘是没有意义的。

那么就可以使用它的共轭复数来相乘，得到模长，即： \left[ \begin{array}{ccc} \bar1 & \bar i \end{array} \right]\left[ \begin{array}{ccc} 1 \\ i \\ \end{array} \right]= 1+1=2 ，所以模长是 \sqrt{2} ，那么这个向量值只有在零向量时才会算出0 ，其它的情况都会是正数的情况。这个就是模长的定义。

这个式子在做转置的时候是要求出每个 z_i 的共轭复数的。 \left[ \begin{array}{ccc} \bar z_1 & \bar z_2 \end{array} \right]\left[ \begin{array}{ccc} z_1 \\ z_2 \\ \end{array} \right]= |z_1|^2+|z_2|^2

向量的内积：(H=Hermitian)：

\bar y^Tx=y^Hx 大部分情况下内积的结果也是复数，向量与自身的内积就是模的平方。

复数对阵矩阵：

A^T=A 对于实数矩阵成立，但是对于复数矩阵是不成立的。 所以和上面的模的类似，应该为 \bar A^T=A 在计算的时候需要先转置再计算共轭，但是对角线上的数据不用取共轭。

A=\left[ \begin{array}{ccc} 2 & 3+i \\ 3-i & 5 \\ \end{array} \right] 这个就是复数的Hermitian矩阵， A^H=A （H表示共轭转置）

如果求一下上面的转置 A^H ，首先转换位置 \left[ \begin{array}{ccc} 2 & 3-i \\ 3+i & 5 \\ \end{array} \right] 然后取共轭 \left[ \begin{array}{ccc} 2 & 3-i \\ 3+i & 5 \\ \end{array} \right]=A

上一节课中有提到，复数矩阵的特征值也是实数，特征向量相互垂直。

\begin{array}{ccc} q_1 & q_2 & ...q_n \end{array} 有 \bar q_i^Tq_j=q_i^Hq_j=\left\{ \begin{array}{ccc} 0 & i=j\\ 1 & i\ne j\\ \end{array} \right\}

例如： Q=\left[ \begin{array}{ccc} | &| & ...&|\\ q_1 & q_2 & ...& q_n \\ | &| & ...&|\\ \end{array} \right]

实数: Q^TQ=I （正交）

复数: \bar Q^TQ=I=Q^HQ （正交，类比实数的得出复数的）

把对阵矩阵的概念改成埃米尔特矩阵，也同时给正交矩阵改了个名字叫“酉矩阵”。什么是酉矩阵呢？首先它是n阶方阵，列向量正交（相互垂直 ）计算的时候要共轭转置 。

傅里叶矩阵

n阶傅里叶矩阵 F_n=\left[ \begin{array}{ccc} 1 & 1 & 1 & 1\\ 1 & w & w^2 & w^{n-1}\\ 1& w^2 & w^{4} & w^{2(n-1)}\\ . & . & . & .\\ 1 & w^{n-1}& w^{2(n-1)} & w^{(n-1)(n-1)}\\ \end{array} \right] ， (Fn)_{ij}=w_{ij} 其中 ij=0,1,3...(n-1)

式子中有很多个： w^n=1，此时 w=e^{\frac{i2\pi}{n}}=cos(\frac{2\pi}{n})+isin(\frac{2\pi}{n}) ， w 是落在单位圆上的数。

欧拉当时发明这个函数的原因可能是后面这个 cos(\frac{2\pi}{n})+isin(\frac{2\pi}{n}) 不好计算，但是前面的 e^{\frac{i2\pi}{n}} 好计算。

因为 2\pi 正好是一圈：

如果n是6的话，那么n=1正好是 {60}^{o} ，也就是图中的 w^{1} ，那么 w^6=1 ，也就是说6阶傅里叶方阵就是这个 e^{\frac{2\pi}{6}} 和它的乘方构造出来的，正好在圆上。

如果n是4的话，那么n=4的时候， w=e^{\frac{2i\pi}{4}}=e^{\frac{i\pi}{2}} ，此时n=1的时候是 90^o ，那n=4的时候等于1，即 w^4=1

i^1，i^2=-1，i^3=-i，i ^4=1

（这里每次乘以自己，都会逆时针旋转 60^o或者90^o ）

F_4=\left[ \begin{array}{ccc} 1 & 1 & 1 & 1\\ 1 & w & w^2 & w^{4-1}\\ 1& w^2 & w^{4} & w^{2(4-1)}\\ 1 & w^{4-1}& w^{2(4-1)} & w^{(4-1)(4-1)}\\ \end{array} \right]= \left[ \begin{array}{ccc} 1 & 1 & 1 & 1\\ 1 & i & i^2 & i^3\\ 1& i^2 & i^{4} & i^6\\ 1 & i^3& i^6 & i^9\\ \end{array} \right]=\left[ \begin{array}{ccc} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1& -1 & 1 & -1\\ 1 & -i& -1 & i\ \end{array} \right]

(指数等于行序数乘以列序数，从0开始)

为什么这个矩阵很有意义呢？四点傅立叶变换实际上作用于四维向量，向量分别左乘矩阵 F_4或者F_4^{-1} 一个就是傅里叶变换，另一个就是傅里叶逆变换。

上述的 F_4 的个列都是正交的， 我们很容易的计算它的逆矩阵，而且还可以把它分解成“稀疏矩阵”，验证是否正交，第二列和第四列，先取共轭再计算（不要直接计算，虽然结果相同。不要忘记取共轭，取共轭，取共轭）

第二列第四列=取共轭（1，-i，-1，i）*（1，- i，-1，i）=1-1+1-1=0（如果不取共轭结果等于4）

由于列向量的长度是2，所以它不是一个标准正交矩阵。可以乘以 \frac{1}{2} 得到标准正交矩阵。而这个标准正交向量可以快速得到逆矩阵，复数矩阵转置等于共轭转置H，所以： F^H_4F_4=I ，标准正交矩阵相乘等于单位矩阵（此处的F是包含 \frac{1}{2} ），那么 F^H 就等于它的逆矩阵，即 F^{-1}=F^H ，逆矩阵各列也是正交的。

以上性质都是一些比较好的性质，但是是什么性质导致了快速傅里叶变换的问世呢？

F_6和它的一半F_3存在着某种关系，F_8和F_4，F_{64}和F_{32}都存在这种关系， F_{64} 是一个64阶方阵。

64的w是1的64次方，32的w是1的32次方，那么它们的角度应该是2倍关系。

W_{64}^2=W_{64}W_{64}=e^\frac{i2\pi}{64}e^\frac{i2\pi}{64}=e^\frac{i2\pi}{32}=W_{32} 复数的平方，辐角翻倍（一个是64次循环一次到1，一个是23次循环到1）。

我们知道这个关系之后，如果要计算 W_{64}平方本来是需要64x64次，但是如果转换成 W_{32} 那么计算量直接下降就变成了：2x32x32次（如下矩阵。之前计算是64x64，现在计算到32的位置就可以停止了，因为其余的都是0，但是有两个 F_{32} 所以乘以2）

那怎么将64转成32的呢？就是说如何得到式子 \left[ \begin{array}{ccc} F_{64} \end{array} \right]\rightarrow \left[ \begin{array}{ccc} F_{32} & 0\\ 0 & F_{32} \end{array} \right]

为什么是这个式子呢？因为如果左下角或者右上角不是0，计算的时候就不会是32次，只有0的时候才会减少计算。

如果想让这个式子相等，后面矩阵两边还需要乘以一个修正矩阵，使等式可以相等。

那这个修正矩阵怎么求？

\left[ \begin{array}{ccc} F_{64} \end{array} \right]=\left[ \begin{array}{ccc} F_{修正} \end{array} \right] \left[ \begin{array}{ccc} F_{32} & 0\\ 0 & F_{32} \end{array} \right]\left[ \begin{array}{ccc} F_{修正} \end{array} \right] \Rightarrow \left[ \begin{array}{ccc} F_{64} \end{array} \right]= \left[ \begin{array}{ccc} I & D \\ I & -D \end{array} \right] \left[ \begin{array}{ccc} F_{32} & 0\\ 0 & F_{32} \end{array} \right]\left[ \begin{array}{ccc} P \end{array} \right] 这个修正带来的计算量会是2x32x32加上这部分修正开销（32次数值乘法），也就是： 2(32)^2+左乘的矩阵开销 。而且左右两边的修正矩阵也包含大量的0元素。

那么这个右侧应该是置换矩阵 P ，奇数位是1，下面的偶数位上是1，如下： \left[ \begin{array}{ccc} F_{32} & 0\\ 0 & F_{32} \end{array} \right]\left[ \begin{array}{ccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0& 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0& 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0& 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0& 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0& 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0& 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 1\\ .&.&. \end{array} \right] 作用到矩阵上之后得到 \left[ \begin{array}{ccc} q_1& q_3 & 0 &0...\\ 0 & 0 & q_2&q_4...\\ \end{array} \right] 奇数列在上面，偶数列在下面，就把偶数列排到了前面，这一步只是移动不计算，所以无开销。然后上面的矩阵左乘 \left[ \begin{array}{ccc} I & D \\ I & -D \end{array} \right]\left[ \begin{array}{ccc} q_1& q_3 & 0 &0...\\ 0 & 0 & q_2&q_4...\\ \end{array} \right] ， D=\left[ \begin{array}{ccc} 1 &&&&\\ &w^1&&&\\ &&w^2&&\\ &&&&w^{n-1}\\ \end{array} \right] 所以矩阵计算的开销仅是乘以D引起的32次乘法，那么总开销就变成了： 2(32)^2+32

依此类推： 2[ 2(16)^{2}+16 ]^2+32 ......从64-2一共修正6（32，16，8，4，2，1）次，也就是6x32

即： log_{2}^{64}*\frac{64}{2} 推出 \frac{1}{2}nlog^n_2 ，减少了运算量。

举例： n=1024=2^{10} , n^2>1,000,000

但是通过傅里叶变换之后计算量为： \frac{1}{2}nlog^n_2=512log_2^{1024}=512*10 计算量下降200倍。