前言
本系列是科大25年秋课程《人工智能的数理科学基础》同步笔记。本文为第一章线性代数、微积分与优化的第二部分：矩阵分解相关内容。
系列文章
1、特征值分解 (Eigendecomposition)
设方阵 $\boldsymbol A\in \mathbb R^{n\times n}$。如果存在 $\lambda \in \mathbb C$ 和某个非零向量 $\boldsymbol v\in \mathbb C^n$ 使得：
$$ \boldsymbol{Av} = \lambda \boldsymbol{v} $$
那么 $(\lambda \boldsymbol{I} - \boldsymbol{A})\boldsymbol{v} = 0$，即矩阵 $\lambda \boldsymbol{I} - \boldsymbol{A}$ 不满秩。因此，$\lambda$ 的值可以通过求解以下特征方程得到：
$$ p_A(\lambda) = \det(\lambda \boldsymbol{I} - \boldsymbol{A}) = 0 $$
其中 $p_A(\lambda)$ 被称为矩阵 $\boldsymbol A$ 的特征多项式 (characteristic polynomial)。该多项式的根 $\lambda$ 被称为矩阵 $\boldsymbol A$ 的特征值 (eigenvalue)，对应的向量 $\boldsymbol v$ 被称为特征向量 (eigenvector)。也即：
$$ p_A(\lambda)=\prod_{i=1}^n (\lambda-\lambda_i)=\lambda^n-(\lambda_1+\cdots+\lambda_n)\lambda^{n-1}+\cdots $$
特征多项式的一些性质：
- $\boldsymbol A$ 和 $\boldsymbol A^\top$ 拥有相同的特征值。
- 所有特征值之和等于矩阵的迹：$\sum_{i=1}^n \lambda_i = \text{Tr}(\boldsymbol{A})$。
- 所有特征值之积等于矩阵的行列式：$\prod_{i=1}^n \lambda_i = \det(\boldsymbol{A})$。
- Cayley-Hamilton 定理：$p_A(\boldsymbol A) = \boldsymbol 0$。
此外对于$\boldsymbol A$的幂，有$\boldsymbol A^k \boldsymbol v_j=\boldsymbol A^{k-1}( \boldsymbol A\boldsymbol v_j)=\lambda_j\boldsymbol A^{k-1}\boldsymbol v_j=\lambda^k_j\boldsymbol v_j$。因此$\boldsymbol A^k$的特征值为$\lambda_1^k,\cdots,\lambda_n^k$，其同样对应特征向量$\boldsymbol v_1,\cdots,\boldsymbol v_n$。
若矩阵 $\boldsymbol A$ 有 $n$ 个线性无关的特征向量${\boldsymbol v_1, \dots, \boldsymbol v_n}$，对应特征值${\lambda_1, \dots, \lambda_n}$，我们可以将所有特征方程写成一个矩阵形式：
$$ \boldsymbol{AV} = \boldsymbol{V\Lambda} $$
其中 $\boldsymbol V = [\boldsymbol v_1, \dots, \boldsymbol v_n]$ 是特征向量组成的矩阵，$\boldsymbol \Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)$ 是特征值组成的对角矩阵。这就是特征值分解 (Eigendecomposition)，也可以写作 $\boldsymbol A = \boldsymbol{V\Lambda V^{-1}}$。显然地，对于$\boldsymbol A$的幂同样有特征值分解：
$$ \boldsymbol A^k=\boldsymbol V \boldsymbol \Lambda^k\boldsymbol V^{-1} $$
定义矩阵 $\boldsymbol A$ 的谱半径 (spectral radius) 为：
$$ \rho(\boldsymbol A) = \max_i |\lambda_i| $$
如果 $\rho(\boldsymbol A) < 1$，那么有特征值分解可知$\lim_{k\to\infty} \boldsymbol A^k = \boldsymbol 0$，因此通过谱半径可以分析某些迭代过程的收敛性。
2、实对称矩阵 (Real Symmetric Matrices)
实对称矩阵（$\boldsymbol A = \boldsymbol A^\top$）具有以下重要性质：
- 特征值为实数。（$(\boldsymbol A\boldsymbol v)\cdot(\boldsymbol A\boldsymbol v)=\lambda^2\boldsymbol v\cdot\boldsymbol v$）
- 不同特征值对应的特征向量是正交的。（$\boldsymbol v_{2}^\top \boldsymbol A \boldsymbol v_{1}=\lambda_{1} \boldsymbol v_{2}^\top \boldsymbol v_{1}=\lambda_{2} \boldsymbol v_{2}^\top \boldsymbol v_{1} \quad \Rightarrow \quad \boldsymbol v_{2}^\top \boldsymbol v_{1}=\boldsymbol 0$）
根据这些性质，实对称矩阵的特征向量可以被选择为一组标准正交基。因此，由特征向量组成的矩阵 $\boldsymbol V$ 是一个标准正交矩阵，即 $\boldsymbol V\boldsymbol V^\top = \boldsymbol I$，或 $\boldsymbol V^{-1} = \boldsymbol V^\top$。此时，特征值分解可以写成：
$$ \boldsymbol A = \boldsymbol{V\Lambda V^\top} = \sum_{i=1}^n \lambda_i \boldsymbol v_i \boldsymbol v_i^\top $$
对于二次型 $\boldsymbol w^\top \boldsymbol{Aw}$，如果一个实对称矩阵 $\boldsymbol A$ 的所有特征值都大于 0 ($\lambda_i > 0$)，则称其为对称正定 (symmetric positive definite)，此时 $\boldsymbol w^\top \boldsymbol{Aw} > 0$（除非 $\boldsymbol w=0$）。如果所有特征值大于等于 0 ($\lambda_i \ge 0$)，则称其为对称半正定 (symmetric positive semi-definite)，此时 $\boldsymbol w^\top \boldsymbol{Aw} \ge 0$。容易知道，对于任意实矩阵$\boldsymbol A$，$\boldsymbol A^\top\boldsymbol{A}$一定为方阵且对称半正定。
3、Householder 变换与 QR 分解
Householder 变换是一种线性变换，它将一个向量 $\boldsymbol x$ 反射过一个由单位向量 $\boldsymbol u$ 定义的超平面。其几何意义在于找到一个合适的镜面，将一个向量反射到另一个具有相同长度的向量。具体而言，我们考虑$n$维空间中关于平面
$$ \boldsymbol u^\top\boldsymbol x=0,\boldsymbol u\in \mathbb R^n $$
的镜面反射$\mathcal P:x\to \mathcal P(x)$，其满足：
- $\mathcal P(\boldsymbol x)-\boldsymbol x$垂直于平面，即$\exists t\in \mathbb R,\mathcal P(\boldsymbol x)-\boldsymbol x=t\boldsymbol u$。
- 点$\frac 12 (\mathcal P(\boldsymbol x)+\boldsymbol x)$在平面上，即$\frac 12\boldsymbol u^\top(\mathcal P(\boldsymbol x)+\boldsymbol x)=0$。
容易解出$t=-2\boldsymbol u^\top\boldsymbol x$与$\mathcal P(\boldsymbol x) $。该变换的矩阵形式，即 Householder 矩阵，定义为：
$$ \boldsymbol P = \boldsymbol I - 2\boldsymbol u\boldsymbol u^\top $$
其中 $\boldsymbol u$ 是一个单位向量。Householder 矩阵是实对称矩阵（$\boldsymbol P = \boldsymbol P^\top$），并且是它自身的逆（$\boldsymbol P^2 = \boldsymbol I$），这反映了“反射两次等于没有反射”的直观几何性质。同时可以看出Householder变换不会改变原向量的模长，这也可以从反射的几何性质理解。
QR 分解正是利用 Householder 变换来实现的。其目标是将一个矩阵 $\boldsymbol A \in \mathbb R^{m\times n}$ 分解为一个单位正交矩阵 $\boldsymbol Q \in \mathbb R^{m\times m}$ （$\boldsymbol Q\boldsymbol Q^\top=\boldsymbol I$）和一个上三角矩阵 $\boldsymbol R \in \mathbb R^{m\times n}$ （满足$r_{ij}=0,\forall i>j$）的乘积：
$$ \boldsymbol A = \boldsymbol{QR} $$
该过程通过一系列 Householder 变换逐步将 $\boldsymbol A$ 矩阵的列向量转换为上三角形式，核心思想就是构造一系列的 Householder 矩阵 $\boldsymbol{P}_1, \boldsymbol{P}_2, \cdots$依次作用于 $\boldsymbol{A}$，每一步都在一个新的列中引入所需的零。
算法步骤如下：
第一步：构造第一个 Householder 矩阵 $\boldsymbol P_1$，用于将 $\boldsymbol A$ 的第一列向量 $\boldsymbol a_1$ 变换为 $\alpha_1 \boldsymbol e_1$，其中 $\boldsymbol{e}_1 =
[1, 0, \ldots, 0]^\top$ 是标准基向量。$$ \boldsymbol P_1 \boldsymbol A = \begin{bmatrix} \alpha_1 & \dots \\ 0 & \\ \vdots & \boldsymbol A' \\ 0 & \end{bmatrix} $$
其中 $\alpha_1 = \pm \|\boldsymbol a_1\|_2$。此时我们构造：$\boldsymbol u_1=\boldsymbol a_1\pm\|\boldsymbol a_1\|_2\boldsymbol e_1$，则：
$$ \boldsymbol P_1 = \boldsymbol I - 2\frac{\boldsymbol u_1 \boldsymbol u_1^\top}{\|\boldsymbol u_1\|_2^2} $$
第二步：对子矩阵 $\boldsymbol A'$ 重复此过程。构造一个更小的 Householder 矩阵 $\hat{\boldsymbol P_2}$，然后将其扩展为与 $\boldsymbol A$ 同维度的矩阵 $\boldsymbol P_2$：
$$ \boldsymbol P_2 = \begin{bmatrix} 1 & \boldsymbol 0 \\ \boldsymbol 0 & \hat{\boldsymbol P_2} \end{bmatrix} $$
左乘 $\boldsymbol P_2$ 不会改变第一行和第一列已经处理好的部分。
$$ \boldsymbol P_2 \boldsymbol P_1 \boldsymbol A = \begin{bmatrix} \alpha_1 & \dots & \dots \\ 0 & \alpha_2 & \dots \\ \vdots & 0 & \\ 0 & \vdots & \boldsymbol A'' \end{bmatrix} $$
迭代：重复此过程 $k = \min(m, n)$ 次，得到：
$$ \boldsymbol P_k \cdots \boldsymbol P_2 \boldsymbol P_1 \boldsymbol A = \boldsymbol R $$
其中 $\boldsymbol R$ 是一个上三角矩阵。
构造 Q：由于每个 $\boldsymbol P_i$ 都是标准正交矩阵，它们的乘积也是。因此：
$$ \boldsymbol A = (\boldsymbol P_1 \boldsymbol P_2 \cdots \boldsymbol P_k) \boldsymbol R $$
令 $\boldsymbol Q = \boldsymbol P_1 \boldsymbol P_2 \cdots \boldsymbol P_k$（因为 $\boldsymbol P_i^{-1} = \boldsymbol P_i$），我们就得到了最终的 QR 分解。在实际计算中，我们通常存储向量 $\boldsymbol u_i$ 而非完整的矩阵 $\boldsymbol P_i$，这大大降低了存储需求。
4、奇异值分解 (SVD)
对于任意矩阵 $\boldsymbol A \in \mathbb R^{m\times n}$（不一定是方阵），其奇异值分解 (Singular Value Decomposition, SVD) 定义为：
$$ \boldsymbol A = \boldsymbol{U\Sigma V^\top} $$
其中：
- $\boldsymbol U \in \mathbb R^{m\times m}$ 是一个标准正交矩阵，其列向量称为左奇异向量。
- $\boldsymbol V \in \mathbb R^{n\times n}$ 是一个标准正交矩阵，其列向量称为右奇异向量。
- $\boldsymbol \Sigma \in \mathbb R^{m\times n}$ 是一个矩形对角矩阵，其对角线上的元素 $\sigma_i$ 称为奇异值，且满足 $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$（$r=\text{rank}(\boldsymbol A)$）。
奇异值是矩阵 $\boldsymbol A^\top \boldsymbol A$ 的特征值的平方根。SVD 分解揭示了矩阵的内在几何结构，并且在数据降维、推荐系统等领域有广泛应用。
矩阵的 2-范数 定义为：
$$ \|\boldsymbol A\|_2 = \sup_{\boldsymbol x \neq 0} \frac{\|\boldsymbol{Ax}\|_2}{\|\boldsymbol x\|_2} $$
通过 SVD，可以证明 $\|\boldsymbol A\|_2 = \sigma_1$，即矩阵二范数为最大的奇异值。具体而言考察$\max_{\|\boldsymbol x\|_2=1} \|\boldsymbol A\boldsymbol x\|_2$。代入SVD，有：
$$ \|\boldsymbol A\boldsymbol x\|_2=\|\boldsymbol U(\boldsymbol\Sigma\boldsymbol V^{\top}\boldsymbol x)\|_2 $$
由于正交矩阵变换不改变向量模长：$\|\boldsymbol Q\boldsymbol x\|_2=\|\boldsymbol x\|_2$，则$\|\boldsymbol A\boldsymbol x\|_2=\|\boldsymbol\Sigma\boldsymbol V^{\top}\boldsymbol x\|_2$。定义$\boldsymbol z=\boldsymbol V^{\top}\boldsymbol x $，同样有：$\|\boldsymbol z \|_2=\|\boldsymbol x\|_2=1$，所以$\max_{\|\boldsymbol x\|_2=1} \|\boldsymbol A\boldsymbol x\|_2$等价与考察$\max_{\|\boldsymbol z\|_2=1} \|\boldsymbol \Sigma\boldsymbol z\|_2$。设$\boldsymbol z=[z_1,\cdots,z_n]^\top,\sum_{i=1}^nz_i=1$，则
$$ \|\boldsymbol \Sigma\boldsymbol z\|_2^2=\sum_{i=1}^n\sigma_i^2z_i^2\leq \sigma_1^2 $$
而另一方面，如果取$\boldsymbol z=[1,0\cdots,0]^\top=\boldsymbol e_1$，显然地此时$\|\boldsymbol \Sigma\boldsymbol z\|_2=\sigma_1 $，因此$\|\boldsymbol A\|_2 = \sigma_1$。
5、Homework
- 设实矩阵 $\boldsymbol R$ 满足 $\boldsymbol R^\top \boldsymbol R = \boldsymbol I$。证明 $\boldsymbol R$ 的实特征值必定是 -1 或 +1 之一。
- 通过计算矩阵 $\boldsymbol A$ 的特征多项式 $p_A$ 在 0 处的值，证明 $\lambda_1 \cdots \lambda_n = \det \boldsymbol A$。
- 设 $\boldsymbol P = \boldsymbol I - 2\boldsymbol u\boldsymbol u^\top$ 是 Householder 矩阵。查阅 Sherman-Morrison 公式，证明 $\det(\boldsymbol P) = -1$。
- 设矩阵 $\boldsymbol A \in \mathbb R^{m\times n}$，$\boldsymbol Q \in \mathbb R^{m\times m}$ 和 $\boldsymbol P \in \mathbb R^{n\times n}$ 是单位正交矩阵，证明 $\|\boldsymbol{QA}\|_2 = \|\boldsymbol{AP}\|_2 = \|\boldsymbol{A}\|_2$。
