Singular Values and Spectral Decomposition

先看两个矩阵：

$$A_1=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],A_2=\left[\begin{array}{cc}1& 0\\ 0& {10}^{-3}\end{array}\right].$$

它们的秩都是 2，但保留二维信息的能力并不相同。$A_1$ 完全不改变单位圆；$A_2$ 却把单位圆压成了一根针。第二个坐标在精确算术中确实还没有消失，但只要混入一点噪声，它就可能被彻底淹没。

秩说不出这种差别。它能告诉我们某个方向是否已经消失，却不能告诉我们这个方向离消失还有多远。我们真正想要的是另一种描述：矩阵作用在哪些输入方向上，分别把它们伸缩了多少，最后又把它们送到了哪些输出方向。

奇异值分解给出的正是这种描述。下面先从二维图形建立直觉，再沿着同一幅图理解奇异值谱、$A^{T}A$、低秩近似、谱分解和谱范数。

奇异值分解

对实矩阵 $A\in {\mathbb{R}}^{m\times n}$，奇异值分解写作

$$A=U\mathrm{\Sigma }{V}^T.$$

$U$ 和 $V$ 是正交矩阵，$\mathrm{\Sigma }$ 是一个矩形对角阵，它的对角元就是奇异值：

$${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0.$$

要看懂这个乘积，最好按照它作用在向量上的顺序，从右向左读：

$$x\stackrel{V^T}{\to }{V}^{T}x\stackrel{\mathrm{\Sigma }}{\to }\mathrm{\Sigma }{V}^{T}x\stackrel{U}{\to }U\mathrm{\Sigma }{V}^{T}x.$$

记 $v_i$ 为 $V$ 的第 $i$ 列，那么 $V^{T}x$ 的第 $i$ 个分量是

$$(V^{T}x{)}_i=v_i^{T}x.$$

因此，$V^T$ 所做的是读取 $x$ 沿输入方向 $v_i$ 的坐标；$\mathrm{\Sigma }$ 再把这个坐标乘以 ${\sigma }_i$；最后，$U$ 把结果写到输出方向 $u_i$ 上。换一种更紧凑的写法，就是

$$A{v}_i={\sigma }_i{u}_i.$$

整个分解的几何意义都藏在这个式子里：$v_i$ 是一组正交输入方向，$u_i$ 是一组正交输出方向，${\sigma }_i$ 记录从前者到后者还保留了多少长度；如果 ${\sigma }_i=0$，整个 $v_i$ 方向都会被抹掉。

调节下面的 ${\theta }_V$、${\sigma }_1$、${\sigma }_2$ 和 ${\theta }_U$，四幅图会让同一个固定向量依次经过 $x$、$V^{T}x$、$\mathrm{\Sigma }{V}^{T}x$ 和 $U\mathrm{\Sigma }{V}^{T}x$。

θ_V

30°

输入基角度σ₁

2.10

第一奇异值σ₂

0.65

第二奇异值θ_U

-20°

输出基角度

x

Vᵀx

ΣVᵀx

UΣVᵀx = Ax

单位球会变成什么形状，现在已经很清楚了。$V^T$ 和 $U$ 都是正交变换，不会改变长度；真正改变长度的只有 $\mathrm{\Sigma }$。所以，$A$ 会把单位球变成椭球，椭球各条半轴的长度是奇异值，方向则是 $U$ 的各列。

奇异值的作用

开头两个矩阵的奇异值分别是 $(1,1)$ 和 $(1,{10}^{-3})$。秩只看这两组数里有几个不为零：

$$\mathrm{rank}(A)=\mathrm{\#}\{i:{\sigma }_i>0\}.$$

奇异值补上了秩遗漏的信息。奇异值等于零，表示这个方向已经彻底消失；奇异值很小，表示这个方向在代数上仍然存在，却在数值上非常脆弱，因为恢复它时必须除以一个很小的数。

对满秩方阵，这种脆弱程度可以用二范数条件数概括：

$${\kappa }_2(A)=\frac{{\sigma }_1}{{\sigma }_n}.$$

$A_2$ 的条件数是 ${10}^3$，这意味着在求逆时，沿弱方向的误差可能被放大到同一数量级。如果 ${\sigma }_n=0$，逆矩阵不存在，条件数记为无穷大。

奇异值谱

把奇异值排列成有序列表 $({\sigma }_1,{\sigma }_2,\dots )$，得到的是奇异值谱。这里的限定词不能省略：方阵的“谱”通常指它的特征值，而特征值可以是负数或复数；奇异值适用于矩形矩阵，并且总是非负实数。

维度很高时，谱的尾部往往比精确秩更有信息。给定阈值 $\epsilon$，可以定义有效秩

$$r_{\epsilon }=\mathrm{\#}\{i:{\sigma }_i\ge \epsilon \}.$$

给定截断位置 $k$，还可以计算前 $k$ 个方向保留了多少平方奇异值总量：

$$E_k=\frac{\sum _{i=1}^k{\sigma }_i^2}{\sum _i{\sigma }_i^2}.$$

平坦的谱把尺度分散在许多方向上；快速衰减的谱则把尺度集中在前几个方向上。因此，一个矩阵完全可以拥有满的精确秩，同时在实际效果上很像一个低维映射。

下面的例子采用 ${\sigma }_i=e^{-\alpha (i-1)}$；调节 $\alpha$、$\epsilon$ 和 $k$，可以直接观察谱的衰减如何改变有效秩、保留能量和截断误差。

衰减 α

0.24

阈值 ε

0.08

截断阶数 k

5

ε

σ₁

σ₂

σ₃

σ₄

σ₅

σ₆

σ₇

σ₈

σ₉

σ₁₀

σ₁₁

σ₁₂

σ₁₃

σ₁₄

σ₁₅

σ₁₆

有效秩

r_ε = 11

保留能量

E₅ = 91.0%

截断误差

σ₆ = 0.301

这正是奇异值比秩更有用的地方：它把“这个方向还在不在”的二元判断，变成了“这个方向还保留了多强”的定量描述。

从 AᵀA 求 SVD

SVD 告诉我们，真正重要的输入方向是 $V$ 的各列。那么，只给定 $A$ 时，怎样找出这些方向？

关键观察是，输出长度的平方可以写成一个二次型：

$$\Vert Ax{\Vert }_2^2=x^T{A}^{T}Ax.$$

因此，$A^{T}A$ 记录了 $A$ 对每个输入方向的伸缩程度，却不再保留输出最后朝向哪里。把 SVD 代入后，这个消去过程会直接显现出来：

$$\begin{array}{rl}{A}^{T}A& =(U\mathrm{\Sigma }{V}^T{)}^T(U\mathrm{\Sigma }{V}^T)\\ & =V{\mathrm{\Sigma }}^T{U}^{T}U\mathrm{\Sigma }{V}^T\\ & =V{\mathrm{\Sigma }}^T\mathrm{\Sigma }{V}^T.\end{array}$$

因为 $U^{T}U=I$，左奇异方向被抵消了，剩下的正是 $A^{T}A$ 的正交谱分解：

$$A^{T}A{v}_i={\sigma }_i^2{v}_i.$$

所以，右奇异向量是 $A^{T}A$ 的特征向量，奇异值则是对应特征值的平方根。对每个正奇异值，还可以进一步得到左奇异向量：

$$u_i=\frac{A{v}_i}{{\sigma }_i}.$$

当 ${\sigma }_i=0$ 时，这个式子没有定义，$U$ 中剩余的列需要用一组正交补补齐。在输出空间做同样的推导，可以得到

$$A{A}^T{u}_i={\sigma }_i^2{u}_i.$$

这里有一个常见的简写错误。对任意向量 $x$，正确的式子是

$$A^{T}Ax=V{\mathrm{\Sigma }}^T\mathrm{\Sigma }{V}^{T}x,$$

而不是 ${\mathrm{\Sigma }}^{2}x$。只有先把 $x$ 写进 $V$ 的坐标系，或者 $x$ 本身就是某个 $v_i$ 时，对角阵的作用才会直接显现。

通过特征分解理解 SVD 很自然，但它不是首选的数值算法。显式构造 $A^{T}A$ 会把条件数平方，弱方向上的信息可能因此丢失；稳定的 SVD 算法通常直接处理 $A$，例如先把它化为双对角阵。

谱分解

关系式 $A{v}_i={\sigma }_i{u}_i$ 只描述了 $A$ 对一个特殊方向的作用。要恢复它对任意向量的作用，先把 $x$ 展开为

$$x=\sum _i(v_i^{T}x)v_i.$$

再对两边作用 $A$，得到

$$Ax=\sum _i{\sigma }_i(v_i^{T}x)u_i.$$

因为这个式子对所有 $x$ 都成立，所以矩阵本身可以写成

$$A=\sum _i{\sigma }_i{u}_i{v}_i^T.$$

每个秩一项都是一条独立的方向通道：$v_i^T$ 读取一个输入坐标，${\sigma }_i$ 对它进行伸缩，$u_i$ 再把结果写入输出空间。只保留前 $k$ 条通道，就得到截断 SVD：

$$A_k=\sum _{i=1}^k{\sigma }_i{u}_i{v}_i^T.$$

Eckart–Young 定理说明，在谱范数和 Frobenius 范数下，$A_k$ 都是 $A$ 的最佳秩 $k$ 近似；对谱范数，误差还有一个特别简洁的形式：

$$\Vert A-A_k{\Vert }_2={\sigma }_{k+1}.$$

这就是谱图尾部值得关注的原因：第一根被舍弃的柱子，恰好等于剩余部分在最坏方向上的误差。

这个秩一展开有时会被宽泛地称为“谱分解”，但保留术语边界很有用。实对称矩阵具有正交特征分解

$$A=Q\mathrm{\Lambda }{Q}^T=\sum _i{\lambda }_i{q}_i{q}_i^T.$$

这里同一个方向 $q_i$ 同时出现在左右两边。对一般矩阵，输入方向 $v_i$ 与输出方向 $u_i$ 未必相同，所以它的 SVD 并不是 $A$ 自身的正交谱分解。

如果 $A$ 是对称半正定矩阵，它的特征值都非负，特征分解便与 SVD 对齐。如果 $A$ 对称但不定，奇异值是 $|{\lambda }_i|$，符号会被吸收到一侧的奇异向量中。对任意矩阵，始终拥有正交谱分解的是 $A^{T}A$ 和 $A{A}^T$：

$$A^{T}A=\sum _i{\sigma }_i^2{v}_i{v}_i^T,A{A}^T=\sum _i{\sigma }_i^2{u}_i{u}_i^T.$$

谱范数

同一幅几何图还能直接给出最后一个量。谱范数所问的是：$A$ 最多能把一个单位向量拉长多少倍？

$$\Vert A{\Vert }_2=\underset{\Vert x{\Vert }_2=1}{max}\Vert Ax{\Vert }_2.$$

令 $y=V^{T}x$。正交性保证 $\Vert y{\Vert }_2=\Vert x{\Vert }_2=1$，于是

$$\begin{array}{rl}\Vert Ax{\Vert }_2^2& =\Vert U\mathrm{\Sigma }{V}^{T}x{\Vert }_2^2\\ & =\Vert \mathrm{\Sigma }y{\Vert }_2^2\\ & =\sum _i{\sigma }_i^2{y}_i^2\\ & \le {\sigma }_1^2\sum _i{y}_i^2\\ & ={\sigma }_1^2.\end{array}$$

取 $x=v_1$ 时等号成立，因此

$$\boxed{{\displaystyle \Vert A{\Vert }_2={\sigma }_1}}.$$

现在可以回答开头的问题了。理解一个矩阵，最有用的方式是把它看成一组正交的方向通道：

$$v_i\stackrel{{\sigma }_i}{\to }{u}_i.$$

秩只计算其中有多少条通道的增益不为零；奇异值谱记录所有通道的强弱；截断会以最优方式删去弱通道；谱范数则是最强通道的增益。这幅图适用于任意实矩阵，而只有当矩阵对称时，它的输入方向和输出方向才会对齐，形成矩阵自身的正交谱分解。