奇异值分解

奇异值分解（singular value decomposition，SVD）把任意实矩阵的作用拆成正交方向之间的伸缩。矩阵可以不是方阵，也可以没有逆。设 $A$ 为 $m \times n$ 实矩阵，秩为 $r$ 。它可写成 $A = \sum_{i = 1}^{r} σ_{i} u_{i} v_{i}^{𝖳} = U_{r} Σ_{r} V_{r}^{𝖳} .$ 非零奇异值按 $σ_{1} \geq \dots \geq σ_{r} > 0$ 排序。这里 $v_{i}$ 是输入空间中两两正交的单位向量， $u_{i}$ 是输出空间中两两正交的单位向量； $σ_{i}$ 是非零奇异值。式子 $A v_{i} = σ_{i} u_{i}$ 说得很具体：沿第 $i$ 个输入方向走一个单位，输出沿对应方向走 $σ_{i}$ 个单位。对没有输出的方向， $A$ 把它送到零。

单位圆怎样变成椭圆

看一个不是对称矩阵的例子： $A = (\begin{matrix} 0 & - 1 \\ 2 & 0 \end{matrix}), A (x, y) = (- y, 2 x) .$ 输入单位方向 $v_{1} = (1, 0)$ 被送到 $(0, 2) = 2 u_{1}$ ，其中 $u_{1} = (0, 1)$ ； $v_{2} = (0, 1)$ 被送到 $(- 1, 0) = u_{2}$ ，其中 $u_{2} = (- 1, 0)$ 。因而 $U = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}), Σ = (\begin{matrix} 2 & 0 \\ 0 & 1 \end{matrix}) .$ 取 $V = I_{2}$ ，便有 $A = U Σ V^{𝖳}$ 。左右两组方向各自正交，但承担不同角色： $V$ 指明输入方向， $U$ 指明对应的输出方向。这里先伸长，再把方向转过直角。直接相乘可以复核 $U Σ = A$ 。

把单位圆参数化为 $(x, y) = (\cos t, \sin t)$ ，其像为 $(X, Y) = (- \sin t, 2 \cos t)$ 。消去 $t$ 得 $X^{2} + Y^{2} / 4 = 1$ ：水平半轴长一，竖直半轴长二。图左的两条输入单位方向，对应图右标出的两条输出半轴；半轴长度就是奇异值。

左侧单位圆有水平和竖直两个单位方向，矩阵将其映到右侧竖直半轴二水平半轴一的椭圆；水平输入方向映到竖直二，竖直输入方向映到向左一 — 单位圆的两个正交方向经矩阵作用后仍对应正交方向，伸缩倍数为二和一。

本例 $A^{𝖳} A = (\begin{matrix} 4 & 0 \\ 0 & 1 \end{matrix})$ 。它的特征值四和一开平方，正是奇异值二和一。这不是巧合，也是一般构造的入口。

从对称矩阵得到任意矩阵的分解

对任意 $A$ ，矩阵 $A^{𝖳} A$ 对称，且对所有 $x$ 有 $x^{𝖳} A^{𝖳} A x = ‖ A x ‖^{2} \geq 0$ 。由实对称矩阵谱定理，它有一组正交规范特征向量 $v_{1}, \dots, v_{n}$ ，特征值非负。把正特征值写为 $σ_{i}^{2}$ ，并定义 $u_{i} = A v_{i} / σ_{i}$ 。

还需核对这些 $u_{i}$ 确实正交。由特征向量的正交性， $u_{i}^{𝖳} u_{j} = \frac{v_{i}^{𝖳} A^{𝖳} A v_{j}}{σ_{i} σ_{j}} = \frac{σ_{j}^{2} v_{i}^{𝖳} v_{j}}{σ_{i} σ_{j}} = {\begin{matrix} 1, & i = j, \\ 0, & i \neq j . \end{matrix}$ 零特征值的方向满足 $‖ A v_{i} ‖^{2} = 0$ ，因而 $A v_{i} = 0$ 。任意输入 $x$ 都能沿这组 $v_{i}$ 分解；作用 $A$ 后，零方向消失，剩下 $A x = \sum_{i = 1}^{r} σ_{i} u_{i} (v_{i}^{𝖳} x) .$ 这就是开篇的公式，也说明正奇异值的个数恰为矩阵的秩。若把两组单位向量各补足为完整正交基，还能写成 $A = U Σ V^{𝖳}$ ；完整 $Σ$ 可为长方形，未使用的位置填零。零奇异值并非“没有分解”，它们记录的是核中的输入方向。

伸缩范围与条件数

沿正交输入方向分解后，输出长度可逐项计算： $‖ A x ‖^{2} = \sum_{i = 1}^{r} σ_{i}^{2} (v_{i}^{𝖳} x)^{2} .$ 对单位输入，最大可能输出长度是 $σ_{1}$ ，在 $x = v_{1}$ 取得；因此矩阵的二范数 $‖ A ‖_{2} = σ_{1}$ 。若 $A$ 是可逆方阵，最小伸缩倍数为 $σ_{n}$ ，于是二范数条件数为 $κ_{2} (A) = σ_{1} / σ_{n}$ 。这一公式在奇异方阵上不能把零奇异值放到分母里当成有限条件数。

例如对角矩阵 $D = diag (1, 0.001)$ ，沿第二坐标的输入被压缩一千倍。若输出第二坐标因测量误差增加 $0.001$ ，恢复输入时第二坐标会增加一。这里的放大来自问题本身；计算方法再精确，也不能从受噪声污染的数据中无条件恢复被强烈压缩的方向。

只保留较大的伸缩方向

令 $A_{k} = \sum_{i = 1}^{k} σ_{i} u_{i} v_{i}^{𝖳}$ ，其中 $k < r$ 。它的秩至多为 $k$ ，丢掉的部分在二范数下满足 $‖ A - A_{k} ‖_{2} = σ_{k + 1}$ 。这个截断不仅方便计算，在所有秩不超过 $k$ 的矩阵里，它还达到最小的二范数误差。

可以直接看出下界。任取秩不超过 $k$ 的矩阵 $B$ ；在 $span (v_{1}, \dots, v_{k + 1})$ 这个 $k + 1$ 维空间内， $B$ 必有一个单位零向量 $x$ 。由于 $B x = 0$ ，而 $x$ 只由前 $k + 1$ 个 $v_{i}$ 组成， $‖ (A - B) x ‖ = ‖ A x ‖ \geq σ_{k + 1} ‖ x ‖ = σ_{k + 1} .$ 所以没有秩 $k$ 的 $B$ 能让最大方向误差小于 $σ_{k + 1}$ ； $A_{k}$ 刚好达到它。对前面的二阶矩阵，只留 $σ_{1} = 2$ 得 $A_{1} = (\begin{matrix} 0 & 0 \\ 2 & 0 \end{matrix})$ ，丢失的竖直输入方向造成的最大误差为一。截断是改变原变换以换取低秩表示，不能把被丢弃的方向一概判作“噪声”。

练习取 $B = (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$ 。计算 $B^{𝖳} B = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ ，其特征值为二和零，所以奇异值为 $\sqrt{2}, 0$ 。向量 $(1, - 1)$ 落入核；这说明即使矩阵有两个输入坐标，也可能只保留一个可辨别方向。

参考资料与知识联系

MIT OpenCourseWare：奇异值分解：一般矩阵的正交—伸缩—正交表示。
MIT 18.065，SVD 与低秩逼近讲次。
先修：正交矩阵、实对称矩阵谱定理；应用：条件数、伪逆、最小二乘法。