线性代数 ZoomNotes

第 7 部分：奇异值与奇异向量

7.1 $U$、$V$ 中的奇异向量与 $\Sigma$ 中的奇异值

奇异值分解 (Singular Value Decomposition, SVD) 对 每一个 矩阵 $A$（尺寸 $m \times n$，任意秩 $r$）都存在：

$$A = U \Sigma V^T$$

组成部分：

• $U$：$m \times m$ 的正交矩阵（orthogonal matrix）。其列是 左奇异向量 (left singular vectors) $u_1, \dots, u_m$（张成列空间与左零空间）
• $V$：$n \times n$ 的正交矩阵。其列是 右奇异向量 (right singular vectors) $v_1, \dots, v_n$（张成行空间与零空间）
• $\Sigma$：$m \times n$ 的对角矩阵（diagonal matrix），其对角线上为 奇异值 (singular values) $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$，其余位置为零

基本方程：

$$A v_k = \sigma_k u_k \quad \text{for } k = 1, \dots, r$$

且对 $k > r$，有 $A v_k = 0$ 以及 $A^T u_k = 0$。

---

7.2 简约 SVD / 完整 SVD / 从 $A^T A$ 构造 $U\Sigma V^T$

完整 SVD (Full SVD)： $A = U_{m \times m} \Sigma_{m \times n} V_{n \times n}^T$

简约（经济型）SVD (Reduced/Economy SVD)： $A = U_r \Sigma_r V_r^T$，其中：

• $U_r$ 尺寸为 $m \times r$（仅保留对应非零奇异值的 $r$ 个左奇异向量）
• $\Sigma_r$ 尺寸为 $r \times r$ 的对角矩阵
• $V_r$ 尺寸为 $n \times r$

从 $A^T A$ 构造：

1. 计算 $A^T A$（尺寸 $n \times n$），它是对称半正定的（symmetric positive semidefinite）
2. 求其特征值 $\sigma_1^2 \geq \sigma_2^2 \geq \cdots \geq \sigma_r^2 > 0$
3. $A^T A$ 的特征向量即为 右奇异向量 $v_1, \dots, v_r$
4. 奇异值为 $\sigma_k = \sqrt{\lambda_k(A^T A)}$
5. 计算 左奇异向量：$u_k = A v_k / \sigma_k$，其中 $k = 1, \dots, r$

从 $AA^T$ 的替代方法： 类似地，$AA^T$ 的特征向量给出左奇异向量 $u_k$，且具有相同的特征值 $\sigma_k^2$。

---

7.3 SVD 的几何意义：旋转 - 拉伸 - 旋转

SVD 揭示了 每一个线性变换 都可以分解为三个几何步骤：

$$A = U \Sigma V^T$$

1. 旋转（或反射）——通过 $V^T$：$V^T$ 将标准基映射为右奇异向量
2. 拉伸——通过 $\Sigma$：沿各坐标轴按 $\sigma_k$ 缩放（若 $m \neq n$，则同时嵌入到 $\mathbb{R}^m$ 中）
3. 旋转——通过 $U$：从拉伸后的坐标轴旋转到左奇异向量

单位圆到椭圆的视图： 当 $A$ 为 $2 \times 2$ 时，单位圆映射为一个椭圆，其半轴分别为 $\sigma_1 u_1$ 和 $\sigma_2 u_2$。

2x2 矩阵的四数 SVD： 任意 2x2 矩阵可以表示为：

$$A = Q_\theta \, \Sigma \, Q_\phi$$

其中 $Q_\theta$ 和 $Q_\phi$ 分别是转角为 $\theta$ 和 $\phi$ 的旋转矩阵（rotation matrices），$\Sigma$ 为对角矩阵，包含 $\sigma_1, \sigma_2$。

---

7.4 $A_k$ 是最接近 $A$ 的矩阵：主成分分析 (PCA)

Eckart-Young 定理： 矩阵 $A$ 的最佳秩-$k$ 近似（在 Frobenius 范数或谱范数意义下）通过截断 SVD 得到：

$$A_k = U_k \Sigma_k V_k^T = \sum_{i=1}^k \sigma_i u_i v_i^T$$

其中 $U_k$、$V_k$ 包含前 $k$ 个奇异向量，$\Sigma_k$ 包含前 $k$ 个奇异值。这最小化了在所有秩-$k$ 矩阵 $B$ 上的 $\|A - B\|$。

PCA（主成分分析, Principal Component Analysis）：

• 数据中心化：从数据矩阵 $A$ 的每一列减去其均值
• 计算中心化后数据的 SVD
• 第一主成分 (first principal component) $u_1$ 是最大方差的方向
• 样本协方差矩阵 (sample covariance matrix) 为 $S = AA^T / (n-1)$
• 总方差 (total variance) = $S$ 的特征值之和 = $\sum \sigma_i^2$
• 前 $k$ 个成分所捕获的方差比例为 $(\sum_{i=1}^k \sigma_i^2) / (\sum_{i=1}^m \sigma_i^2)$

---

7.5 计算 $S$ 的特征值与 $A$ 的奇异值

QR 算法（用于特征值, eigenvalues）：

1. 设 $S_0 = S$（对称矩阵）
2. 对 $k = 1, 2, \dots$：
   • 分解 $S_{k-1} = Q_k R_k$
   • 置 $S_k = R_k Q_k$
3. $S_k$ 收敛到一个对角矩阵，包含特征值

QR 算法利用了 $S_k = Q_k^T S_{k-1} Q_k$ 这一事实，因此所有 $S_k$ 都是相似的（similar），具有相同的特征值。

Golub-Kahan 算法（用于 SVD）： 一种高效的两步过程：

1. 利用 Householder 反射将 $A$ 化为双对角形式（bidiagonal form）
2. 对双对角矩阵应用隐式 QR 迭代以求奇异值

现代数值线性代数可在 $O(mn^2)$ 或 $O(m^2 n)$ 次运算内完成 SVD 计算。

---

7.6 利用 SVD 压缩图像

一张图像可以表示为一个像素值矩阵 $A$。SVD 提供了一种自然的压缩方案：

截断 SVD 压缩 (Truncated SVD Compression)： 不再存储全部 $m \times n$ 个元素，仅存储：

• $k$ 个奇异值 $\sigma_1, \dots, \sigma_k$
• $k$ 个左奇异向量 $u_1, \dots, u_k$（每个长度为 $m$）
• $k$ 个右奇异向量 $v_1, \dots, v_k$（每个长度为 $n$）

总存储量为：$k(1 + m + n)$，而非 $mn$。当 $k$ 相对于秩较小时，这就是显著的压缩。

示例： 一张 $1000 \times 1000$ 的图像（$10^6$ 个像素）可能被 $k=50$ 个奇异值很好地近似，只需存储约 $50 \times (1 + 1000 + 1000) \approx 100,000$ 个数——约 10 倍压缩。

---

7.7 正交性的胜利

本章颂扬了正交性（orthogonality）在整个线性代数中的基本作用。九个关键性质：

1. $\|Qx\| = \|x\|$ ——正交矩阵保持长度不变
2. 对称矩阵的特征向量是正交的 —— $S = Q\Lambda Q^T$
3. 奇异向量是正交的 —— $A = U\Sigma V^T$，其中 $U^T U = I$，$V^T V = I$
4. Gram-Schmidt 正交化从任意独立集合生成正交基
5. 四个基本子空间构成正交对 —— 行空间 $\perp$ 零空间，列空间 $\perp$ 左零空间
6. 傅里叶级数使用了正交的正弦/余弦函数 —— 傅里叶基是标准正交的（orthonormal）
7. 投影矩阵是对称且幂等的 —— $P^T = P$，$P^2 = P$
8. 最小二乘法通过正交性最小化误差 —— $A^T(b - A\hat{x}) = 0$
9. QR 分解将 Gram-Schmidt 结合为矩阵形式

极分解 (Polar Decomposition)： 每个矩阵 $A$ 都可以分解为：

$$A = Q S$$

其中 $Q$ 是正交矩阵，$S$ 是对称半正定矩阵（若 $A$ 可逆则为正定矩阵）。由 SVD 可得：$Q = UV^T$ 且 $S = V\Sigma V^T$。这是复数中 $z = re^{i\theta}$ 的矩阵类比。