Linear Algebra-酉矩阵与快速FFT-27

一、知识概要

之前我们提及过复数矩阵，但并未对其运算与性质展开讨论。本节将介绍复数矩阵的运算等特征，并着重讲解一个重要的复数矩阵——傅里叶矩阵。同时，重点介绍快速傅里叶变换，它能够显著减少运算量。

二、复数矩阵

我们从最基础的向量说起，如果向量中有分量是虚数，就不能再用常规公式计算长度和内积。例如向量 $\begin{bmatrix}1\\i\end{bmatrix}$ ，按照以往的计算方式会得到： $\begin{bmatrix}1 & i\end{bmatrix}\begin{bmatrix}1\\i\end{bmatrix}=1\times1 + i\times i = 1 - 1 = 0$ ，这样计算出的长度为 0，但实际上该向量模长为 $\sqrt{1^2 + |i|^2}=\sqrt{1 + 1}=\sqrt{2}$ ，这就产生了矛盾。所以，这里给出复向量的长度与内积计算方法。

对于复数向量，向量长度计算公式为 $|z|^{2}=z^{H}z=\overline{z}^{T}z$ ，同样，复数向量的内积变为 $y^{H}x=\overline{y}^{T}x$ 。

接着讨论对称阵，在实矩阵中，若 $A^{T}=A$ ，则 $A$ 为对称阵。但在复矩阵中，这个定义不再适用。结合上面向量内积的处理方法，我们发现复矩阵中取共轭与取转置常常同时进行。所以，复对称矩阵定义为：若 $\overline{A}^{T}=A$ ，则 $A$ 为对称阵。

例如矩阵 $\begin{bmatrix}2 & 3 + i\\3 - i & 5\end{bmatrix}$ ，主对角线上的元素是实数，沿主对角线对称的两个元素共轭，这样的矩阵我们称为埃尔米特矩阵，即 $A^{H}=A$ 。埃尔米特矩阵的特征值都是实数，且特征向量正交。

同理，将特征向量正交的概念推广到复矩阵中，若一组向量 $q_{1}, q_{2} \cdots \cdots q_{n}$ 满足 $\overline{q}_{i}^{T}q_{j}=\begin{cases}0 & (i\neq j) \\ 1 & (i = j)\end{cases}$ ，它们就是一组标准正交基。由这组标准正交基可以构成一个矩阵 $Q$ ， $Q=\begin{bmatrix}q_{1} & q_{2} & q_{3} & \cdots & q_{n}\end{bmatrix}$ （ $q$ 是列向量）。

此时有 $Q^{T}Q = I = Q^{H}Q$ （前一部分是之前的写法，后一部分是类比得出的写法），这样的矩阵 $Q$ 称为酉矩阵。

三、傅里叶矩阵与快速傅里叶变换

3.1 傅里叶矩阵

傅里叶矩阵 $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}$

其中 $w^{n}=1$ ， $w = e^{i\frac{2\pi}{n}}=\cos(\frac{2\pi}{n}) + i\sin(\frac{2\pi}{n})$ 。

计算时建议使用 $e^{i\frac{2\pi}{n}}$ 的形式，而不是 $a + bi$ 的形式。在复数坐标系中， $w = e^{i\frac{2\pi}{n}}$ 表示在单位圆上， $n$ 表示将这个圆等分成 $n$ 部分，对应的点分别为 $w$ ， $w^{2}$ ， $w^{3}$ ， $\cdots$ ， $w^{n - 1}$ 。

假设 $w = e^{i\frac{2\pi}{4}} = i$ ，则对应的四阶傅里叶矩阵 $F_{4}$ 为：

$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix}$

该矩阵的列向量均正交，其逆矩阵满足 $F_{4}^{H}F_{4}=4I$ 。将 $F_{4}$ 前乘 $\frac{1}{2}$ 作为新的 $F_{4}'$ ，则新 $F_{4}'$ 的逆矩阵即为 $F_{4}^{\prime H}$ 。

3.2 快速傅里叶变换

快速傅里叶变换的核心在于傅里叶矩阵之间存在关联，以 $F_{64}$ 与 $F_{32}$ 为例：

直接代入公式 $w = e^{i\frac{2\pi}{n}}$ 可得， $F_{32}$ 中的 $w_{32}$ =(w_{64})^{2}$$ 。

构造矩阵转换公式：

$[F_{64}]=\begin{bmatrix}I & D \\ I & -D\end{bmatrix}\begin{bmatrix}F_{32} & 0 \\ 0 & F_{32}\end{bmatrix}[P]$

下面解释这个式子，其中置换矩阵 $P$ 的作用是将奇偶行分开，目的是减小计算量；而前面的 $D$ 代表对角矩阵。

例如在 4 维时，置换矩阵 $P=\begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$ ， $D=\begin{bmatrix}1 & & & \\ & w & & \\ & & w^{2} & \\ & & & w^{3}\end{bmatrix}$ ，矩阵 $\begin{bmatrix}I & D \\ I & -D\end{bmatrix}$ 的作用是将 $F_{32}$ 转化为 $F_{64}$ 。

用傅里叶矩阵乘以一个列向量，原本计算 $[F_{64}]$ 时，因为它有 64 个元素，所以需要 $64×64$ 次运算才能得到结果。而经过快速傅里叶变换，计算量变为 $2×32×32 + 32$ 次。其中 $2×32×32$ 是两个 $F_{32}$ 的运算量， $+ 32$ 是修正项的计算量，修正项的计算量来自于 $\begin{bmatrix}I & D \\ I & -D\end{bmatrix}$ 中的32阶对角矩阵 $D$ 的运算。虽然从矩阵形式上看应该计算两次 $D$ ，但两次运算只是符号相反，具体值只需计算一次，两个位置上的结果改变符号即可。

如果继续这样分解下去，计算量会变为 $2×(2×16×16 + 16)+32$ 次，原因和从 $F_{32}$ 到 $F_{64}$ 的变化一样。一共进行 $\log_{2}64$ 次分解，最后只剩下修正项的运算， $F$ 变为 $I$ 。所以最后的运算量变为 $\frac{64}{2}\log_{2}64$ 。推广到 $n$ 阶，快速傅里叶变换的运算量为 $\frac{n}{2}\log_{2}n$ 。与原本的 $n^2$ 次运算量相比，运算量减少显著。

3.3 验证用的 Matlab 代码

% 计算傅里叶矩阵
% 计算F64
n = 64;
w = exp(1j*2*pi/n);
F64 = zeros(n);
for i = 1:n
    for j = 1:n
        F64(i,j) = w^((i - 1)*(j - 1));
    end
end

% 计算F32
m = 32;
w32 = exp(1j*2*pi/m);
F32 = zeros(m);
for i = 1:m
    for j = 1:m
        F32(i,j) = w32^((i - 1)*(j - 1));
    end
end

% 构造置换矩阵P
P = eye(n);
P = P([1:2:n, 2:2:n], :);

% 构造对角矩阵D
D = diag(w.^(0:m - 1));

% 计算等式右边的矩阵
right_hand_side = [eye(m), D; eye(m), -D]*[F32, zeros(m); zeros(m), F32]*P;

% 验证等式是否成立
error_norm = norm(F64 - right_hand_side);
if error_norm < 1e-10
    disp('理论验证通过，两个矩阵在数值上相等。');
else
    disp('理论验证未通过，两个矩阵在数值上不相等。');
end

三、学习感悟

本节主要研究了复矩阵、复向量的计算以及性质，拓展了向量内积和向量长度的计算方法，还探讨了一种特殊的复矩阵——傅里叶矩阵。最后讲解了本章重点内容快速傅里叶变换，这部分是难点，尤其是对 $[F_{64}]=\begin{bmatrix}I & D \\ I & -D\end{bmatrix}\begin{bmatrix}F_{32} & 0 \\ 0 & F_{32}\end{bmatrix}[P]$ 这一转换的理解有一定难度。个人理解是转换矩阵 $P$ 将向量的奇偶行分离，从而减小计算量，而 $\begin{bmatrix}I & D \\ I & -D\end{bmatrix}$ 的作用是实现两个傅里叶矩阵 $F$ 之间的转换。快速傅里叶变换（FFT）非常重要，其应用较为复杂，想要彻底理解还需要进一步深入学习这部分知识。