第三十讲：奇异值分解

本讲我们介绍将一个矩阵写为 $A = U Σ V^{T}$ ，分解的因子分别为正交矩阵、对角矩阵、正交矩阵，与前面几讲的分解不同的是，这两个正交矩阵通常是不同的，而且这个式子可以对任意矩阵使用，不仅限于方阵、可对角化的方阵等。

在正定一讲中（第二十八讲）我们知道一个正定矩阵可以分解为 $A = Q Λ Q^{T}$ 的形式，由于 $A$ 对称性其特征向量是正交的，且其 $Λ$ 矩阵中的元素皆为正，这就是正定矩阵的奇异值分解。在这种特殊的分解中，我们只需要一个正交矩阵 $Q$ 就可以使等式成立。
在对角化一讲中（第二十二讲），我们知道可对角化的矩阵能够分解为 $A = S Λ S^{T}$ 的形式，其中 $S$ 的列向量由 $A$ 的特征向量组成，但 $S$ 并不是正交矩阵，所以这不是我们希望得到的奇异值分解。

我们现在要做的是，在 $A$ 的列空间中找到一组特殊的正交基 $v_{1}, v_{2}, \dots, v_{r}$ ，这组基在 $A$ 的作用下可以转换为 $A$ 的行空间中的一组正交基 $u_{1}, u_{2}, \dots, u_{r}$ 。

用矩阵语言描述为 $A [v_{1} v_{2} \dots v_{r}] = [σ_{1} u_{1} σ_{2} u_{2} \dots σ_{r} u_{r}] = [u_{1} u_{2} \dots u_{r}] [\begin{matrix} σ_{1} \\ σ_{2} \\ ⋱ \\ σ_{n} \end{matrix}]$ ，即 $A v_{1} = σ_{1} u_{1}, A v_{2} = σ_{2} u_{2}, \dots, A v_{r} = σ_{r} u_{r}$ ，这些 $σ$ 是缩放因子，表示在转换过程中有拉伸或压缩。而 $A$ 的左零空间和零空间将体现在 $σ$ 的零值中。

另外，如果算上左零、零空间，我们同样可以对左零、零空间取标准正交基，然后写为 $A [v_{1} v_{2} \dots v_{r} v_{r + 1} \dots v_{m}] = [u_{1} u_{2} \dots u_{r} u_{r + 1} \dots u_{n}] [\begin{array}{cccc} σ_{1} \\ ⋱ \\ σ_{r} \\ [\begin{matrix} 0 \end{matrix}] \end{array}]$ ，此时 $U$ 是 $m \times m$ 正交矩阵， $Σ$ 是 $m \times n$ 对角矩阵， $V^{T}$ 是 $n \times n$ 正交矩阵。

最终可以写为 $A V = U Σ$ ，可以看出这十分类似对角化的公式，矩阵 $A$ 被转化为对角矩阵 $Σ$ ，我们也注意到 $U, V$ 是两组不同的正交基。（在正定的情况下， $U, V$ 都变成了 $Q$ 。）。进一步可以写作 $A = U Σ V^{- 1}$ ，因为 $V$ 是标准正交矩阵所以可以写为 $A = U Σ V^{T}$

计算一个例子， $A = [\begin{matrix} 4 & 4 \\ - 3 & 3 \end{matrix}]$ ，我们需要找到：

行空间 $R^{2}$ 的标准正交基 $v_{1}, v_{2}$ ；
列空间 $R^{2}$ 的标准正交基 $u_{1}, u_{2}$ ；
$σ_{1} > 0, σ_{2} > 0$ 。

在 $A = U Σ V^{T}$ 中有两个标准正交矩阵需要求解，我们希望一次只解一个，如何先将 $U$ 消去来求 $V$ ？

这个技巧会经常出现在长方形矩阵中：求 $A^{T} A$ ，这是一个对称正定矩阵（至少是半正定矩阵），于是有 $A^{T} A = V Σ^{T} U^{T} U Σ V^{T}$ ，由于 $U$ 是标准正交矩阵，所以 $U^{T} U = I$ ，而 $Σ^{T} Σ$ 是对角线元素为 $σ^{2}$ 的对角矩阵。

现在有 $A^{T} A = V [\begin{matrix} σ_{1} \\ σ_{2} \\ ⋱ \\ σ_{n} \end{matrix}] V^{T}$ ，这个式子中 $V$ 即是 $A^{T} A$ 的特征向量矩阵而 $Σ^{2}$ 是其特征值矩阵。

同理，我们只想求 $U$ 时，用 $A A^{T}$ 消掉 $V$ 即可。

我们来计算 $A^{T} A = [\begin{matrix} 4 & - 3 \\ 4 & 3 \end{matrix}] [\begin{matrix} 4 & 4 \\ - 3 & 3 \end{matrix}] = [\begin{matrix} 25 & 7 \\ 7 & 25 \end{matrix}]$ ，对于简单的矩阵可以直接观察得到特征向量 $A^{T} A [\begin{matrix} 1 \\ 1 \end{matrix}] = 32 [\begin{matrix} 1 \\ 1 \end{matrix}], A^{T} A [\begin{matrix} 1 \\ - 1 \end{matrix}] = 18 [\begin{matrix} 1 \\ - 1 \end{matrix}]$ ，化为单位向量有 $σ_{1} = 32, v_{1} = [\begin{matrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{matrix}], σ_{2} = 18, v_{2} = [\begin{matrix} \frac{1}{\sqrt{2}} \\ - \frac{1}{\sqrt{2}} \end{matrix}]$ 。

到目前为止，我们得到 $[\begin{matrix} 4 & 4 \\ - 3 & 3 \end{matrix}] = [\begin{matrix} u_{?} & u_{?} \\ u_{?} & u_{?} \end{matrix}] [\begin{matrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{matrix}] [\begin{matrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} \end{matrix}]$ ，接下来继续求解 $U$ 。

$A A^{T} = U Σ V^{T} V Σ^{T} U^{T} = U Σ^{2} U^{T}$ ，求出 $A A^{T}$ 的特征向量即可得到 $U$ ， $[\begin{matrix} 4 & 4 \\ - 3 & 3 \end{matrix}] [\begin{matrix} 4 & - 3 \\ 4 & 3 \end{matrix}] = [\begin{matrix} 32 & 0 \\ 0 & 18 \end{matrix}]$ ，观察得 $A A^{T} [\begin{matrix} 1 \\ 0 \end{matrix}] = 32 [\begin{matrix} 1 \\ 0 \end{matrix}], A A^{T} [\begin{matrix} 0 \\ 1 \end{matrix}] = 18 [\begin{matrix} 0 \\ 1 \end{matrix}]$ 。但是我们不能直接使用这一组特征向量，因为式子 $A V = U Σ$ 明确告诉我们，一旦 $V$ 确定下来， $U$ 也必须取能够满足该式的向量，所以此处 $A v_{2} = [\begin{matrix} 0 \\ - \sqrt{18} \end{matrix}] = u_{2} σ_{2} = [\begin{matrix} 0 \\ - 1 \end{matrix}] \sqrt{18}$ ，则 $u_{1} = [\begin{matrix} 1 \\ 0 \end{matrix}], u_{2} = [\begin{matrix} 0 \\ - 1 \end{matrix}]$ 。（这个问题在本讲的官方笔记中有详细说明。）

补充： $A B$ 的特征值与 $B A$ 的特征值相同，证明来自Are the eigenvalues of AB equal to the eigenvalues of BA? (Citation needed!)：
取 $λ \neq 0$ ， $v$ 是 $A B$ 在特征值取 $λ$ 时的的特征向量，则有 $B v \neq 0$ ，并有 $λ B v = B (λ v) = B (A B v) = (B A) B v$ ，所以 $B v$ 是 $B A$ 在特征值取同一个 $λ$ 时的特征向量。
再取 $A B$ 的特征值 $λ = 0$ ，则 $0 = det A B = det A det B = det B A$ ，所以 $λ = 0$ 也是 $B A$ 的特征值，得证。

最终，我们得到 $[\begin{matrix} 4 & 4 \\ - 3 & 3 \end{matrix}] = [\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}] [\begin{matrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{matrix}] [\begin{matrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} \end{matrix}]$ 。

再做一个例子， $A = [\begin{matrix} 4 & 3 \\ 8 & 6 \end{matrix}]$ ，这是个秩一矩阵，有零空间。 $A$ 的行空间为 $[\begin{matrix} 4 \\ 3 \end{matrix}]$ 的倍数， $A$ 的列空间为 $[\begin{matrix} 4 \\ 8 \end{matrix}]$ 的倍数。

标准化向量得 $v_{1} = [\begin{matrix} 0.8 \\ 0.6 \end{matrix}], u_{1} = \frac{1}{\sqrt{5}} [\begin{matrix} 1 \\ 2 \end{matrix}]$ 。
$A^{T} A = [\begin{matrix} 4 & 8 \\ 3 & 6 \end{matrix}] [\begin{matrix} 4 & 3 \\ 8 & 6 \end{matrix}] = [\begin{matrix} 80 & 60 \\ 60 & 45 \end{matrix}]$ ，由于 $A$ 是秩一矩阵，则 $A^{T} A$ 也不满秩，所以必有特征值 $0$ ，则另特征值一个由迹可知为 $125$ 。
继续求零空间的特征向量，有 $v_{2} = [\begin{matrix} 0.6 \\ - 0, 8 \end{matrix}], u_{1} = \frac{1}{\sqrt{5}} [\begin{matrix} 2 \\ - 1 \end{matrix}]$

最终得到 $[\begin{matrix} 4 & 3 \\ 8 & 6 \end{matrix}] = [\begin{matrix} 1 & \underset{―}{2} \\ 2 & \underset{―}{- 1} \end{matrix}] [\begin{matrix} \sqrt{125} & 0 \\ 0 & \underset{―}{0} \end{matrix}] [\begin{matrix} 0.8 & 0.6 \\ \underset{―}{0.6} & \underset{―}{- 0.8} \end{matrix}]$ ，其中下划线部分都是与零空间相关的部分。

$v_{1}, \dots, v_{r}$ 是行空间的标准正交基；
$u_{1}, \dots, u_{r}$ 是列空间的标准正交基；
$v_{r + 1}, \dots, v_{n}$ 是零空间的标准正交基；
$u_{r + 1}, \dots, u_{m}$ 是左零空间的标准正交基。

通过将矩阵写为 $A v_{i} = σ_{i} u_{i}$ 形式，将矩阵对角化，向量 $u, v$ 之间没有耦合， $A$ 乘以每个 $v$ 都能得到一个相应的 $u$ 。

第三十讲：奇异值分解 ​

第三十讲：奇异值分解