跳转至

第二十七讲:复数矩阵和快速傅里叶变换

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

复数矩阵运算

先介绍复数向量,我们不妨换一个字母符号来表示:\(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}\)

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



回到顶部