奇异值分解（一）

为何要分解矩阵？

在深入数学细节之前，我们先建立一个直观的认识。在机器学习中，矩阵通常代表着数据或一种变换。例如，一个用户-物品评分矩阵，或者一个将输入向量变换到输出向量的线性算子。奇异值分解的核心思想是，任何复杂的线性变换（由矩阵 A 代表）都可以被拆解为三个基本、更易于理解的连续操作：

1. 一次 旋转或反射。
2. 一次沿着坐标轴的 缩放。
3. 另一次 旋转或反射。

SVD的强大之处在于，它保证了任何矩阵都存在这样一种分解方式，并为我们揭示了矩阵内在的、最重要的“结构信息”。

---

一、奇异值分解的定义与基本定理

1.1 定义与符号约定（对应定义15.1）

我们首先严格地定义奇异值分解。

对于任意一个给定的 $m\times n$ 实矩阵 $A$，它的奇异值分解是指存在一个分解式，形如：

$$A=U\Sigma V^T$$

这里的每个组成部分都有明确的身份和性质：

• $A$: 我们要分解的目标矩阵，维度为 $m\times n$。
• $U$: 一个 $m\times m$ 的 正交矩阵（Orthogonal Matrix）。它的列向量 $u_1,u_2,\dots ,u_m$ 被称为 左奇异向量。
  • “正交”意味着 $U$ 的所有列向量彼此正交且长度为1（标准正交基），这使得 $U^{T}U=U{U}^T=I_m$（$I_m$ 是 $m$ 阶单位矩阵）。从几何上看，$U$ 代表了一个不改变向量长度和夹角的旋转或反射操作。
• $V$: 一个 $n\times n$ 的 正交矩阵。它的列向量 $v_1,v_2,\dots ,v_n$ 被称为 右奇异向量。
  • 同样，“正交”意味着 $V^{T}V=V{V}^T=I_n$。从几何上看，$V$ 也代表了一个旋转或反射操作。注意，在分解式中我们使用的是 $V^T$。
• $\Sigma$: 一个 $m\times n$ 的 矩形对角矩阵（Rectangular Diagonal Matrix）。它的特殊之处在于，只有主对角线上的元素可能非零，其余元素都为0。
  • 这些对角线上的元素 ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_p$ 被称为 奇异值，其中 $p=\min (m,n)$。
  • 按照约定，这些奇异值是非负的，并且是降序排列的：${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_p\ge 0$。

1.2 核心定理：存在性与构造性证明

定理 15.1：

若 $A$ 为一个 $m\times n$ 实矩阵，则 $A$ 的奇异值分解 $A=U\Sigma V^T$ 存在。

这个定理的证明是构造性的，也就是说，我们通过一步步地找出 $U,\Sigma ,V$ 来证明它们的存在性。这正是理解SVD计算原理的关键。为方便讨论，我们不妨假设 $m\ge n$（若 $m<n$，证明逻辑完全对称，只需从 $A{A}^T$ 出发即可）。

证明步骤：

第一步：构造 $V$ 和 $\Sigma$

这一步的核心技巧是，我们不直接处理可能非方阵、非对称的 $A$，而是构造一个与之相关且性质优良的矩阵。这个矩阵就是 $A^{T}A$。

1. 构造辅助矩阵：我们计算 $A^{T}A$。

   • $A$ 是 $m\times n$ 矩阵，$A^T$ 是 $n\times m$ 矩阵，所以 $A^{T}A$ 是一个 $n\times n$ 的 方阵。

   • 更重要的是，$A^{T}A$ 是 对称的，因为 $(A^{T}A{)}^T=A^T(A^T{)}^T=A^{T}A$。

   • 并且，$A^{T}A$ 是 半正定的。这意味着对于任意非零向量 $x\in {\mathbb{R}}^n$，都有 $x^T(A^{T}A)x\ge 0$。这一点从如下的公式(15.3)的推导可以看出：

     $$x^T(A^{T}A)x=(Ax{)}^T(Ax)=\Vert Ax{\Vert }^2\ge 0$$

     这个性质保证了 $A^{T}A$ 的所有特征值都是非负的。

2. 对 $A^{T}A$ 进行特征值分解：

   • 根据谱定理，任何实对称矩阵都可以被正交对角化。因此，存在一个 $n\times n$ 的正交矩阵 $V$ 和一个对角矩阵 $\Lambda$，使得：

     $$A^{T}A=V\Lambda V^T$$

   • 矩阵 $V$ 的列向量 $v_1,v_2,\dots ,v_n$ 就是 $A^{T}A$ 的标准正交特征向量。这便是我们SVD中所需要的 $V$。

   • 对角矩阵 $\Lambda$ 的对角元 ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ 就是 $A^{T}A$ 的特征值。由于 $A^{T}A$ 是半正定的，我们知道所有 ${\lambda }_i\ge 0$。我们可以将它们降序排列。

3. 定义奇异值：

   • 我们定义矩阵 $A$ 的 奇异值 ${\sigma }_j$ 为其特征值 ${\lambda }_j$ 的平方根：

     $${\sigma }_j=\sqrt{{\lambda }_j},j=1,2,\dots ,n$$

   • 将这些奇异值降序排列 ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n\ge 0$，并用它们构建 $m\times n$ 的矩形对角矩阵 $\Sigma$。当 $m>n$ 时，$\Sigma$ 的形式如下：

     $$\Sigma ={\left[\begin{array}{cccc}{\sigma }_1& & & \\ & {\sigma }_2& & \\ & & \ddots & \\ & & & {\sigma }_n\\ 0& \dots & \dots & 0\\ ⋮& & & ⋮\\ 0& \dots & \dots & 0\end{array}\right]}_{m\times n}$$

   • 至此，我们已经成功构造出了 $V$ 和 $\Sigma$。

第二步：构造 $U$

现在，我们有了 $V$ 和 $\Sigma$，需要根据关系式 $A=U\Sigma V^T$ 来找出 $U$。将关系式两边同时右乘 $V$，得到：

$$AV=U\Sigma$$

我们把这个矩阵方程展开，逐列来看。设 $A$ 的秩为 $r$，即 $A^{T}A$ 有 $r$ 个非零特征值，因此有 $r$ 个非零奇异值 ${\sigma }_1,\dots ,{\sigma }_r>0$，而 ${\sigma }_{r+1},\dots ,{\sigma }_n=0$。

1. 定义 $U$ 的前 $r$ 列：

   • 对于 $j=1,\dots ,r$，上面的矩阵方程的第 $j$ 列是：

     $$A{v}_j={\sigma }_j{u}_j$$

   • 由于 ${\sigma }_j>0$，我们可以定义 $u_j$ 为：

     $$u_j=\frac{1}{{\sigma }_j}A{v}_j,j=1,\dots ,r$$

     这给了我们 $U$ 的前 $r$ 个列向量。

2. 证明这 $r$ 列是标准正交的：我们需要证明 $u_i^T{u}_j={\delta }_{ij}$ ( ${\delta }_{ij}$ 当 $i=j$ 时为1，否则为0)。

   $$\begin{array}{rlrl}{u}_i^T{u}_j& ={\left(\frac{1}{{\sigma }_i}A{v}_i\right)}^T\left(\frac{1}{{\sigma }_j}A{v}_j\right)& & \text{（根据定义）}\\ & =\frac{1}{{\sigma }_i{\sigma }_j}{v}_i^T{A}^{T}A{v}_j& & \text{（展开转置）}\\ & =\frac{1}{{\sigma }_i{\sigma }_j}{v}_i^T({\lambda }_j{v}_j)& & \text{（因为 ATAvj=λjvj）}\\ & =\frac{{\lambda }_j}{{\sigma }_i{\sigma }_j}{v}_i^T{v}_j& & \text{（提出标量）}\\ & =\frac{{\sigma }_j^2}{{\sigma }_i{\sigma }_j}(v_i^T{v}_j)& & \text{（因为 λj=σj2）}\end{array}$$
   • 由于 $V$ 的列向量 $\{v_i\}$ 是标准正交的，所以 $v_i^T{v}_j={\delta }_{ij}$。
   • 当 $i=j$ 时，上式变为 $\frac{{\sigma }_j^2}{{\sigma }_j^2}(1)=1$。
   • 当 $i\ne j$ 时，上式变为 $\frac{{\sigma }_j^2}{{\sigma }_i{\sigma }_j}(0)=0$。
   • 这就证明了 $\{u_1,\dots ,u_r\}$ 构成了 ${\mathbb{R}}^m$ 空间中的一个标准正交向量集。

3. 构造 $U$ 的剩余 $m-r$ 列：

   • 我们已经有了 $r$ 个标准正交的 $m$ 维向量。如果 $r<m$，这 $r$ 个向量张成的是 ${\mathbb{R}}^m$ 的一个子空间。
   • 我们可以使用如格拉姆-施密特（Gram-Schmidt）正交化等方法，找到另外 $m-r$ 个单位向量 $\{u_{r+1},\dots ,u_m\}$，使得它们与 $\{u_1,\dots ,u_r\}$ 正交，并且彼此也正交。
   • 这样，我们就得到了完整的 $m$ 个标准正交向量，将它们作为列，构成了一个 $m\times m$ 的正交矩阵 $U=[u_1,\dots ,u_r,u_{r+1},\dots ,u_m]$。

第三步：验证 $A=U\Sigma V^T$

我们已经构造好了 $U,\Sigma ,V$。现在只需验证它们相乘的结果是否确实是 $A$。我们来计算 $U\Sigma V^T$：

$$\begin{array}{rl}U\Sigma V^T& =[u_1,\dots ,u_r,\dots ,u_m]{\left[\begin{array}{cccc}{\sigma }_1& & & \\ & \ddots & & \\ & & {\sigma }_r& \\ & & & 0\end{array}\right]}_{m\times n}[v_1,\dots ,v_n{]}^T\\ & =\sum _{j=1}^r{\sigma }_j{u}_j{v}_j^T\end{array}$$

为了证明这个和等于 $A$，我们可以证明它们作用在任意向量 $v_k$ 上结果相同。

$$\begin{array}{rl}\left(\sum _{j=1}^r{\sigma }_j{u}_j{v}_j^T\right)v_k& =\sum _{j=1}^r{\sigma }_j{u}_j(v_j^T{v}_k)\\ & ={\sigma }_k{u}_k(\text{因为 }{v}_j^T{v}_k={\delta }_{jk})\\ & ={\sigma }_k\left(\frac{1}{{\sigma }_k}A{v}_k\right)(\text{根据 }{u}_k\text{ 的定义})\\ & =A{v}_k\end{array}$$

由于 $\{v_k\}$ 是 ${\mathbb{R}}^n$ 的一组基，上述等式对所有基向量成立，意味着对任意向量都成立。因此，我们证明了 $A=U\Sigma V^T$。

证明完毕。 这个构造过程不仅证明了SVD的存在性，也为我们提供了计算它的蓝图。

---

二、奇异值分解的不同形式

根据实际需求，SVD有几种不同的变体。

2.1 完全奇异值分解（Full SVD）

这就是我们刚刚证明和定义的标准形式：$A_{m\times n}=U_{m\times m}{\Sigma }_{m\times n}{V}_{n\times n}^T$。 $U$ 和 $V$ 都是满秩的方阵，$\Sigma$ 的维度与 $A$ 完全相同，包含了大量的零。

2.2 紧凑奇异值分解（Compact SVD，对应定义15.2）

在实际应用中，奇异值为零的部分通常是冗余信息。紧凑SVD就是去除这些冗余部分。设矩阵 $A$ 的秩为 $r$（即有 $r$ 个非零奇异值）。

$$A=U_r{\Sigma }_r{V}_r^T$$

• ${\Sigma }_r$: 是一个 $r\times r$ 的对角方阵，仅包含 $r$ 个非零奇异值 ${\sigma }_1,\dots ,{\sigma }_r$。
• $U_r$: 取完全SVD中 $U$ 的前 $r$ 列（即 $u_1,\dots ,u_r$），构成一个 $m\times r$ 的矩阵。
• $V_r$: 取完全SVD中 $V$ 的前 $r$ 列（即 $v_1,\dots ,v_r$），构成一个 $n\times r$ 的矩阵。$V_r^T$ 则是 $r\times n$ 维度。

为什么可以这样做？ 回顾完全SVD的乘法过程 $U\Sigma V^T$，我们会发现 $U$ 中第 $r+1$ 列到第 $m$ 列，以及 $V$ 中第 $r+1$ 列到第 $n$ 列，都将与 $\Sigma$ 中的零元素相乘。因此，这些列对最终结果 $A$ 没有任何贡献。紧凑SVD正是去除了这些无贡献的部分，使得存储和计算更高效。

2.3 截断奇异值分解（Truncated SVD）

这是SVD在机器学习中应用最广泛的形式。它不仅去除了零奇异值部分，还进一步舍弃了那些值很小的奇异值。我们选择一个远小于秩 $r$ 的数 $k$，只保留前 $k$ 个最大的奇异值。

$$A\approx A_k=U_k{\Sigma }_k{V}_k^T$$

• ${\Sigma }_k$: 是一个 $k\times k$ 的对角方阵，包含前 $k$ 个最大的奇异值。
• $U_k$: 取 $U$ 的前 $k$ 列，构成 $m\times k$ 矩阵。
• $V_k$: 取 $V$ 的前 $k$ 列，构成 $n\times k$ 矩阵。

这里的关键是 约等于（$\approx$）。$A_k$ 是原矩阵 $A$ 的一个 低秩近似。后续我们会学到（对应书15.3节），截断SVD是在所有秩为 $k$ 的矩阵中，对原矩阵 $A$ 的最优近似。这正是PCA降维、数据压缩和去噪的理论基础。

---

三、几何解释

一个 $m\times n$ 的矩阵 $A$ 可以看作一个从 $n$ 维空间 ${\mathbb{R}}^n$ 到 $m$ 维空间 ${\mathbb{R}}^m$ 的线性变换 $T:x\mapsto Ax$。

SVD分解 $A=U\Sigma V^T$ 告诉我们，这个看似复杂的变换 $T$ 可以分解为三步：

考虑一个向量 $x\in {\mathbb{R}}^n$ 经过变换 $y=Ax=U\Sigma V^{T}x$ 的过程：

1. 第一步：$V^{T}x$ （输入空间的坐标系旋转/反射）

   • $V$ 的列向量 $\{v_1,\dots ,v_n\}$ 构成 ${\mathbb{R}}^n$ 空间的一组新的标准正交基。
   • 计算 $V^{T}x$ 的过程，实际上是将向量 $x$ 从标准的坐标系 $(e_1,e_2,\dots )$ 投影到这个由 $V$ 的列向量定义的 新坐标系 上，得到新的坐标。可以理解为对输入空间进行了一次旋转或反射，使得基准坐标轴与 $\{v_j\}$ 对齐。

2. 第二步：$\Sigma (V^{T}x)$ （沿新坐标轴的缩放）

   • $\Sigma$ 是一个矩形对角矩阵。它将上一步得到的新坐标向量的每一个分量，沿着新的坐标轴（即 $v_j$ 方向）进行缩放，缩放比例就是对应的奇异值 ${\sigma }_j$。
   • 如果 ${\sigma }_j$ 很大，说明在这个方向上的拉伸很显著。
   • 如果 ${\sigma }_j$ 很小，说明在这个方向上的信息被压缩了。
   • 如果 ${\sigma }_j=0$（对于 $j>r$），说明这个维度直接被“压扁”了，其信息完全丢失。
   • 经过这一步，我们得到一个在 $m$ 维空间中的向量（因为 $\Sigma$ 是 $m\times n$ 的），但它仍然是用一个中间坐标系来表示的。

3. 第三步：$U(\Sigma V^{T}x)$ （输出空间的坐标系旋转/反射）

   • $U$ 的列向量 $\{u_1,\dots ,u_m\}$ 构成了输出空间 ${\mathbb{R}}^m$ 的一组新的标准正交基。
   • 将上一步得到的缩放后的向量乘以 $U$，相当于将这个向量从中间坐标系（与 $\{u_j\}$ 关联）转换回 ${\mathbb{R}}^m$ 的标准坐标系中。这可以理解为对输出空间进行了一次旋转或反射。

一个经典的类比： 想象在二维空间中，将一个单位圆上的所有点进行线性变换。

• $V^T$ 找到了最适合拉伸的“主轴方向”，并将圆旋转，使主轴与标准坐标轴对齐。
• $\Sigma$ 沿着对齐后的坐标轴进行不同程度的拉伸或压缩，将单位圆变成一个椭圆。
• $U$ 再将这个对齐的椭圆旋转到它在目标空间中的最终位置。

所以，SVD的几何本质就是：任何线性变换都可以看作是“旋转-缩放-再旋转”的组合。奇异值 ${\sigma }_j$ 就是缩放的比例，而左右奇异向量构成的正交矩阵 $V$ 和 $U$ 则定义了这两个旋转。

---

四、主要性质

SVD的代数结构引出了一些非常重要的性质。

(1) SVD与 $A^{T}A$ 和 $A{A}^T$ 的特征值分解的深刻联系

这一点在我们证明SVD存在性时已经用到了，这里我们正式地总结一下。

• 对于 $A^{T}A$:

  $$\begin{array}{rlrl}{A}^{T}A& =(U\Sigma V^T{)}^T(U\Sigma V^T)& & \\ & =(V{\Sigma }^T{U}^T)(U\Sigma V^T)& & \\ & =V{\Sigma }^T(U^{T}U)\Sigma V^T& & \text{（矩阵乘法结合律）}\\ & =V{\Sigma }^{T}I\Sigma V^T& & \text{（U 是正交矩阵, UTU=I）}\\ & =V({\Sigma }^T\Sigma )V^T& & \end{array}$$

  这正是 $A^{T}A$ 的特征值分解。$V$ 是其特征向量矩阵，而对角矩阵 ${\Sigma }^T\Sigma$（这是一个 $n\times n$ 的方阵）的对角元是 $\{{\sigma }_1^2,{\sigma }_2^2,\dots ,{\sigma }_n^2\}$，即 $A^{T}A$ 的特征值。

• 对于 $A{A}^T$:

  $$\begin{array}{rlrl}A{A}^T& =(U\Sigma V^T)(U\Sigma V^T{)}^T& & \\ & =(U\Sigma V^T)(V{\Sigma }^T{U}^T)& & \\ & =U\Sigma (V^{T}V){\Sigma }^T{U}^T& & \text{（矩阵乘法结合律）}\\ & =U\Sigma I{\Sigma }^T{U}^T& & \text{（V 是正交矩阵, VTV=I）}\\ & =U(\Sigma {\Sigma }^T)U^T& & \end{array}$$

  这正是 $A{A}^T$ 的特征值分解。$U$ 是其特征向量矩阵，而对角矩阵 $\Sigma {\Sigma }^T$（这是一个 $m\times m$ 的方阵）的对角元是 $\{{\sigma }_1^2,\dots ,{\sigma }_n^2,0,\dots ,0\}$（如果 $m>n$），即 $A{A}^T$ 的特征值。

结论：矩阵 $A$ 的奇异值是 $A^{T}A$ 和 $A{A}^T$ 的非零特征值的平方根。$A$ 的右奇异向量是 $A^{T}A$ 的特征向量，$A$ 的左奇异向量是 $A{A}^T$ 的特征向量。这是计算SVD的标准算法基础。

(2) 左、右奇异向量与奇异值之间的关系

从 $A=U\Sigma V^T$ 可以直接推导出左右奇异向量之间的桥梁关系。

• 右乘 $V$ 得到 $AV=U\Sigma$。比较两边矩阵的第 $j$ 列：

  $$A{v}_j={\sigma }_j{u}_j,j=1,2,\dots ,n$$

  这表明，右奇异向量 $v_j$ 经过矩阵 $A$ 变换后，会恰好落在其对应的左奇异向量 $u_j$ 的方向上，并且长度被缩放了 ${\sigma }_j$ 倍。

• 类似地，从 $A^T=V{\Sigma }^T{U}^T$ 右乘 $U$ 得到 $A^{T}U=V{\Sigma }^T$。比较两边矩阵的第 $j$ 列：

  $$A^T{u}_j={\sigma }_j{v}_j,j=1,2,\dots ,m$$

  这表明，左奇异向量 $u_j$ 经过矩阵 $A^T$ 变换后，会恰好落在其对应的右奇异向量 $v_j$ 的方向上，长度同样被缩放了 ${\sigma }_j$ 倍。

这两个关系式完美地诠释了 $U$ 和 $V$ 分别是 $A$ 的输出空间和输入空间中的“特殊基向量”。

后续，我们学习一下奇异值分解的求解方法奇异值分解（二）：计算方法与例题。