Chapter7 MATH1408
奇异值分解
1. 引言与动机
- 回顾特征值分解: 对于方阵 $A$ (特别是对称阵或可对角化阵)，我们有特征值分解 $A = P D P^{-1}$ (或 $A = U \Lambda U^T$ 对于对称阵，其中 $U$ 是正交阵，$\Lambda$ 是对角阵)。特征值分解在理解线性变换、解微分方程等方面非常有用。
- 问题: 对于任意的 $m \times n$ 矩阵 $A$ (不一定是方阵，也不一定对称)，是否存在类似的分解，能够揭示其内在结构？
- 目标: 找到两个正交矩阵 $U$ ($m \times m$) 和 $V$ ($n \times n$) 以及一个“对角”矩阵 $\Sigma$ ($m \times n$)，使得 $A = U \Sigma V^T$。
- 这里的“对角”矩阵 $\Sigma$ 指的是其主对角线上的元素 $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$ (其中 $r = \text{rank}(A)$)，其余元素为0。这些 $\sigma_i$ 称为奇异值 (Singular Values)。
- 历史: Beltrami (1873) 等人早期对二次型和双线性型进行研究时有所涉及。
- 几何意义 (初步): 考虑双线性型 $f(X,Y) = X^T A Y$。通过坐标变换 $X = U\xi$ 和 $Y = V\eta$ (其中 $U, V$ 是正交的)，我们希望 $f(X,Y) = \xi^T (U^T A V) \eta = \xi^T \Sigma \eta$，其中 $\Sigma$ 是对角形式。这启发了 $A = U \Sigma V^T$ 的形式。
2. 奇异值分解定理 (SVD Theorem)
2.1 定理叙述
任何 $m \times n$ 的实矩阵 $A$ (秩为 $r$) 都可以分解为：
$A = U \Sigma V^T$
其中：
- $U$ 是一个 $m \times m$ 的正交矩阵 (Orthogonal Matrix)。$U$ 的列向量 $u_1, u_2, \dots, u_m$ 称为 $A$ 的左奇异向量 (Left Singular Vectors)。
- $V$ 是一个 $n \times n$ 的正交矩阵 (Orthogonal Matrix)。$V$ 的列向量 $v_1, v_2, \dots, v_n$ 称为 $A$ 的右奇异向量 (Right Singular Vectors)。
- $\Sigma$ 是一个 $m \times n$ 的对角矩阵，其形式为：
$\Sigma = \begin{pmatrix}
D & O \\
O & O
\end{pmatrix}$
其中 $D = \text{diag}(\sigma_1, \sigma_2, \dots, \sigma_r)$ 是一个 $r \times r$ 的对角矩阵，且奇异值 (Singular Values) $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$。
$O$ 代表零矩阵块。$\Sigma$ 的具体形式取决于 $m, n, r$ 的关系：- 如果 $m=n=r$: $\Sigma = D$
- 如果 $m > r, n = r$: $\Sigma = \begin{pmatrix} D \\ O \end{pmatrix}$
- 如果 $m = r, n > r$: $\Sigma = \begin{pmatrix} D & O \end{pmatrix}$
- 一般形式 (如PPT所示，假设 $m \ge n$):
$\Sigma = \begin{pmatrix}
\sigma_1 & 0 & \dots & 0 & 0 & \dots & 0 \\
0 & \sigma_2 & \dots & 0 & 0 & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\
0 & 0 & \dots & \sigma_r & 0 & \dots & 0 \\
0 & 0 & \dots & 0 & 0 & \dots & 0 \\
\vdots & \vdots & & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \dots & 0 & 0 & \dots & 0
\end{pmatrix}_{m \times n}$
2.2 奇异值与 $A^T A$ 和 $A A^T$ 的关系
- 考虑矩阵 $B = A^T A$ (这是一个 $n \times n$ 的对称半正定矩阵)。
- $B$ 的特征值 $\lambda_i \ge 0$。
- 由于 $V^T (A^T A) V = V^T (U \Sigma V^T)^T (U \Sigma V^T) V = V^T (V \Sigma^T U^T U \Sigma V^T) V = \Sigma^T \Sigma$。
而 $\Sigma^T \Sigma$ 是一个 $n \times n$ 的对角矩阵，其对角元素为 $\sigma_1^2, \sigma_2^2, \dots, \sigma_r^2, 0, \dots, 0$。
因此，$A^T A$ 的非零特征值恰好是 $A$ 的非零奇异值的平方，即 $\lambda_i = \sigma_i^2$。
$V$ 的列向量 $v_i$ 是 $A^T A$ 的（标准正交）特征向量。 - 类似地，考虑 $A A^T$ (这是一个 $m \times m$ 的对称半正定矩阵)。
$A A^T = (U \Sigma V^T)(U \Sigma V^T)^T = U \Sigma V^T V \Sigma^T U^T = U (\Sigma \Sigma^T) U^T$。
$\Sigma \Sigma^T$ 是一个 $m \times m$ 的对角矩阵，其对角元素为 $\sigma_1^2, \sigma_2^2, \dots, \sigma_r^2, 0, \dots, 0$。
因此，$A A^T$ 的非零特征值也恰好是 $A$ 的非零奇异值的平方。
$U$ 的列向量 $u_i$ 是 $A A^T$ 的（标准正交）特征向量。结论:
- $A$ 的奇异值 $\sigma_i$ 是 $A^T A$ (或 $A A^T$) 的非零特征值的正平方根。
- 右奇异向量 $v_i$ 是 $A^T A$ 对应于特征值 $\sigma_i^2$ 的特征向量。
- 左奇异向量 $u_i$ 是 $A A^T$ 对应于特征值 $\sigma_i^2$ 的特征向量。
2.3 SVD定理的证明思路 (PPT中的推导)
构造 $V$:
- 考虑 $n \times n$ 对称半正定矩阵 $B = A^T A$。
- $B$ 可以被正交对角化: $V^T B V = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_n)$，其中 $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0$ 是 $B$ 的特征值， $V$ 是由 $B$ 的标准正交特征向量构成的正交矩阵。
- 由于 $\text{rank}(A^T A) = \text{rank}(A) = r$，所以 $B$ 恰好有 $r$ 个正特征值。
令 $\sigma_i = \sqrt{\lambda_i}$ for $i=1, \dots, r$。则 $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$。
其余 $\lambda_{r+1} = \dots = \lambda_n = 0$。 - 将 $V$ 的列向量分块为 $V = [V_1 | V_2]$，其中 $V_1 = [v_1, \dots, v_r]$ 对应非零特征值， $V_2 = [v_{r+1}, \dots, v_n]$ 对应零特征值。
- 我们有 $A^T A V_1 = V_1 \Lambda^2_D$ (其中 $\Lambda_D = \text{diag}(\sigma_1, \dots, \sigma_r)$，所以 $\Lambda_D^2 = \text{diag}(\sigma_1^2, \dots, \sigma_r^2)$)
- 并且 $A^T A V_2 = O$。由于 $N(A^T A) = N(A)$ (零空间相同)，所以 $A V_2 = O$。
构造 $U_1$:
- 令 $U_1 = A V_1 \Lambda_D^{-1}$ (这是一个 $m \times r$ 的矩阵)。
(注意 $\Lambda_D^{-1} = \text{diag}(1/\sigma_1, \dots, 1/\sigma_r)$ 是存在的，因为 $\sigma_i > 0$) - 验证 $U_1$ 的列是标准正交的：
$U_1^T U_1 = (\Lambda_D^{-1})^T V_1^T A^T A V_1 \Lambda_D^{-1}$
$= \Lambda_D^{-1} V_1^T (V_1 \Lambda_D^2) \Lambda_D^{-1}$ (因为 $V_1^T V_1 = E_r$ 且 $\Lambda_D$ 是对角的)
$= \Lambda_D^{-1} (V_1^T V_1) \Lambda_D^2 \Lambda_D^{-1}$
$= \Lambda_D^{-1} E_r \Lambda_D^2 \Lambda_D^{-1} = \Lambda_D^{-1} \Lambda_D = E_r$。 - 所以 $U_1$ 的 $r$ 个列向量是标准正交的。
- 令 $U_1 = A V_1 \Lambda_D^{-1}$ (这是一个 $m \times r$ 的矩阵)。
构造 $U$:
- $U_1$ 的列向量张成了 $A$ 的列空间 $C(A)$ 的一个标准正交基。
- 如果 $r < m$，则 $C(A)$ 的维数是 $r$。我们可以将 $U_1$ 的 $r$ 个列向量扩展为 $m$ 维空间 $\mathbb{R}^m$ 的一个标准正交基，得到 $U = [U_1 | U_2]$，其中 $U_2$ 是一个 $m \times (m-r)$ 的矩阵，其列向量与 $U_1$ 的列向量正交，并且自身也是标准正交的。$U_2$ 的列张成了 $N(A^T)$ (A的左零空间)。
- 这样构造的 $U$ 是一个 $m \times m$ 的正交矩阵。
验证分解:
- $U^T A V = \begin{pmatrix} U_1^T \\ U_2^T \end{pmatrix} A [V_1 | V_2] = \begin{pmatrix} U_1^T A V_1 & U_1^T A V_2 \\ U_2^T A V_1 & U_2^T A V_2 \end{pmatrix}$
- $U_1^T A V_1 = (A V_1 \Lambda_D^{-1})^T A V_1 = (\Lambda_D^{-1})^T V_1^T A^T A V_1 = \Lambda_D^{-1} (V_1^T V_1 \Lambda_D^2) = \Lambda_D^{-1} \Lambda_D^2 = \Lambda_D = \text{diag}(\sigma_1, \dots, \sigma_r)$。
- $A V_2 = O$ (如步骤1所述)，所以 $U_1^T A V_2 = O$ 和 $U_2^T A V_2 = O$。
- $U_2^T A V_1$: 由于 $U_1$ 的列张成 $C(A)$，而 $U_2$ 的列与 $U_1$ 的列正交，所以 $U_2$ 的列位于 $C(A)$ 的正交补 $N(A^T)$ 中。
$A V_1 = U_1 \Lambda_D$ (来自 $U_1$ 的定义)。$A V_1$ 的列在 $C(A)$ 中。
因此 $U_2^T (A V_1) = O$。 - 所以 $U^T A V = \begin{pmatrix} \Lambda_D & O \\ O & O \end{pmatrix} = \Sigma$。
- 因此 $A = U \Sigma V^T$。
□
2.4 奇异向量之间的关系
从 $A = U \Sigma V^T$ 可以得到：
- $A V = U \Sigma$
- $A^T U = V \Sigma^T$
写成分量形式：
- $A v_i = \sigma_i u_i$ for $i=1, \dots, r$
- $A v_i = 0$ for $i=r+1, \dots, n$ (因为 $\sigma_i=0$ for $i>r$)
- $A^T u_i = \sigma_i v_i$ for $i=1, \dots, r$
- $A^T u_i = 0$ for $i=r+1, \dots, m$
这表明：
- 右奇异向量 $v_i$ (来自 $V_1$) 被 $A$ 映射到左奇异向量 $u_i$ (来自 $U_1$) 的 $\sigma_i$ 倍。
- 右奇异向量 $v_i$ (来自 $V_2$) 位于 $A$ 的零空间 $N(A)$。
- 左奇异向量 $u_i$ (来自 $U_1$) 被 $A^T$ 映射到右奇异向量 $v_i$ (来自 $V_1$) 的 $\sigma_i$ 倍。
- 左奇异向量 $u_i$ (来自 $U_2$) 位于 $A^T$ 的零空间 $N(A^T)$ (也称为 $A$ 的左零空间)。
3. SVD 的几何解释
- SVD 将一个线性变换 $X \mapsto AX$ 分解为三个几何操作：
- 旋转/反射 (Rotation/Reflection): $V^T X$。将输入向量 $X$ 在 $\mathbb{R}^n$ 中进行旋转或反射，将其与 $V$ 的列向量（右奇异向量，构成标准正交基）对齐。
- 缩放 (Scaling): $\Sigma (V^T X)$。将旋转后的向量的每个分量沿着新的轴（由 $V$ 的列定义）进行缩放。前 $r$ 个分量按 $\sigma_i$ 缩放，其余分量变为0。结果向量在 $\mathbb{R}^m$ 中。
- 旋转/反射 (Rotation/Reflection): $U (\Sigma V^T X)$。将缩放后的向量在 $\mathbb{R}^m$ 中进行旋转或反射，将其与 $U$ 的列向量（左奇异向量，构成标准正交基）对齐。
- 例子: 考虑 $\mathbb{R}^2$ 中的单位圆。
- $V^T$ 旋转单位圆。
- $\Sigma$ 将旋转后的圆（仍然是圆）沿着主轴拉伸/压缩成一个椭圆（如果 $\sigma_1 \ne \sigma_2$）。如果某个 $\sigma_i=0$，则降维。
- $U$ 再将这个椭圆在 $\mathbb{R}^m$ (这里是 $\mathbb{R}^2$) 中旋转。
- 最终结果是，SVD 表明任何线性变换 $A$ 将 $\mathbb{R}^n$ 中的单位球体（或超球体）映射为 $\mathbb{R}^m$ 中的一个椭球体（或超椭球体，可能退化）。椭球体的主轴方向由左奇异向量 $u_i$ 给出，主轴的半轴长度由奇异值 $\sigma_i$ 给出。
4. SVD 的性质与应用
4.1 外积展开 (Outer Product Expansion)
$A = U \Sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T$
- 这是一个非常重要的性质，它将矩阵 $A$ 表示为 $r$ 个秩为1的矩阵之和。
- 每个 $u_i v_i^T$ 是一个 $m \times n$ 的秩1矩阵。
- 这个展开式对于低秩近似非常关键。
4.2 低秩近似 (Low-Rank Approximation) - Eckart-Young-Mirsky 定理
- 定理: 设 $A$ 的SVD为 $A = \sum_{i=1}^r \sigma_i u_i v_i^T$。对于任意 $k < r$，矩阵 $A_k = \sum_{i=1}^k \sigma_i u_i v_i^T$ 是秩为 $k$ 的矩阵中，与 $A$ 在 Frobenius 范数意义下最接近的矩阵。
即，$\min_{\text{rank}(B)=k} |A-B|_F = |A-A_k|_F = \sqrt{\sum_{i=k+1}^r \sigma_i^2}$。
（对于谱范数也有类似结论：$\min_{\text{rank}(B)=k} |A-B|_2 = |A-A_k|_2 = \sigma_{k+1}$）。 - 应用:
- 数据压缩: 图像、信号等可以表示为矩阵。通过SVD找到最重要的奇异值和奇异向量，用 $A_k$ 近似 $A$，可以大大减少存储需求。PPT中提到存储 $A_k$ 需要 $k(m+n+1)$ 个数值，而存储 $A$ 需要 $mn$ 个数值。
- 降噪: 较小的奇异值通常对应于数据中的噪声，将其去除可以得到更清晰的信号。
- 主成分分析 (PCA): SVD与PCA密切相关。$A^T A$ 的特征向量（即 $V$）是数据的主成分方向。
4.3 其他应用
- 伪逆 (Pseudoinverse): $A^+ = V \Sigma^+ U^T$，其中 $\Sigma^+$ 是将 $\Sigma$ 中的非零奇异值 $\sigma_i$ 替换为 $1/\sigma_i$ 再转置得到的。伪逆用于解线性最小二乘问题。
- 推荐系统: SVD被用于协同过滤算法，如Netflix Prize。
- 数值稳定性: SVD是计算矩阵的秩、解线性方程组、最小二乘问题等最稳健的方法之一。
- 求解齐次线性方程组: $N(A)$ 由对应于零奇异值的右奇异向量 $v_{r+1}, \dots, v_n$ 张成。
- 确定四个基本子空间:
- $C(A)$ (列空间) 的标准正交基是 $u_1, \dots, u_r$。
- $N(A^T)$ (左零空间) 的标准正交基是 $u_{r+1}, \dots, u_m$。
- $C(A^T)$ (行空间) 的标准正交基是 $v_1, \dots, v_r$。
- $N(A)$ (零空间) 的标准正交基是 $v_{r+1}, \dots, v_n$。
5. 例子 (PPT中的例子)
例1: $A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \end{pmatrix}$
- 计算 $A^T A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & -1 & 2 \end{pmatrix}$。
(PPT这里直接给出了 $A A^T$ 或其他矩阵，应从 $A^T A$ 开始找 $V$ 和 $\sigma_i$)
正确的做法是：
$A^T A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & -1 & 2 \end{pmatrix}$ (这是一个3x3矩阵)
特征值方程 $|\lambda I - A^T A|=0$ 解出来是 $\lambda_1=3, \lambda_2=1, \lambda_3=0$。
所以奇异值 $\sigma_1=\sqrt{3}, \sigma_2=1$。 ($r=2$)
$\Sigma = \begin{pmatrix} \sqrt{3} & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$。
找到对应的 $A^T A$ 的特征向量 $v_1, v_2, v_3$ 组成 $V$。
然后 $u_1 = \frac{1}{\sigma_1}Av_1$, $u_2 = \frac{1}{\sigma_2}Av_2$ 组成 $U$ (因为 $m=2, r=2$，所以 $U_2$ 不存在)。 - PPT中似乎直接给出了一个分解，需要验证。它提到了 $A = U^T \Lambda U$ (这更像是对称阵的谱分解，如果 $A$ 是对称的)。然后又提到了 $D = \Lambda W^T$。这部分表述比较混乱，应遵循标准的SVD步骤。
- 计算 $A^T A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & -1 & 2 \end{pmatrix}$。
例2 (几何变换): 变换 $S_1: x^2+y^2=1$ (单位圆) 到由矩阵 $A = \begin{pmatrix} 2 & 2 \\ 1 & -1 \end{pmatrix}$ 作用后的图形。
- 需要计算 $A$ 的SVD。
- $A^T A = \begin{pmatrix} 2 & 1 \\ 2 & -1 \end{pmatrix} \begin{pmatrix} 2 & 2 \\ 1 & -1 \end{pmatrix} = \begin{pmatrix} 5 & 3 \\ 3 & 5 \end{pmatrix}$。
特征值: $(5-\lambda)^2 - 9 = 0 \Rightarrow \lambda^2 - 10\lambda + 16 = 0 \Rightarrow (\lambda-8)(\lambda-2)=0$。
$\lambda_1=8, \lambda_2=2$。
奇异值 $\sigma_1 = \sqrt{8} = 2\sqrt{2}$, $\sigma_2 = \sqrt{2}$。
$\Sigma = \begin{pmatrix} 2\sqrt{2} & 0 \\ 0 & \sqrt{2} \end{pmatrix}$。 - 找到 $A^T A$ 的特征向量 $v_1, v_2$ 组成 $V$。
- $u_1 = \frac{1}{2\sqrt{2}}Av_1$, $u_2 = \frac{1}{\sqrt{2}}Av_2$ 组成 $U$。
- 变换后的椭圆的主轴由 $u_1, u_2$ 决定，半轴长为 $\sigma_1, \sigma_2$。
例3 (特殊矩阵): $A = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ (旋转 $-\pi/2$)
- $A^T A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I$。
特征值 $\lambda_1=1, \lambda_2=1$。
奇异值 $\sigma_1=1, \sigma_2=1$。 $\Sigma = I$。 - $V$ 可以是任意正交矩阵，例如 $V=I$。
- 则 $U = A V \Sigma^{-1} = A I I = A = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$。
- 所以 $A = U \Sigma V^T = A I I^T = A$。
- PPT中给出的分解是 $A = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \frac{1}{\sqrt{2}}\begin{pmatrix} -1 & 1 \\ 1 & 1 \end{pmatrix}$。
这里的 $U = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$, $V^T = \frac{1}{\sqrt{2}}\begin{pmatrix} -1 & 1 \\ 1 & 1 \end{pmatrix} \Rightarrow V = \frac{1}{\sqrt{2}}\begin{pmatrix} -1 & 1 \\ 1 & 1 \end{pmatrix}$。
$U$ 和 $V$ 都是正交的。这个分解也是有效的，说明SVD对于某些情况（如奇异值有重根）不是唯一的 (U和V的列可以乘以-1，或者在对应相同奇异值的子空间内旋转)。
- $A^T A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I$。
6. 总结
奇异值分解 $A = U \Sigma V^T$ 是一个极其强大的工具，它：
- 适用于任何 $m \times n$ 矩阵。
- 揭示了矩阵的内在几何结构和代数性质 (秩、四个基本子空间)。
- 提供了最佳低秩近似的方法。
- 在数据科学、工程、统计学等领域有广泛应用。
Chapter7 MATH1408