V27 负数矩阵和快速傅里叶变换.md

这一节我们讨论复数的情况,有时候,实矩阵也会有复数的特征值,所以要学会处理复数.当一阵子是复数,特征向量也变成复向量.

我来告诉你复矩阵最重要的一个例子,就是傅里叶矩阵!非礼也矩阵就是复矩阵,绝对是最重要的复矩阵.在傅里叶变换中需要用到.我还要介绍一个特殊的情况,就是快速傅里叶变换,FFT,在计算机中经常使用到,特别是涉及到大量数据的时候,因为可以很快速的进行傅里叶变换,也就是说,在做乘法的时候,怎么样用这个n-n的方阵(没有元素是0,是一个满矩阵)快速做乘法?通常,n阶方阵的乘法需要算n^2 次,如果这个矩阵的的列正交,我得说,这种矩阵是最棒的,而快速傅里叶变换,把n^2 次的计算缩减到nlogn!天壤之别!这只是一个矩阵的简单分解,但是改变是巨大的.

现在开始讲复矩阵和复向量

给定向量z,复数向量: $$ Z = ​​\left[\begin{matrix}z_1\z_1\\vdots\ z_n \end{matrix} \right] $$ 需要注意的是,已经不在属于 $R^n$,而是n维复空间,每一个分量都是复数,是在 $C^n$ 的.模长怎么求呢?注意,$z^T z$ 这样的公式求模长是不对的,因为模长的平方应该是正数的,假设分量都是$1+i$,那么 $z^T z$ 就是0了,但是明显有这个分量的模长不是0.正确的公式应该是 $z ̅^T z = |z|^2= z^H z$(H表示转置去共轭),应该使用共轭复数.

那么内积呢? 同样的道理,2个向量的内积不再是 $y^T x$,这样的公式这是对实向量而言,对于复向量来说,转置的时候,还要去共轭,那么公式是 $y ̅^T x= y^H x$,内积的结果也大多数时候不是实数了,而是复数,但是当y和x相同的时候,就是模长的平方,是实数

我们的改变对对称矩阵的看法了!前面对称矩阵的定义是,$A^T=A$,但是A是复矩阵的时候不好使,复数时对称矩阵的定义如下,也需要取共轭 $$ A ̅^T=A $$ 那么以为着,对角线上的元素只能是实数,因为转置的时候对角线元素是不变的,取共轭的时候,也不能变.如下是一个2-2例子

这样的矩阵叫做埃尔米特[Hermitian]矩阵:$A^H=A$

这些矩阵的特征值也是实数,特征向量也垂直.相互垂直以为着内积是....

---

现在讲垂直.垂直单位向量 $q_1…q_n$,也是就是标准正交基.垂直意味着, $$ \bar { q } _ { \mathrm { i } } ^ { \tau } q _ { \mathrm { j } } = q _ { \mathrm { i } } ^ { H } q _ { \mathrm { j } } = \left{ \begin{array} { l l } 0 & i ! = j \ 1 & i = j \end{array} \right. $$ 在是实数的情况下,我们知道 $Q = [q_1…q_n]$,这时候 $Q^T Q=I$,但是现在是复数,那我们得到的是 $Q^H Q=I$.

其实我们只是从实数空间 $R^n$ 到了负数空间 $C^n$ 而已,当然,对称矩阵的这个概念变成了埃尔米特矩阵,人们也给正交矩阵Q换了一个词:酉矩阵[unitary],也就是表示是n阶方阵,列向量标准正交,是单位向量,元素是复数.计算的时候记得取共轭

现在进入本节课的重点,最著名的复矩阵,也是酉矩阵,有正交的的列,以傅里叶命名.,因为来自于傅里叶转换.这个矩阵和我们息息相关.

首先看看n阶情况下它是怎么样的. 我们令n = 4,这样比较好计算.在接下来的半节课里,我最好也教一点电气工程的知识,然后再回到数学上.有什么区别呢?数学是从0开始,电气工程是从0开始,我们还是迁就一下他们把.

傅里叶矩阵的第0列是是1,然后第1列是w的以1为递增的指数,第2列是w以2为递增的指数...直到n-1列,注意这个矩阵是对称矩阵(实数的那种对称,但是傅里叶矩阵元素是复数)公式就是 $$ (F_n)_{ij}=w^{i ∗j} \qquad (i,j是从0 到 n-1) $$ 只要知道了w,那么傅里叶矩阵就可以知道了,这个矩阵没有0,是一个满矩阵.w是一个很特殊的值,n次方 $w^n=1$,事实上,有n个数字可以如此,其中一个就是1.而我们想要的w的值,角度是$2π/n$ $$ w = e ^ { \frac { i 2 \pi } { n } } = \cos \left( \frac { 2 \pi } { n } \right) + i \sin \left( \frac { 2 \pi } { n } \right) $$ 在复平面内,w落在单位圆上!在计算乘方的时候,不要用欧拉公式展开,因为石永红直角坐标系计算不是一个好办法.但是时候e的方式是比较简单的.

当n = 6,那么在复平面单位圆上的就是整个院角度的1/6,60度,而w^2,也在单位圆上,是120度,因为不管取多少次方,模长都是1.,w^6,回到了实轴1的位置,,也就是w^6=1,如下

可以这么说,w的幂,是1的6个6次方根[six sitth roots of 1].

现在看看n = 1的情况,也就是 $w^4=1$,这时候,$w = e^(i2π/4)$,逆时针旋恰好是90度.注意到,这时候, $$ \begin{array} { l } \mathrm { w } = e ^ { \frac { i 2 \pi } { 4 } } = \cos \left( \frac { \pi } { 2 } \right) + i \sin \left( \frac { \pi } { 2 } \right) = i \ w ^ { 2 } = e ^ { \frac { i 2 \pi } { 2 } } = \cos ( \pi ) + i \sin ( \pi ) = - 1 = i ^ { 2 } \ w ^ { 3 } = e ^ { \frac { i 2 \pi } { 4 } } = \cos \left( \frac { 3 \pi } { 2 } \right) + i \sin \left( \frac { 3 \pi } { 2 } \right) = - i = i ^ { 3 } \ w ^ { 3 } = e ^ { i 2 \pi } = \cos ( 2 \pi ) + i \sin ( 2 \pi ) = 1 = i ^ { 4 } \end{array} $$ 现在可以写下4-4的傅里叶矩阵了

为什么这个矩阵如此重要呢?通过这个4-4傅里叶矩阵,可以得到一个四点的傅里叶变换fout point Fourier transform,这个傅里叶变换该如何进行呢?四点傅里叶变换实际作用于四维向量[vector with four components],向量分量左乘矩阵F_4 或者〖F_4〗^(−1), ,一个是傅里叶变换.另一个则是傅里叶逆变换,两者如此接近,甚至容易混淆.这个矩阵的逆也是一个好矩阵,这个矩阵本身的各列是正交的,所以可以很容易的计算出这个矩阵的逆.还有些性质,连大名鼎鼎的傅里叶也不知道,也许高斯注意到了,但是没有十分重视.实际上这个矩阵如此特殊,我们可以把它分解为一系列的稀疏矩阵,这些矩阵具有大量的0元素,无论乘以它还是计算它的逆都非常的快捷,怎么做呢?

因为矩阵的各列正交(可以验证一下,但是注意一下需要注意取共轭,用c2和c4验证一下).没问题,.各列是正交的,但是不是标准正交的,所有的列的模长是2,我们可以轻易修改变成标准正交,只要把矩阵除以2就可以了,这样就是标准正交的了.

​

这又如何呢?可以立刻求它的逆!

这就是F_4 的优良性质,任何F_4 具有的性质,它的逆也有同样的性质,比如逆矩阵的各列也是正交的!但是有时什么性质导致FFT问世的呢?这就是接下来讨论的内容.

快速傅里叶变换FFT F_6 和F_3 之间存在某种奇妙的关系,F_8,F_4 也有,F_64,F_32 也有,也就是2倍关系的都有.比如,F_64 是一个64阶的方阵,w是1的64次方根,但是注意F_32 是一个32阶的矩阵,大小不一样,w是1的32次方根.注意,在单位圆上的角度,是2倍的关系,也就是说 $$ \left( w _ { 64 } \right) ^ { 2 } = w _ { 32 } $$

那么.F_64 和F_32 的联系是什么呢?F_64 与由2个F_32 构成的方阵有关,

注意看看上面2个矩阵,他们之间不相等的,要使他们相等,还需要补充一些修正矩阵,但是关键就在于右侧的零矩阵,如果F_64 乘以1个列向量,一般情况下,需要〖64〗^2 次乘法.但是左边的矩阵一半是0!下面看看补充矩阵,左右各一个,美妙的是,这些修正矩阵也存在大量的0.转换过后,原先的〖64〗^2 次,变成2*〖32〗^2 次,因为有2个F_32,还在再加上修正的开始,我们先确定一下修正矩阵

其中右侧是一个非常简单的奇偶置换矩阵,看第1斜行,总共32个1,1与1之间隔了一列,把它记做P,如果P乘以1个向量,就把向量偶数位置上的分量统统排到奇数分量前面,那么P就对F_64 的列的分量划分为奇偶2部分,分别进行32节傅里叶变换.再把他们重新组合,左边的修正矩阵就是I和对角矩阵D构成

因此修正的开销主要开销是左乘D的开销,因为P和I的开销都是很小的.对角阵D的开销一共有32次乘法.所以〖64〗^2 次方变成〖2∗32〗^2+32

D的元素是什么呢?也是w的幂

然后我们可以继续分解F_32 !左边的D不变.也就是....很难记录,看书把,,,,

这时候新的乘法次数是 $$ 2〖(2∗16〗^2+16)+32 $$

最终分解为2阶甚至是1阶傅里叶矩阵,左右两侧堆满了修正矩阵,右侧都是置换矩阵,左侧的矩阵有D和I构成,总共有多少个修正矩阵呢?log64个.一共有6步,先是32,然后是16,8,4,2,1.那么取代〖64〗^2 次乘法的是 $\log_2 64 ∗64/2$,也就是 $1/2 nlog_2 n$

假设 $n = 2^10$,那么 $n^2$ 大于100W,但是通过FFT,只需要 $1024 * 10/2=1024 ∗5$,是原来运算的1/200.这就是分解矩阵的功劳!实际上科学计算一直离不开傅里叶变换