线性代数导论(27)-复数矩阵和快速傅里叶变换(最新讲义)

本讲主要介绍复数向量、复数矩阵的相关知识(包括如何做复数向量的点积运算、什么是复数对称矩阵等),以及傅里叶矩阵(最重要的复数矩阵)和快速傅里叶变换。

复数矩阵运算

先介绍复数向量,我们不妨换一个字母符号来表示:$z=\begin{bmatrix}z_1\\z_2\\\vdots\\z_n\end{bmatrix}$,向量的每一个分量都是复数。此时$z$不再属于$\mathbb{R}^n$实向量空间,它现在处于$\mathbb{C}^n$复向量空间。

计算复向量的模

对比实向量,我们计算模只需要计算$\left|v\right|=\sqrt{v^Tv}$即可,而如果对复向量使用$z^Tz$则有$z^Tz=\begin{bmatrix}z_1&z_2&\cdots&z_n\end{bmatrix}\begin{bmatrix}z_1\\z_2\\\vdots\\z_n\end{bmatrix}=z_1^2+z_2^2+\cdots+z_n^2$,这里$z_i$是复数,平方后虚部为负,求模时本应相加的运算变成了减法。(如向量$\begin{bmatrix}1&i\end{bmatrix}$,右乘其转置后结果为$0$,但此向量的长度显然不是零。)

根据上一讲我们知道,应使用$\left|z\right|=\sqrt{\bar{z}^Tz}$,即$\begin{bmatrix}\bar z_1&\bar z_2&\cdots&\bar z_n\end{bmatrix}\begin{bmatrix}z_1\\z_2\\\vdots\\z_n\end{bmatrix}$,即使用向量共轭的转置乘以原向量即可。(如向量$\begin{bmatrix}1&i\end{bmatrix}$,右乘其共轭转置后结果为$\begin{bmatrix}1&-i\end{bmatrix}\begin{bmatrix}1\\i\end{bmatrix}=2$。)

我们把共轭转置乘以原向量记为$z^Hz$,$H$读作埃尔米特(人名为Hermite,形容词为Hermitian)

计算向量的内积

有了复向量模的计算公式,同理可得,对于复向量,内积不再是实向量的$y^Tx$形式,复向量内积应为$y^Hx$。

对称性

对于实矩阵,$A^T=A$即可表达矩阵的对称性。而对于复矩阵,我们同样需要求一次共轭$\bar{A}^T=A$。举个例子$\begin{bmatrix}2&3+i\\3-i&5\end{bmatrix}$是一个复数情况下的对称矩阵。这叫做埃尔米特矩阵,有性质$A^H=A$。

正交性

在第十七讲中,我们这样定义标准正交向量:$q_i^Tq_j=\begin{cases}0\quad i\neq j\\1\quad i=j\end{cases}$。现在,对于复向量我们需要求共轭:$\bar{q}_i^Tq_j=q_i^Hq_j=\begin{cases}0\quad i\neq j\\1\quad i=j\end{cases}$

第十七讲中的标准正交矩阵:$Q=\Bigg[q_1\ q_2\ \cdots\ q_n\Bigg]$$Q^TQ=I$。现在对于复矩阵则有$Q^HQ=I$

就像人们给共轭转置起了个“埃尔米特”这个名字一样,正交性(orthogonal)在复数情况下也有了新名字,酉(unitary),酉矩阵(unitary matrix)与正交矩阵类似,满足$Q^HQ=I$的性质。而前面提到的傅里叶矩阵就是一个酉矩阵。

傅里叶矩阵

$n$阶傅里叶矩阵$F_n=\begin{bmatrix}1&1&1&\cdots&1\\1&w&w^2&\cdots&w^{n-1}\\1&w^2&w^4&\cdots&w^{2(n-1)}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&w^{n-1}&w^{2(n-1)}&\cdots&w^{(n-1)^2}\end{bmatrix}$,对于每一个元素有$(F_n)_{ij}=w^{ij}\quad i,j=0,1,2,\cdots,n-1$。矩阵中的$w$是一个非常特殊的值,满足$w^n=1$,其公式为$w=e^{i2\pi/n}$。易知$w$在复平面的单位圆上,$w=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}$

在傅里叶矩阵中,当我们计算$w$的幂时,$w$在单位圆上的角度翻倍。比如在$6$阶情形下,$w=e^{2\pi/6}$,即位于单位圆上$60^\circ$角处,其平方位于单位圆上$120^\circ$角处,而$w^6$位于$1$处。从开方的角度看,它们是$1$的$6$个六次方根,而一次的$w$称为原根。

  • 我们现在来看$4$阶傅里叶矩阵,先计算$w$有$w=i,\ w^2=-1,\ w^3=-i,\ w^4=1$$F_4=\begin{bmatrix}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{bmatrix}=\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}$

    矩阵的四个列向量正交,我们验证一下第二列和第四列,$\bar{c_2}^Tc_4=1-0+1-0=0$,正交。不过我们应该注意到,$F_4$的列向量并不是标准的,我们可以给矩阵乘上系数$\frac{1}{2}$(除以列向量的长度)得到标准正交矩阵$F_4=\frac{1}{2}\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}$。此时有$F_4^HF_4=I$,于是该矩阵的逆矩阵也就是其共轭转置$F_4^H$。

快速傅里叶变换(Fast Fourier transform/FFT)

对于傅里叶矩阵,$F_6,\ F_3$$F_8,\ F_4$$F_{64},\ F_{32}$之间有着特殊的关系。

举例,有傅里叶矩阵$F_64$,一般情况下,用一个列向量右乘$F_{64}$需要约$64^2$次计算,显然这个计算量是比较大的。我们想要减少计算量,于是想要分解$F_{64}$,联系到$F_{32}$,有$\Bigg[F_{64}\Bigg]=\begin{bmatrix}I&D\\I&-D\end{bmatrix}\begin{bmatrix}F_{32}&0\\0&F_{32}\end{bmatrix}\begin{bmatrix}1&&\cdots&&&0&&\cdots&&\\0&&\cdots&&&1&&\cdots&&\\&1&\cdots&&&&0&\cdots&&\\&0&\cdots&&&&1&\cdots&&\\&&&\ddots&&&&&\ddots&&\\&&&\ddots&&&&&\ddots&&\\&&&\cdots&1&&&&\cdots&0\\&&&\cdots&0&&&&\cdots&1\end{bmatrix}$

我们分开来看等式右侧的这三个矩阵:

  • 第一个矩阵由单位矩阵$I$和对角矩阵$D=\begin{bmatrix}1&&&&\\&w&&&\\&&w^2&&\\&&&\ddots&\\&&&&w^{31}\end{bmatrix}$组成,我们称这个矩阵为修正矩阵,显然其计算量来自$D$矩阵,对角矩阵的计算量约为$32$即这个修正矩阵的计算量约为$32$,单位矩阵的计算量忽略不计。

  • 第二个矩阵是两个$F_{32}$与零矩阵组成的,计算量约为$2\times 32^2$

  • 第三个矩阵通常记为$P$矩阵,这是一个置换矩阵,其作用是讲前一个矩阵中的奇数列提到偶数列之前,将前一个矩阵从$\Bigg[x_0\ x_1\ \cdots\Bigg]$变为$\Bigg[x_0\ x_2\ \cdots\ x_1\ x_3\ \cdots\Bigg]$,这个置换矩阵的计算量也可以忽略不计。(这里教授似乎在黑板上写错了矩阵,可以参考FFTHow the FFT is computed做进一步讨论。)

所以我们把$64^2$复杂度的计算化简为$2\times 32^2+32$复杂度的计算,我们可以进一步化简$F_{32}$得到与$F_{16}$有关的式子$\begin{bmatrix}I_{32}&D_{32}\\I_{32}&-D_{32}\end{bmatrix}\begin{bmatrix}I_{16}&D_{16}&&\\I_{16}&-D_{16}&&\\&&I_{16}&D_{16}\\&&I_{16}&-D_{16}\end{bmatrix}\begin{bmatrix}F_{16}&&&\\&F_{16}&&\\&&F_{16}&\\&&&F_{16}\end{bmatrix}\begin{bmatrix}P_{16}&\\&P_{16}\end{bmatrix}\Bigg[\ P_{32}\ \Bigg]$。而$32^2$的计算量进一步分解为$2\times 16^2+16$的计算量,如此递归下去我们最终得到含有一阶傅里叶矩阵的式子。

来看化简后计算量,$2\left(2\left(2\left(2\left(2\left(2\left(1\right)^2+1\right)+2\right)+4\right)+8\right)+16\right)+32$,约为$6\times 32=\log_264\times \frac{64}{2}$,算法复杂度为$\frac{n}{2}\log_2n$

于是原来需要$n^2$的运算现在只需要$\frac{n}{2}\log_2n$就可以实现了。不妨看看$n=10$的情况,不使用FFT时需要$n^2=1024\times 1024$次运算,使用FFT时只需要$\frac{n}{2}\log_2n=5\times 1024$次运算,运算量大约是原来的$\frac{1}{200}$

下一讲将继续介绍特征值、特征向量及正定矩阵。


技术交流学习,请加QQ微信:631531977
目录