奇异值分解（二）：计算方法与例题

从存在性到计算方法

在奇异值分解（一）：基本概念与性质中，我们通过构造法证明了任何矩阵 $A$ 都存在奇异值分解。这个证明过程本身就为我们指明了一条清晰的计算路径。而SVD的计算核心在于求解相关对称矩阵的特征值和特征向量。现在，我们将其系统化为一个具体的算法。

---

一、奇异值分解的计算步骤

给定一个 $m\times n$ 的实矩阵 $A$，其SVD $A=U\Sigma V^T$ 的计算步骤如下：

第一步：计算 $A^{T}A$ 的特征值和特征向量，以确定 $V$ 和 $\Sigma$

1. 构造对称矩阵 $W=A^{T}A$。这是一个 $n\times n$ 的方阵。
2. 求解 $W$ 的特征值。这需要解特征方程 $\det (W-\lambda I)=0$，得到 $n$ 个（非负的）特征值。
3. 将这些特征值按从大到小的顺序排列：${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n\ge 0$。
4. 计算奇异值 ${\sigma }_j=\sqrt{{\lambda }_j}$，并用它们构建 $m\times n$ 的矩形对角矩阵 $\Sigma$。
5. 对每一个特征值 ${\lambda }_j$，求解齐次线性方程组 $(W-{\lambda }_{j}I)x=0$，得到对应的特征向量。

第二步：标准化特征向量，构造正交矩阵 $V$

• 补充：基与正交

  • 基 (Basis)：在一个向量空间（如 ${\mathbb{R}}^n$）中，一组“最基本”的向量，通过它们的线性组合可以表示空间中的任何一个向量。这组向量必须是线性无关的。例如，二维平面中的 $(1,0)$ 和 $(0,1)$ 就是一组标准基。
  • 正交 (Orthogonal)：如果两个向量的点积为零（即 $v_i^T{v}_j=0$），我们称它们是正交的。几何上，这意味着它们互相垂直。
  • 标准正交基 (Orthonormal Basis)：这是一组特殊的基，其中所有基向量不仅相互正交，而且每个向量自身的长度（范数）都为1。

• 我们在第一步中得到的属于不同特征值的特征向量已经是相互正交的。我们需要将每个特征向量 单位化 (normalize)，即将其除以自身的长度，使其长度变为1。

• 将这些单位化后的标准正交特征向量作为列，就构成了 $n\times n$ 的正交矩阵 $V=[v_1,v_2,\dots ,v_n]$。

第三步：计算左奇异向量，构造正交矩阵 $U$

1. 确定 $U$ 的前 $r$ 列：设矩阵 $A$ 的秩为 $r$ (即有 $r$ 个非零奇异值)。对于 $j=1,\dots ,r$，我们利用上一部分推导出的关系式来计算左奇异向量 $u_j$：

   $$u_j=\frac{1}{{\sigma }_j}A{v}_j$$

   我们已经证明过，这样得到的 $\{u_1,\dots ,u_r\}$ 是一个标准正交向量集。

2. 确定 $U$ 的剩余 $m-r$ 列：如果 $r<m$，矩阵 $U$ 还有 $m-r$ 列需要确定。这些向量需要与 $\{u_1,\dots ,u_r\}$ 正交，且彼此之间也标准正交。

   • 补充：零空间 (Null Space)
     • 一个矩阵 $M$ 的零空间，记为 $N(M)$，是所有满足方程 $Mx=0$ 的向量 $x$ 的集合。零空间是一个向量子空间。
   • 理论上，这剩下的 $m-r$ 个左奇异向量 $\{u_{r+1},\dots ,u_m\}$ 构成了矩阵 $A^T$ 的零空间 $N(A^T)$ 的一组标准正交基。
   • 因此，我们求解齐次线性方程组 $A^{T}x=0$，找到其解空间的一组基，然后使用 格拉姆-施密特 (Gram-Schmidt) 正交化 方法将这组基转换为标准正交基。

3. 将这两部分向量合并，构成 $m\times m$ 的正交矩阵 $U=[u_1,\dots ,u_r,u_{r+1},\dots ,u_m]$。

第四步：得到最终分解

将计算出的 $U,\Sigma ,V$ 组合起来，即得到 $A=U\Sigma V^T$。

---

二、完整计算实例分析

问题： 试求矩阵 $A=\left[\begin{array}{cc}1& 1\\ 2& 2\\ 0& 0\end{array}\right]$ 的奇异值分解。

这是一个 $m=3,n=2$ 的矩阵。

解：

(1) 求 $A^{T}A$ 的特征值和特征向量

首先，计算 $A^{T}A$：

$$A^{T}A=\left[\begin{array}{ccc}1& 2& 0\\ 1& 2& 0\end{array}\right]\left[\begin{array}{cc}1& 1\\ 2& 2\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}(1\cdot 1+2\cdot 2+0\cdot 0)& (1\cdot 1+2\cdot 2+0\cdot 0)\\ (1\cdot 1+2\cdot 2+0\cdot 0)& (1\cdot 1+2\cdot 2+0\cdot 0)\end{array}\right]=\left[\begin{array}{cc}5& 5\\ 5& 5\end{array}\right]$$

接下来，求解其特征值。特征方程为 $\det (A^{T}A-\lambda I)=0$：

$$\det \left(\left[\begin{array}{cc}5& 5\\ 5& 5\end{array}\right]-\lambda \left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\right)=\det \left(\begin{array}{cc}5-\lambda & 5\\ 5& 5-\lambda \end{array}\right)=0$$ $$(5-\lambda )(5-\lambda )-5\cdot 5=0$$ $${\lambda }^2-10\lambda +25-25=0$$ $$\lambda (\lambda -10)=0$$

解得特征值为 ${\lambda }_1=10,{\lambda }_2=0$。

现在，我们求对应的特征向量：

• 对于 ${\lambda }_1=10$：

  $$(A^{T}A-10I)x=\left(\begin{array}{cc}5-10& 5\\ 5& 5-10\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{cc}-5& 5\\ 5& -5\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$$

  这得到方程 $-5x_1+5x_2=0$，即 $x_1=x_2$。我们可以取一个简单的特征向量为 $[1,1{]}^T$。

• 对于 ${\lambda }_2=0$：

  $$(A^{T}A-0I)x=\left(\begin{array}{cc}5& 5\\ 5& 5\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$$

  这得到方程 $5x_1+5x_2=0$，即 $x_1=-x_2$。我们可以取一个简单的特征向量为 $[1,-1{]}^T$。

(2) 构造矩阵 $V$ 和 $\Sigma$

• 构造 $\Sigma$: 奇异值为特征值的平方根：${\sigma }_1=\sqrt{{\lambda }_1}=\sqrt{10}$，${\sigma }_2=\sqrt{{\lambda }_2}=0$。 $\Sigma$ 是一个 $3\times 2$ 的矩形对角矩阵：

  $$\Sigma =\left[\begin{array}{cc}\sqrt{10}& 0\\ 0& 0\\ 0& 0\end{array}\right]$$

• 构造 $V$: 我们需要将特征向量单位化。 对于 ${\lambda }_1=10$ 的特征向量 $[1,1{]}^T$，其长度为 $\sqrt{1^2+1^2}=\sqrt{2}$。单位化后得到 $v_1=\left[\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right]$。 对于 ${\lambda }_2=0$ 的特征向量 $[1,-1{]}^T$，其长度为 $\sqrt{1^2+(-1{)}^2}=\sqrt{2}$。单位化后得到 $v_2=\left[\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\right]$。 将它们作为列，构成正交矩阵 $V$:

  $$V=\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ 1/\sqrt{2}& -1/\sqrt{2}\end{array}\right]$$

(3) 构造正交矩阵 $U$

矩阵 $A$ 的秩 $r=1$（因为只有一个非零奇异值）。

• 计算 $u_1$:

  $$\begin{array}{rl}{u}_1& =\frac{1}{{\sigma }_1}A{v}_1\\ & =\frac{1}{\sqrt{10}}\left[\begin{array}{cc}1& 1\\ 2& 2\\ 0& 0\end{array}\right]\left[\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right]\\ & =\frac{1}{\sqrt{10}}\left[\begin{array}{c}1/\sqrt{2}+1/\sqrt{2}\\ 2/\sqrt{2}+2/\sqrt{2}\\ 0\end{array}\right]\\ & =\frac{1}{\sqrt{10}}\left[\begin{array}{c}2/\sqrt{2}\\ 4/\sqrt{2}\\ 0\end{array}\right]=\frac{1}{\sqrt{10}}\left[\begin{array}{c}\sqrt{2}\\ 2\sqrt{2}\\ 0\end{array}\right]\\ & =\left[\begin{array}{c}\sqrt{2}/\sqrt{10}\\ 2\sqrt{2}/\sqrt{10}\\ 0\end{array}\right]=\left[\begin{array}{c}1/\sqrt{5}\\ 2/\sqrt{5}\\ 0\end{array}\right]\end{array}$$

• 计算 $u_2,u_3$: 我们需要求 $A^T$ 的零空间 $N(A^T)$ 的一组标准正交基。

  $$A^T=\left[\begin{array}{ccc}1& 2& 0\\ 1& 2& 0\end{array}\right]$$

  求解方程 $A^{T}x=0$：

  $$\left[\begin{array}{ccc}1& 2& 0\\ 1& 2& 0\end{array}\right]\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)⟹x_1+2x_2=0$$

  这意味着 $x_1=-2x_2$，$x_3$ 可以是任意值。该零空间是二维的。我们需要找到两个相互正交的基向量。

  1. 取 $x_2=1,x_3=0$，得到一个基向量 $w_2=[-2,1,0{]}^T$。
  2. 取 $x_3=1$，并使其与 $w_2$ 正交。一个简单的选择是 $x_2=0$，得到 $x_1=0$，即基向量 $w_3=[0,0,1{]}^T$。可以验证 $w_2^T{w}_3=0$。 现在将这两个基向量单位化：
  • $u_2=\frac{w_2}{\Vert w_2\Vert }=\frac{1}{\sqrt{(-2{)}^2+1^2+0^2}}[-2,1,0{]}^T=\left[\begin{array}{c}-2/\sqrt{5}\\ 1/\sqrt{5}\\ 0\end{array}\right]$。
  • $u_3=\frac{w_3}{\Vert w_3\Vert }=\frac{1}{\sqrt{0^2+0^2+1^2}}[0,0,1{]}^T=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$。

  注： 零空间的基不是唯一的。例如，取 $w_2^{\prime }=[2,-1,0{]}^T$ 也是一个合法的基向量，标准化后得到 $u_2^{\prime }=[2/\sqrt{5},-1/\sqrt{5},0{]}^T$。只要保证基是标准正交的，最终的SVD分解都是正确的。我们这里采用与书中最终答案一致的 $u_2$。

• 构造 $U$:

  $$U=[u_1,u_2,u_3]=\left[\begin{array}{ccc}1/\sqrt{5}& 2/\sqrt{5}& 0\\ 2/\sqrt{5}& -1/\sqrt{5}& 0\\ 0& 0& 1\end{array}\right]$$

(4) 得到矩阵A的奇异值分解

最后，我们将 $U,\Sigma ,V^T$ 组合起来：

$$V^T={\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ 1/\sqrt{2}& -1/\sqrt{2}\end{array}\right]}^T=\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ 1/\sqrt{2}& -1/\sqrt{2}\end{array}\right]$$

所以，最终的SVD分解是：

$$A=U\Sigma V^T=\left[\begin{array}{ccc}1/\sqrt{5}& 2/\sqrt{5}& 0\\ 2/\sqrt{5}& -1/\sqrt{5}& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{cc}\sqrt{10}& 0\\ 0& 0\\ 0& 0\end{array}\right]\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ 1/\sqrt{2}& -1/\sqrt{2}\end{array}\right]$$

---

关于实际计算的补充说明

正如《机器学习方法》所述，上面的基于特征值分解的计算方法主要是为了理论阐述和教学目的。在实际的大规模计算中，直接计算 $A^{T}A$ 会存在数值不稳定的风险（例如，如果 $A$ 的某些奇异值非常小，那么在 $A^{T}A$ 中它们的平方会变得更小，可能导致精度损失）。

因此，实际应用中的SVD算法，如在NumPy或PyTorch库中实现的，通常采用更稳定、更高效的迭代方法，例如基于Householder变换或QR分解的变体，它们直接在矩阵 $A$ 上操作，避免了显式构造 $A^{T}A$。