线性代数学习笔记8-1：复数矩阵与共轭转置、Hermite矩阵、酉矩阵、傅里叶矩阵和快速傅里叶变换FFT

即使是实矩阵，也可能有复特征值，因此矩阵运算中无法避免的会碰到复数

这里我们先特别关注复数矩阵的情况，并明确如何处理复矩阵，而在后续学习中一般只研究实矩阵，可以将其推广到复数情况

复向量的内积和共轭转置

对于复向量x=[x1x2⋮xn]∈Cn\mathbf{x}=\left[\begin{array}{c}x_{1} \\x_{2} \\\vdots \\x_{\mathrm{n}}\end{array}\right] \in \mathbf{C}^{n}x=⎣⎡​x1​x2​⋮xn​​⎦⎤​∈Cn，其中每个分量都是复数

在实数情况下，我们学习过，xTx{\mathbf{x}}^{T} \mathbf{x}xTx表示x\mathbf{x}x与自己的内积/点积，结果是一个正实数（向量x\mathbf{x}x长度的平方）

复向量的模长的平方：在x\mathbf{x}x为复数情的况下不能再使用xTx{\mathbf{x}}^{T} \mathbf{x}xTx，复向量模长的平方应推广为x‾Tx\overline{\mathbf{x}}^{T} \mathbf{x}xTx，对于复向量，这是一个常见、很重要的运算

具体带入可知，x‾Tx\overline{\mathbf{x}}^{T} \mathbf{x}xTx的结果必然为非负实数（仅当x=0\mathbf{x}=\mathbf 0x=0时x‾Tx=0\overline{\mathbf{x}}^{T} \mathbf{x}=0xTx=0），这符合“模长平方”的数学意义：x‾Tx=[xˉ1xˉ2xˉ3xˉ4][x1x2x3x4]=∣x1∣2+∣x2∣2+∣x3∣2+∣x4∣2\overline{\mathbf{x}}^{T} \mathbf{x}=\left[\begin{array}{llll}\bar{x}_{1} & \bar{x}_{2} & \bar{x}_{3} & \bar{x}_{4}\end{array}\right]\left[\begin{array}{l}x_{1} \\ x_{2} \\ x_{3} \\ x_{4}\end{array}\right]=\left|x_{1}\right|^{2}+\left|x_{2}\right|^{2}+\left|x_{3}\right|^{2}+\left|x_{4}\right|^{2}xTx=[xˉ1​​xˉ2​​xˉ3​​xˉ4​​]⎣⎡​x1​x2​x3​x4​​⎦⎤​=∣x1​∣2+∣x2​∣2+∣x3​∣2+∣x4​∣2其中，对于复数xix_ixi​，xˉixi=∣xi∣2\bar{x}_{i}x_i=\left|x_{i}\right|^{2}xˉi​xi​=∣xi​∣2（由于(a+ib)(a−ib)=a2+b2(a+ib)(a-ib)=a^2+b^2(a+ib)(a−ib)=a2+b2），可见，结果的每一项都是非负实数

例如，我们认为复向量[1i]\left[\begin{array}{c}1 \\i\end{array}\right][1i​]模长的平方为2，因为[1−i][1i]=2\left[\begin{array}{ll}1 & -i\end{array}\right]\left[\begin{array}{c}1 \\i\end{array}\right]=2[1​−i​][1i​]=2

一般的，复向量的内积运算为yHx\mathbf{y}^{H} \mathbf{x}yHx：yHx=y‾Tx=yˉ1x1+yˉ2x2+⋯+yˉnxn\mathbf{y}^{H} \mathbf{x}=\overline{\mathbf{y}}^{T} \mathbf{x}=\bar{y}_{1} x_{1}+\bar{y}_{2} x_{2}+\cdots+\bar{y}_{n} x_{n}yHx=y​Tx=yˉ​1​x1​+yˉ​2​x2​+⋯+yˉ​n​xn​

若yHx=0\mathbf{y}^{H} \mathbf{x}=0yHx=0，说明两个复向量互相垂直/正交

可见，实数情况下的转置xT\mathbf{x}^{T}xT，在复数情况下推广为共轭转置x‾T=xH\overline{\mathbf{x}}^{T}=\mathbf{x}^{H}xT=xH，也称为Hermite转置

复数矩阵 与 共轭转置（Hermite转置）

由上，矩阵的转置运算AT\mathbf A^TAT，在复空间中推广为Hermite转置AH\mathbf A^HAH

Hermite矩阵：AH=AˉT\mathbf A^H=\mathbf{\bar A}^TAH=AˉT

共轭转置（Hermite转置）的运算性质：

(AH)H=A(\mathbf A^H)^H=\mathbf A(AH)H=A(A+B)H=AH+BH(\mathbf A+\mathbf B)^H=\mathbf A^H+\mathbf B^H(A+B)H=AH+BH(AB)H=BHAH(\mathbf A\mathbf B)^H=\mathbf B^H\mathbf A^H(AB)H=BHAH(A−1)H=(AH)−1(\mathbf A^{-1})^H=(\mathbf A^H)^{-1}(A−1)H=(AH)−1(kA)H=kˉAH(k\mathbf A)^H=\bar{k}\mathbf A^H(kA)H=kˉAH

一般而言，从n维实空间Rn\mathbf{R}^{n}Rn，推广到n维复空间Cn\mathbf{C}^{n}Cn，将各个转置运算换为Hermite转置即可，如：

Hermitian矩阵

对称矩阵，实数下为A=AT\mathbf A=\mathbf A^TA=AT，复数下为A=AH\mathbf A=\mathbf A^HA=AH，称为Hermitian矩阵

酉矩阵

正交矩阵，实数下为QTQ=I\mathbf Q^T\mathbf Q=\mathbf IQTQ=I，复数下为QHQ=I\mathbf Q^H\mathbf Q=\mathbf IQHQ=I，称为酉矩阵（unitary matrix）

酉矩阵的列向量都是复向量，且构成复空间中的标准正交向量组，满足q‾jTqk={0j≠k1j=k\overline{\mathbf{q}}_{j}^{T} \mathbf{q}_{k}=\left\{\begin{array}{ll}

0 & j \neq k \\1 & j=k\end{array}\right.q​jT​qk​={01​j=kj=k​

傅里叶矩阵

使用傅里叶矩阵，可以实现离散傅里叶变换DFT

离散傅里叶变换DFT：X[k]=∑n=0N−1x[n]e−j2πNknX[k]= \sum_{n=0}^{N-1} x[n] \mathrm{e}^{-\mathrm{j} \frac{2 \pi}{N} k n}X[k]=∑n=0N−1​x[n]e−jN2π​kn

离散傅里叶逆变换IDFT：x[n]=1N∑k=0N−1x[n]ej2πNknx[n]=\frac{1}{N}\sum_{k=0}^{N-1} x[n] \mathrm{e}^{\mathrm{j} \frac{2 \pi}{N} k n}x[n]=N1​∑k=0N−1​x[n]ejN2π​kn

长度为nnn的离散向量xn\boldsymbol x_nxn​:

做离散傅里叶变换DFT：Fnxn\boldsymbol{F}_{n}\boldsymbol x_nFn​xn​；（结果是n×1n\times 1n×1的列向量，第kkk行来自于Fn\boldsymbol{F}_{n}Fn​的第kkk行与xn\boldsymbol x_nxn​相乘）做离散傅里叶逆变换IDFT：Fn−1xn\boldsymbol{F}_{n}^{-1}\boldsymbol x_nFn−1​xn​

根据DFT和IDFT定义式，提取基本元素ω=ej2π/n\omega=e^{j 2 \pi / n}ω=ej2π/n，从而得到n阶傅里叶矩阵Fn\boldsymbol{F}_{n}Fn​：

Fn=[111⋯11ωω2ω(n−1)1ω2ω4ω2(n−1)⋮⋱1ωn−1ω2(n−1)ω(n−1)2]\boldsymbol{F}_{n}=\left[\begin{array}{rrrrr}

1 & 1 & 1 & \cdots & 1 \\

1 & \omega & \omega^{2} & & \omega^{(n-1)} \\

1 & \omega^{2} & \omega^{4} & & \omega^{2(n-1)} \\

\vdots & & & \ddots & \\

1 & \omega^{n-1} & \omega^{2(n-1)} & & \omega^{(n-1)^{2}}\end{array}\right]Fn​=⎣⎡​111⋮1​1ωω2ωn−1​1ω2ω4ω2(n−1)​⋯⋱​1ω(n−1)ω2(n−1)ω(n−1)2​⎦⎤​其中，基本元素ω=ej2π/n\omega=e^{j 2 \pi / n}ω=ej2π/n的特点在于：

ω=ej2π/n\omega=e^{j 2 \pi / n}ω=ej2π/n是复元素，但模长为1，因此其幂次方仅对应于单位圆上的旋转；并且ω=ej2π/n\omega=e^{j 2 \pi / n}ω=ej2π/n的相角，就是将一整圈单位圆（2π2\pi2π）划分为nnn份得到的，从而ωn=1\omega^{n}=1ωn=1

傅里叶矩阵的性质

注意，n阶傅里叶矩阵Fn\boldsymbol{F}_{n}Fn​满足：

矩阵元素通项公式：(Fn)ij=ω(i−1)(j−1)=(ej2π/n)(i−1)(j−1)\left(\boldsymbol{F}_{n}\right)_{ij}=\omega^{(i-1)(j-1)}=(e^{j 2 \pi / n})^{(i-1)(j-1)}(Fn​)ij​=ω(i−1)(j−1)=(ej2π/n)(i−1)(j−1)，即第iii行第jjj列元素的指数，由(i−1)(j−1)(i-1)(j-1)(i−1)(j−1)相乘得到（i,j∈[1,n]i,j\in[1,n]i,j∈[1,n]）有一定的对称性（满足Fn=FnT\boldsymbol{F}_{n}=\boldsymbol{F}_{n}^{T}Fn​=FnT​），但并不是Hermitian矩阵（复空间下不能算是对称矩阵，因为不满足A=AH\boldsymbol{A}=\boldsymbol{A}^{H}A=AH）傅里叶矩阵，各个列向量正交，但不是酉矩阵（列向量模长为N\sqrt{N}N​）（复空间下不是“列向量标准正交”的正交矩阵）

好处：列向量正交，可以将傅里叶矩阵分解为一系列稀疏矩阵（含有大量零元素），从而可以轻易做乘法、求逆由上，各列向量正交但模长为N\sqrt{N}N​，整个矩阵除以N\sqrt{N}N​可以得到酉矩阵1NFn\frac{1}{\sqrt{N}}\boldsymbol{F}_{n}N​1​Fn​（正交矩阵在复空间下的推广，列向量为复向量且标准正交）推论：Fn−1=1NFnHF_n^{-1}=\frac{1}{N} F_n^{H}Fn−1​=N1​FnH​，或者说1NFnHFn=I\frac{1}{N} \boldsymbol{F}_{n}{ }^{H} \boldsymbol{F}_{n}=\boldsymbol{I}N1​Fn​HFn​=I

证明：根据上面，1NFn\frac{1}{\sqrt{N}}\boldsymbol{F}_{n}N​1​Fn​为酉矩阵，其逆矩阵为(1NFn)−1=(1NFn)H=1NFnH\left(\frac{1}{\sqrt{N}} F_n\right)^{-1}=\left(\frac{1}{\sqrt{N}} F_n\right)^{H}=\frac{1}{\sqrt{N}} F_n^{H}(N​1​Fn​)−1=(N​1​Fn​)H=N​1​FnH​

两步同乘以1N\frac{1}{\sqrt{N}}N​1​，即可得到Fn−1=1NFnHF_n^{-1}=\frac{1}{N} F_n^{H}Fn−1​=N1​FnH​，证毕

（ps. 这就是为什么DFT有系数1N\frac{1}{N}N1​）

例如，对于F4=[11111ej(π2)ej(π2)2ej(π2)31ej(π2)2ej(π2)2∗2ej(π2)2∗31ej(π2)3ej(π2)3∗2ej(π2)3∗3]=[11111ii2i31i2i4i61i3i6i9]=[11111i−1−i1−11−11−i−1i]\boldsymbol{F}_{4}=\left[\begin{array}{cccc}

1 & 1 & 1 & 1 \\

1 & e^{j\left(\frac{\pi}{2}\right)} & e^{j\left(\frac{\pi}{2}\right) 2} & e^{j\left(\frac{\pi}{2}\right) 3} \\

1 & e^{j\left(\frac{\pi}{2}\right) 2} & e^{j\left(\frac{\pi}{2}\right) 2 * 2} & e^{j\left(\frac{\pi}{2}\right) 2 * 3} \\

1 & e^{j\left(\frac{\pi}{2}\right) 3} & e^{j\left(\frac{\pi}{2}\right) 3 * 2} & e^{j\left(\frac{\pi}{2}\right) 3 * 3}

\end{array}\right]=\left[\begin{array}{cccc}

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}{rrrr}1 & 1 & 1 & 1 \\1 & i & -1 & -i \\1 & -1 & 1 & -1 \\1 & -i & -1 & i\end{array}\right]F4​=⎣⎡​1111​1ej(2π​)ej(2π​)2ej(2π​)3​1ej(2π​)2ej(2π​)2∗2ej(2π​)3∗2​1ej(2π​)3ej(2π​)2∗3ej(2π​)3∗3​⎦⎤​=⎣⎡​1111​1ii2i3​1i2i4i6​1i3i6i9​⎦⎤​=⎣⎡​1111​1i−1−i​1−11−1​1−i−1i​⎦⎤​各个列向量正交（内积xiˉTxj=0\bar{\boldsymbol x_i}^T\boldsymbol x_j=0xi​ˉ​Txj​=0），但列向量的模长平方xiˉTxi=4\bar{\boldsymbol x_i}^T\boldsymbol x_i=4xi​ˉ​Txi​=4

因此，可以修正得到一个酉矩阵：12F4=12[11111i−1−i1−11−11−i−1i]\frac{1}{2}\boldsymbol{F}_{4}=\frac{1}{2}\left[\begin{array}{rrrr}1 & 1 & 1 & 1 \\1 & i & -1 & -i \\1 & -1 & 1 & -1 \\1 & -i & -1 & i\end{array}\right]21​F4​=21​⎣⎡​1111​1i−1−i​1−11−1​1−i−1i​⎦⎤​

酉矩阵12F4\frac{1}{2}\boldsymbol{F}_{4}21​F4​（复数下的正交矩阵）的逆矩阵：12F4H\frac{1}{2}\boldsymbol{F}_{4}^H21​F4H​（共轭转置即可）

满足14F4HF4=I\frac{1}{4} \boldsymbol{F}_{4}{ }^{H} \boldsymbol{F}_{4}=\boldsymbol{I}41​F4​HF4​=I

另外也可以验证F4\boldsymbol{F}_{4}F4​的逆矩阵：F4−1=14F4H=14[11111e−j(π2)e−j(π2)2e−j(π2)31e−j(π2)2e−j(π2)2∗2e−j(π2)2∗31e−j(π2)3e−j(π2)3∗2e−j(π2)3∗3]F_{4}^{-1}=\frac{1}{4} {F}_{4}^H=\frac{1}{4}\left[\begin{array}{cccc}

1 & 1 & 1 & 1 \\

1 & e^{-j\left(\frac{\pi}{2}\right)} & e^{-j\left(\frac{\pi}{2}\right) 2} & e^{-j\left(\frac{\pi}{2}\right) 3} \\

1 & e^{-j\left(\frac{\pi}{2}\right) 2} & e^{-j\left(\frac{\pi}{2}\right) 2 * 2} & e^{-j\left(\frac{\pi}{2}\right) 2 * 3} \\

1 & e^{-j\left(\frac{\pi}{2}\right) 3} & e^{-j\left(\frac{\pi}{2}\right) 3 * 2} & e^{-j\left(\frac{\pi}{2}\right) 3 * 3}

\end{array}\right]F4−1​=41​F4H​=41​⎣⎡​1111​1e−j(2π​)e−j(2π​)2e−j(2π​)3​1e−j(2π​)2e−j(2π​)2∗2e−j(2π​)3∗2​1e−j(2π​)3e−j(2π​)2∗3e−j(2π​)3∗3​⎦⎤​

快速傅里叶变换FFT

快速傅里叶变换FFT可以大大减少DFT的计算量，下面从矩阵角度看待这个问题

FFT中，将N=64的DFT拆为两个N=32的DFT

从矩阵角度：

傅里叶矩阵F64\boldsymbol{F}_{64}F64​和F32\boldsymbol{F}_{32}F32​的基本元素有如下关系：w642=w32w_{64}^2=w_{32}w642​=w32​，可见F64\boldsymbol{F}_{64}F64​和F32\boldsymbol{F}_{32}F32​有一定关系具体而言，[F64]=[IDI−D][F3200F32][P]\left[\boldsymbol{F}_{64}\right]=\left[\begin{array}{rr}

\boldsymbol{I} & \boldsymbol{D} \\

\boldsymbol{I} & -\boldsymbol{D}

\end{array}\right]\left[\begin{array}{rr}

\boldsymbol{F}_{32} & 0 \\

0 & \boldsymbol{F}_{32}

\end{array}\right][\boldsymbol{P}][F64​]=[II​D−D​][F32​0​0F32​​][P]其中，置换矩阵P=[1000⋯⋯00001000⋮0000⋯⋯100100⋯⋯000001⋯⋯00⋮0000⋯⋯01]\boldsymbol{P}=\left[\begin{array}{cccccccc}

1 & 0 & 0 & 0 & \cdots & \cdots & 0 & 0 \\

0 & 0 & 1 & 0 & & & 0 & 0 \\

& & & \vdots & & & & \\

0 & 0 & 0 & 0 & \cdots & \cdots & 1 & 0 \\

0 & 1 & 0 & 0 & \cdots & \cdots & 0 & 0 \\

0 & 0 & 0 & 1 & \cdots & \cdots & 0 & 0 \\

& & & \vdots & & & & \\

0 & 0 & 0 & 0 & \cdots & \cdots & 0 & 1

\end{array}\right]P=⎣⎡​100000​000100​010000​00⋮001⋮0​⋯⋯⋯⋯⋯​⋯⋯⋯⋯⋯​001000​000001​⎦⎤​，功能是将奇数次项（1,3,5）提到前面，将偶数次项（2,4,6）放到后面

对角阵D=[1ωω2⋱ω31]\boldsymbol{D}=\left[\begin{array}{ccccc}

1 & & & & \\

& \omega & & & & \\

& & \omega^{2} & & \\

& & & \ddots & \\

& & & & \omega^{31}

\end{array}\right]D=⎣⎡​1​ω​ω2​⋱​ω31​⎦⎤​计算量对比：

原来对长度为NNN的向量x\boldsymbol xx直接做DFT，则F64x\boldsymbol{F}_{64}\boldsymbol xF64​x的计算量是N×NN\times NN×N

改写为FFT后，计算量是两个F32x\boldsymbol{F}_{32}\boldsymbol xF32​x再加上一些修正项，修正项主要来自于与对角矩阵D的乘法，大约为32次；并且F32\boldsymbol{F}_{32}F32​可进一步拆为两个F16\boldsymbol{F}_{16}F16​、再拆为四个F8\boldsymbol{F}_{8}F8​…最终，所有计算来自于修正项，FFT计算量为(N/2)log2N(N/2)log_2N(N/2)log2​N