L27-复数矩阵和快速傅里叶变换

参考

Unit III: Positive Definite Matrices and Applications - Complex Matrices; Fast Fourier Transform (FFT) | pdf
课本章节：Read Section 10.2 through 10.3 in the 4^th edition or Section 9.2 and 9.3 in the 5^th edition.
练习题：L27-复数矩阵和快速傅里叶变换-习题集

复向量 complex vector 是指构成向量的元素中含有复数，同理复矩阵 complex matrix 是指构成矩阵的元素中含有复数。

课程前面所讨论大多数向量和矩阵都只是由实数构成，而对于复向量和复矩阵，由于复数的存在，所以之前介绍的一些相关的性质和定义会有所不同。

复向量

实数向量 $v$ 模长与向量的平方的关系 $\|v\|^{2}=v^{T}v$ （从矩阵相乘的角度考虑，其中一个向量需要转置）

而对于复向量 $z=\begin{bmatrix} z_{1} \\ z_{2} \\ \vdots \\ z_{n} \end{bmatrix}$ ，它在 $n$ 维复数向量空间 $\mathbb{C}^{n}$ 中（而不是 $\mathbb{R}^{n}$ 实数向量空间中），则它的模长（平方）计算方式需要进行「修整」为共轭向量（的转置）与向量本身相乘

\begin{aligned} \|z\|^{2}&=\overline{z}^{T}z \\ &=\|z_{1}\|^{2}+\|z_{2}\|^{2}+\dots+\|z_{n}\|^{2} \end{aligned}

可以使用更简单的符号 $z^{H}$ 表示共轭向量的转置 $\overline{z}^{T}$ （包含两种运算），该符号读作 Hermitian 埃尔米特

所以复向量的模长平方也可以表示为 $\|z\|^{2}=z^{H}z$

提示

如果将实数向量的模长（平方）计算公式，直接套用于复向量中，例如 $z=\begin{bmatrix} 1 \\ i \end{bmatrix}$

\begin{aligned} z&=z^{T}z \\ &=\begin{bmatrix} 1 & i \end{bmatrix}\begin{bmatrix} 1 \\ i \end{bmatrix} \\ &=1^{2}+i^{2} \\ &=1-1 \\ &=0 \end{aligned}

如果直接进行平方，可能会得到 $i^{2}$ 由于它是负数 $-1$ 所以会对实数部分进行抵消，而不能得到反映向量模长的结果

而使用共轭向量相乘，得到 $-i^{2}$ 由于它是 $1$ ，所以并不会对虚部进行「扩张」，也不会对实数进行抵消，所得的结果正好是实部与虚部（系数）的平方和

例如对于 $z=\begin{bmatrix} 1 \\ i \end{bmatrix}$ 其模长的平方为

\begin{aligned} \|z\|^{2}&=\overline{z}^{T}z \\ &= \begin{bmatrix} 1 & -i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} \\ &=1+(-i^{2}) \\ &=1+1 \\ &=2 \end{aligned}

类似地，实数向量的内积 inner product/dot product 计算公式 $y^{T}x$ ，对于复向量也需要进行「修整」为共轭向量

\overline{y}^{T}x=\overline{y}_{1}x_{1}+\overline{y}_{2}x_{2}+\dots+\overline{y}_{n}x_{n}

内积也可以使用 hermitian 符号表示 $y^{H}x$

提示

复向量的内积所得到的结果一般也是复数

而复向量的模长（平方）就是复向量与其本身的内积，所得到的结果就比较特别，是各个元素的实部与虚部的平方和

复矩阵

对于仅由实数构成的矩阵 $A$ ，如果它是对称矩阵 symmetric matrix，则满足等式 $A^{T}=A$

而对应于复数矩阵，这种矩阵称作 Hermitain Matrix 埃尔米特矩阵，所需满足的等式是 $\overline{A}^{T}=A$

在复矩阵中，对称矩阵称为 Hermitain Matrix 埃尔米特矩阵，所满足的等式是 $\overline{A}^{T}=A$ 也可以简写为 $A^{H}=A$

例如 $A^{T}=A=\begin{bmatrix} 2 & 3+i \\ 3-i & 5 \end{bmatrix}$

提示

在复矩阵中的 Hermitain Matrix 埃尔米特矩阵，与实数矩阵中的对称矩阵具有类似的特性，即它的特征值 eigenvalue 是实数，特征向量 eigenvector 相互垂直/正交

对于仅由实数构成的正交矩阵 $Q$ ，满足的等式 $Q^{T}Q=I$

具体而言，各列向量 $q_{i}$ 需要满足以下公式

q_{i}^{T}q_{j}=\begin{cases} 0, & if \ i \ne j \\ 1, & if \ i = j \end{cases}

而对应于复数矩阵，这种矩阵称作 Unitarty Matrix 酉矩阵，各列向量 $q_{i}$ 需要满足以下公式

\overline{q}_{i}^{T}q_{j}=\begin{cases} 0, & if \ i \ne j \\ 1, & if \ i = j \end{cases}

在复矩阵中，正交矩阵称为 Unitarty Matrix 酉矩阵，所满足的等式可以简写为 $Q^{H}Q=I$

傅里叶矩阵

傅里叶级数 Fourier series 是一种将周期性函数或信号表示为不同频率函数（三角函数）之和的方法

f(x)=a_{0}+a_{1}\cos x+b_{1}\sin x+a_{2}\cos 2x+b_{2}\sin 2x+\dots

在处理有限数据集时，离散傅里叶变换是实现这种分解的关键，以下用矩阵的形式来表示

F_{n}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & w & w^{2} & \dots & w^{n-1} \\ 1 & w^{2} & w^{4} & \dots & w^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w^{n-1} & w^{2(n-1)} & \dots & w^{(n-1)^{2}} \end{bmatrix}

以上是一个 $n \times n$ 的傅立叶矩阵，它属于酉矩阵（正交矩阵），各列向量相互垂直/正交

索引值

傅里叶变换常用于处理信号，在物理中数据集的索引值一般是从 $0$ 开始的，而在纯数学研究中数据集的索引值则是从 $1$ 开始的

在傅里叶矩阵中沿用物理习惯，索引值从 $0$ 开始

其中各元素的通式是 $(F_{n})_{ij}=w^{ij}$ （其中 $i,j=0, \dots, n-1$ ，索引值从 $0$ 开始）

对于傅里叶矩阵 $F_{n}$ 中的元素 $w$ ，满足 $w^{n}=1$ 所以 $w=e^{i\cdot 2\pi/n}=\cos(2\pi/n)+i\sin(2\pi/n)$ ，则 $w$ 是落在（极坐标系）复平面的单位圆上

所以 $w$ 是具有周期的，例如对于 $F_{4}$ ，则 $w$ 是位于复平面单位元的（逆时针）四分之一处 $w=e^{i \cdot 2\pi/4}=e^{\frac{\pi}{2}i}=i$ ，那么 $w^{2}=i^{2}=-1$ 、 $w^{3}=i^{3}=-i$ 、 $w^{4}=i^{4}=1$ 周期为 $4$

提示

以上关于 $w$ 的公式变换在课堂中并没有证明，应该是使用了欧拉公式将复指数函数转换为三角函数

e^{ix}=\cos x+i\sin x

当变量为 $x=\pi$ 时，可得 $e^{i\pi}=\cos \pi+i\sin \pi=-1+0$

一般写成 $e^{i\pi}+1=0$ 称为欧拉恒等式，被尊称为「最美的数学公式」，因为该公式将 $e$ 、 $i$ 、 $\pi$ 、 $1$ 、 $0$ 这五个数学中特殊的数结合在一起了

可以使用一些支持复数的在线计算器，基于欧拉公式将复数幂指数转换为三角函数

快速傅里叶变换

根据前面的推导，可以得到 $4 \times 4$ 傅里叶矩阵

\begin{aligned} 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} \end{aligned}

该 $4 \times 4$ 傅里叶矩阵可以对一个具有四个分量（四个数据点）的向量进行傅里叶变换，通过将 $F_{4}$ 与向量相乘

例如向量 $\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$ 表示一个在时间点为 $0$ 时所记录得到的信号值，可以通过 $F_{4}$ 矩阵对其进行傅里叶变换

\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}= \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}

通过傅里叶变换将这一个信号分解到四个频率上，它们具有相同的值

提示

可以再使用 $F_{4}$ 矩阵对分解的结果向量进一步变换

\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}= \begin{bmatrix} 4 \\ 0 \\ 0 \\ 0 \end{bmatrix}= 4 \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}

可以恢复得到原向量（与之平行的向量）

用公式表示以上运算 $F^{H}_{4}F_{4}v=v$ 可知 $F^{H}_{4}F_{4}$ 是 $I$ ，可证得 $F_{4}$ 是酉矩阵

这也符合前面的总结，即傅里叶矩阵是酉矩阵（对应于实数矩阵中的正交矩阵）

在进一步变换所得到的向量是 $\begin{bmatrix} 4 \\ 0 \\ 0 \\ 0 \end{bmatrix}$ 而不是 $\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$ 由于所乘上的矩阵 $F_{4}$ 严格而言「不是」酉矩阵，由于它的各个列向量的模长并不是 $1$ ，矩阵应该乘上系数（各个列向量的模长的倒数） $\frac{1}{\sqrt{n}}F_{n}$ 才是酉矩阵

在进行傅里叶变换时，傅里叶矩阵 $F_{2n}$ 与向量 $x$ 相乘，如果以矩阵的元素为基准，来计算运算操作的复杂度，则需要 $(2n)^{2}=4n^{2}$ 次运算

由于构成傅里叶矩阵的元素 $w$ 具有周期性，例如 $w_{2n}^{2}=w_{n}$ ，所以高阶的傅里叶矩阵可以分解为更低阶的傅里叶矩阵，简化傅立叶变换的运算步骤

F_{2n}= \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{n} & 0 \\ 0 & F_{n} \end{bmatrix} P

其中 $I$ 是单位矩阵， $D$ 是对角矩阵， $P$ 是置换矩阵， $F_{n}$ 是更低阶的傅里叶矩阵

D= \begin{bmatrix} 1 & 0 & 0 & \dots & 0 \\ 0 & w & 0 & \dots & 0 \\ 0 & 0 & w^{2} & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & w^{n-1} \end{bmatrix}

对角矩阵 $D$ 的维度是 $n \times n$ ，对角线上的元素是由 $w$ 及其高次幂构成

P= \begin{bmatrix} {\color{Red}1 } & 0 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & {\color{Red}1 } & 0 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dots & {\color{Red}1 } & 0 \\ 0 & {\color{Blue}1 } & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & {\color{Blue}1 } & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & 0 & 0 & {\color{Blue}1 } \end{bmatrix}

置换矩阵 $P$ 的维度是 $2n \times 2n$ ，当它与向量 $x$ 相乘时，其的作用（对于矩阵而言就是行交互）对向量的元素进行「重排序」，根据矩阵 $P$ 的元素的排布规律，可知它会将向量 $x$ 的偶数位置的元素（索引值从 $0$ 开始） $x_{0}, x_{2}, x_{4}, \dots$ 提到前面，然后才是奇数位置的元素

傅里叶矩阵 $f_{2n}$ 通过以上分解，傅里叶变换就变成了计算两个 $F_{n}$ 与向量相乘，可以简化运算步骤，从原来的 $(2n)^{2}$ 降低到 $2 \times n^{2}$ ，再算上「修正」矩阵与向量相乘的步骤（其中置换矩阵 $P$ 的运算十分简单，只是对原向量的元素进行重排序，主要的运算消耗是与 $D$ 相乘，但是由于 $D$ 是对称矩阵，它除了对角线上其他位置的元素都是零，所以运算也是相对简单的）

而对于 $F_{n}$ 可以使用同样的方法进行分解，以降低运算量，依此类推，可以将 $F_{2n}$ 所对应的运算复杂度 $(2n)^{2}$ 降低到 $\frac{1}{2}n\log_2(n)$

以上通过将傅里叶矩阵进行分解而降低运算复杂度的算法/步骤，称为快速傅里叶变换 Fast Fourier Transform，简称为 FFT