线性代数 Cheat Sheet 7-4：奇异值分解
对角化定理有很多重要的应用，但并不是所有矩阵都有分解式 $A = PDP^{-1}$，且 $D$ 是对角的。但分解 $A = QDP^{-1}$ 对任意 $m \times n$ 矩阵 $A$ 都有可能。这类特殊的分解称为奇异值分解。
奇异值分解基于一般的矩阵对角化性质，可以被长方形矩阵模仿：一个对称矩阵 $A$ 的特征值的绝对值表示度量 $A$ 拉长或压缩一个向量（特征向量）的成都。如果 $A \boldsymbol x = \lambda \boldsymbol x$，且 $\lVert \boldsymbol x \rVert = 1$，那么
\begin{equation}
\lVert A \boldsymbol x \rVert = \lVert \lambda \boldsymbol x \rVert = |\lambda| \lVert \boldsymbol x \rVert = |\lambda| \tag{1}
\end{equation}
如果 $\lambda_1$ 是具有最大数值的特征值，那么对应的单位向量 $\boldsymbol v_1$ 确定一个由 $A$ 拉长影响最大的方向，也就是说，$(1)$ 式表示 $\boldsymbol x = \boldsymbol v_1$ 时，$A \boldsymbol x$ 的长度最大化，且 $\lVert A \boldsymbol v_1 \rVert = |\lambda_1|$。这个对 $\boldsymbol v_1$ 和 $|\lambda_1|$ 的概述对长方形的矩阵来说也是类似地，这将导致奇异值分解。
1. 一个 $m \times n$ 矩阵的奇异值
令 $A$ 是 $m \times n$ 矩阵，那么 $A^\mathsf{T}A$ 是对称矩阵且可以正交对角化。令 $\{\boldsymbol v_1, \cdots, \boldsymbol v_n\}$ 是 $\mathbb{R}^n$ 的单位正交基且构成 $A^\mathsf{T}A$ 的特征向量，$\lambda_1, \cdots, \lambda_n$ 是 $A^\mathsf{T}A$ 对应的特征值，那么对 $1 \leq i \leq n$，
\begin{equation}
\lVert A \boldsymbol v_1 \rVert^2 = (A \boldsymbol v_1)^\mathsf{T} A \boldsymbol v_1 = \boldsymbol v_1^\mathsf{T} A^\mathsf{T} A \boldsymbol v_1 = \boldsymbol v_1^\mathsf{T} (\lambda_1 \boldsymbol v_1) = \lambda_1 \tag{2}
\end{equation}
所以，$A^\mathsf{T}A$ 的所有特征值都非负。如果必要，通过重新编号，可以假设特征值的重新排列满足
\begin{equation}
\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0
\end{equation}
$A$ 的奇异值是 $A^\mathsf{T}A$ 的特征值的平方根，记为 $\sigma_1, \cdots, \sigma_n$，且它们用递减顺序排列，也就是对 $1 \leq i \leq n$，$\sigma_i = \sqrt{\lambda_i}$。由 $(2)$ 可知，$A$ 的奇异值是向量 $A \boldsymbol v_1, \cdots A \boldsymbol v_n$ 的长度。
定理 9 假若 $\{\boldsymbol v_1, \cdots, \boldsymbol v_n\}$ 是包含 $A^\mathsf{T}A$ 的特征向量的 $\mathbb{R}^n$ 上的单位正交基，重新整理使得对应的 $A^\mathsf{T}A$ 的特征值满足 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$。假若 $A$ 有 $r$ 个非零奇异值，那么 $\{A\boldsymbol v_1, \cdots, A\boldsymbol v_r\}$ 是 $\mathrm{Col}\; A$ 的一个正交基，且 $\mathrm{rank}\; A = r$。
2. 奇异值分解
矩阵 $A$ 的分解涉及一个 $m \times n$ “对角”矩阵 $\Sigma$，其形式是
\begin{equation}
\Sigma = \begin{bmatrix} D & 0 \\ 0 & 0\end{bmatrix} \tag{3}
\end{equation}
其中，$D$ 是一个 $r \times r$ 对角矩阵，且 $r$ 不超过 $m$ 和 $n$ 中较小的那个。
定理 10（奇异值分解）设 $A$ 是秩为 $r$ 的 $m \times n$ 矩阵，那么存在一个类似 $(3)$ 中的 $m \times n$ 矩阵 $\Sigma$，其中 $D$ 的对角线元素是 $A$ 的前 $r$ 个奇异值，$\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$，并且存在一个 $m \times m$ 正交矩阵 $U$ 和一个 $n \times n$ 正交矩阵 $V$ 使得 $A = U \Sigma V^\mathsf{T}$。
任何分解 $A = U \Sigma V^\mathsf{T}$ 称为 $A$ 的一个奇异值分解（或 SVD），其中 $U$ 和 $V$ 是正交矩阵，$\Sigma$ 形如 $(3)$ 式，$D$ 具有正的对角线元素。矩阵 $U$ 和 $V$ 不是 $A$ 惟一确定的，但 $\Sigma$ 的对角线元素必须是 $A$ 的奇异值。这样的一个分解中，$U$ 的列称为 $A$ 的左奇异向量，$V$ 的列称为 $A$ 的右奇异向量。
一个奇异值分解可分为三步进行。下面以 $A = \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2\end{bmatrix}$ 为例，求 $A$ 的一个奇异值分解。
第一步，将 $A^\mathsf{T} A$ 正交对角化。即求矩阵 $A^\mathsf{T} A$ 的特征值及其对应的特征向量的单位正交集。这里
\begin{equation}
A^\mathsf{T} A =
\begin{bmatrix}
80 & 100 & 40 \\
100 & 170 & 140 \\
40 & 140 & 200
\end{bmatrix} \\
\lambda_1 = 360, \; \boldsymbol v_1 = \begin{bmatrix} 1/3 \\ 2/3 \\ 2/3 \end{bmatrix} \\
\lambda_2 = 90, \; \boldsymbol v_2 = \begin{bmatrix} -2/3 \\ -1/3 \\ 2/3 \end{bmatrix} \\
\lambda_3 = 0, \; \boldsymbol v_3 = \begin{bmatrix} 2/3 \\ -2/3 \\ 1/3 \end{bmatrix}
\end{equation}
第二步，计算 $V$ 和 $\Sigma$。将 $A^\mathsf{T} A$ 的特征值按降序排列，使用对应特征向量的排列构造 $P$。在上面的结果中，$\lambda_1 > \lambda_2 > \lambda_3$，构造
\begin{equation}
P = \begin{bmatrix} \boldsymbol v_1 & \boldsymbol v_2 & \boldsymbol v_3\end{bmatrix} =
\begin{bmatrix}1/3 & -2/3 & 2/3 \\2/3 & -1/3 & -2/3 \\2/3 & 2/3 & 1/3\end{bmatrix}
\end{equation}
特征值的平方根就是奇异值：$\sigma_1 = \sqrt{360} = 6 \sqrt{10}$，$\sigma_2 = \sqrt{90} = 3 \sqrt{10}$，$\sigma_3 = 0$。其中非零奇异值是矩阵 $D$ 的对角线元素。矩阵 $\Sigma$ 与矩阵 $A$ 的行列数相同，以矩阵 $D$ 为其左上角，其他元素为 $0$。
\begin{equation}
D = \begin{bmatrix} 6 \sqrt{10} & 0 \\ 0 & 3 \sqrt{10} \end{bmatrix} \\
\Sigma = \begin{bmatrix} D & 0 \end{bmatrix} = \begin{bmatrix} 6 \sqrt{10} & 0 & 0 \\ 0 & 3 \sqrt{10} & 0 \end{bmatrix}
\end{equation}
第三步，构造 $U$。当矩阵 $A$ 的秩为 $r$ 时，矩阵 $U$ 的前 $r$ 列是从 $A \boldsymbol v_1 \cdots A \boldsymbol v_r$ 计算得到的单位向量。这里 $A$ 有两个非零奇异值，因此 $\mathrm{rank}\; A = 2$。根据式 $(2)$，有 $\lVert A \boldsymbol v_1 \rVert = \sigma_1$，$\lVert A \boldsymbol v_2 \rVert = \sigma_2$，于是
\begin{equation}
\boldsymbol u_1 = \frac{1}{\sigma_1} A \boldsymbol v_1 = \frac{1}{6\sqrt{10}} \begin{bmatrix} 18 \\ 6 \end{bmatrix} = \begin{bmatrix} 3/\sqrt{10} \\ 1/\sqrt{10} \end{bmatrix} \\
\boldsymbol u_2 = \frac{1}{\sigma_2} A \boldsymbol v_2 = \frac{1}{3\sqrt{10}} \begin{bmatrix} 3 \\ -9 \end{bmatrix} = \begin{bmatrix} 1/\sqrt{10} \\ -3/\sqrt{10} \end{bmatrix} \\
\end{equation}
留意到 $\{\boldsymbol u_1, \boldsymbol u_2 \}$ 已经是 $\mathbb{R}^2$ 的一个基，因此构造 $U$ 不需要另外的向量，$U = \begin{bmatrix} \boldsymbol u_1 & \boldsymbol u_2 \end{bmatrix}$。$A$ 的奇异值分解是
\begin{equation}
A = \begin{bmatrix} 3\sqrt{10} & 1\sqrt{10} \\ 1\sqrt{10} & -3\sqrt{10} \end{bmatrix}
\begin{bmatrix} 6 \sqrt{10} & 0 & 0 \\ 0 & 3 \sqrt{10} & 0 \end{bmatrix}
\begin{bmatrix}1/3 & -2/3 & 2/3 \\2/3 & -1/3 & -2/3 \\2/3 & 2/3 & 1/3\end{bmatrix}
\end{equation}
3. 奇异值分解的应用
奇异值分解常用于估计矩阵的秩。
当应用矩阵 $A$ 的奇异值分解时，多数涉及方程 $A \boldsymbol x = \boldsymbol b$ 的数值计算要尽可能地可靠。两个正交矩阵 $U$ 和 $V$ 不影响向量的长度和两个向量的夹角（定理 7）。数值计算中的任何不稳定因素都与 $\Sigma$ 有关。如果 $A$ 的奇异值非常大或非常小，则舍入误差几乎不可避免，此时，知道 $\Sigma$ 和 $V$ 中的元素对分析误差特别有用。
如果 $A$ 是一个 $n \times n$ 可逆矩阵，那么最大奇异值和最小奇异值的比率 $\sigma_1 / \sigma_n$ 给出了矩阵 $A$ 的条件数。条件数影响 $A \boldsymbol x = \boldsymbol b$ 的解对 $A$ 元素变化（或误差）的敏感程度。
给定 $m \times n$ 矩阵 $A$ 的一个奇异值分解，取 $\boldsymbol u_1, \cdots, \boldsymbol u_m$ 是左奇异向量，$\boldsymbol v_1, \cdots, \boldsymbol v_m$ 是右奇异向量，且 $\sigma_1, \cdots, \sigma_n$ 是奇异值，$r$ 为 $A$ 的秩。由定理 9，
\begin{equation}
\{\boldsymbol u_1, \cdots, \boldsymbol u_m\} \tag{4}
\end{equation}
是 $\mathrm{Col}\; A$ 的一个单位正交基。由 6-1 定理 3，$(\mathrm{Col}\; A)^\perp = \mathrm{Nul}\; A^\mathsf{T}$，因此
\begin{equation}
\{\boldsymbol u_{r+1}, \cdots, \boldsymbol u_m\} \tag{5}
\end{equation}
是 $\mathrm{Nul}\; A$ 的一个正交基。
由于当 $1 \leq i \leq n$ 时 $\lVert A \boldsymbol v_i \rVert = \sigma_i$，且 $\sigma_i$ 是零的充分必要条件是 $i > r$，因此向量 $\boldsymbol v_{r+1}, \cdots, \boldsymbol v_n$ 生成一个维数为 $n – r$ 的子空间 $\mathrm{Nul}\; A$。由秩定理可知，$\dim \mathrm{Nul}\; A = n – \mathrm{rank}\; $，从而说明
\begin{equation}
\{\boldsymbol v_{r+1}, \cdots, \boldsymbol v_n\} \tag{6}
\end{equation}
是 $\mathrm{Nul}\; A$ 的一个单位正交基。
由 $(4)$ 和 $(5)$ 可知，空间 $\mathrm{Nul}\; A^\mathsf{T}$ 的正交补是 $\mathrm{Col}\; A$。将 $A$ 和 $A^\mathsf{T}$ 交换，有
\begin{equation}
(\mathrm{Nul}\; A)^\perp = \mathrm{Col}\; A^\mathsf{T} = \mathrm{Row}\; A
\end{equation}
因此，右 $(6)$ 得
\begin{equation}
\{\boldsymbol v_1, \cdots, \boldsymbol v_r\} \tag{7}
\end{equation}
是 $\mathrm{Row}\; A$ 的一个单位正交基。
定理（可逆矩阵定理）设 $A$ 为 $m \times n$ 矩阵，那么下述命题中的每一个都与 $A$ 是可逆矩阵的命题等价。
u. $(\mathrm{Col}\; A)^\perp = \{\boldsymbol 0 \}$
v. $(\mathrm{Nul}\; A)^\perp = \mathbb{R}^n$
w. $\mathrm{Row}\; A = \mathbb{R}^n$
x. $A$ 有 $n$ 个非零的特征值。
当 $\Sigma$ 包含零元素的行或列时，矩阵 $A$ 具有更简洁的分解。利用上面建立的符号，取 $r = \mathrm{rank}\; A$，将 $U$ 和 $V$ 矩阵分块称为第一块包含 $r$ 列的子矩阵：
\begin{equation}
U = \begin{bmatrix} U_r & U_{m-r} \end{bmatrix}, \; 其中 U_r = \begin{bmatrix} \boldsymbol u_1 & \cdots & \boldsymbol u_r \end{bmatrix} \\
V = \begin{bmatrix} V_r & V_{n-r} \end{bmatrix}, \; 其中 V_r = \begin{bmatrix} \boldsymbol v_1 & \cdots & \boldsymbol v_r \end{bmatrix}
\end{equation}
那么 $U_r$ 是 $m \times r$，$V_r$ 是 $n \times r$。分块矩阵的乘法表明
\begin{equation}
A = \begin{bmatrix} U_r & U_{m-r} \end{bmatrix}
\begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}
\begin{bmatrix} V_r^\mathsf{T} \\ V_{n-r}^\mathsf{T} \end{bmatrix} =
U_r D V_r^\mathsf{T}
\end{equation}
矩阵 $A$ 的这个分解称为 $A$ 的简化的奇异值分解。由于 $D$ 的对角线元素非零，因此 $D$ 是可逆矩阵。下面的矩阵称为 $A$ 的伪逆（也称穆尔-彭罗斯逆）：
\begin{equation}
A^+ = V_r D^{-1} U_r^\mathsf{T}
\end{equation}