SVD 分解

1. SVD 分解基础

$a.$ 引入

我们前面介绍了矩阵的对角化分解：

$$A = X\Lambda X^{-1}$$

但是这种分解有下面的问题：

1. 正交性问题：对角化分解中的特征向量矩阵 $X$ 通常不是正交的（除非 $A$ 是对称矩阵）。这使得计算和几何解释变得复杂。
2. 存在性问题：不是所有矩阵都有足够的特征向量来对角化。
3. 形状问题：特征值分解只适用于方阵。

而 SVD 分解则不存在这些问题：它适用于任何形状的长方形矩阵、并且分解得到的向量矩阵是正交的。

$b.$ 概述

SVD 实际上是在为矩阵 $A$ 的四个基本子空间寻找最佳的“坐标轴”（基向量）。假设 $A$ 的秩为 $r$，并且：

• 输入空间的 $R^n$ 的基：$v_1, \dots, v_r$ 构成了行空间的标准正交基，$v_{r+1}, \dots, v_n$ 构成了零空间 $N(A)$ 的标准正交基。

• 输出空间 $R^m$ 的基：$u_1, \dots, u_r$ 构成了列空间的标准正交基，$u_{r+1}, \dots, u_m$ 构成了左零空间 $N(A^T)$ 的标准正交基。

则 SVD 分解告诉我们，矩阵 $A$ 的作用是将输入空间的基向量 $v_i$ 映射到输出空间的基向量 $u_i$，并进行伸缩：

$$A v_i = \sigma_i u_i$$

• 对于前 $r$ 个向量：$v_i$ 变成了 $u_i$，长度伸缩了 $\sigma_i$ 倍。
• 对于剩下的向量（零空间）：$A v_i = 0$（相当于 $\sigma = 0$）。

这个式子也可以看作对 $A$ 的积木式拆分：

$$A = \sigma_i u_i v_i ^ T$$

SVD 把 $A$ 拆分成了 $r$ 个秩一矩阵的和，$\sigma_i$ 越大，说明这个秩一矩阵的重要性越大。

这个式子转化为矩阵形式如下：对前 $r$ 个非0奇异值：

$$A \cdot V_r = U_r \cdot \Sigma_r$$

其中 $V_r$ 是 $n \times r$ 矩阵（$r$ 个行空间基向量）, $U_r$ 是 $m \times r$ 矩阵（$r$ 个列空间基向量）,$\Sigma_r$ 是 $r \times r$ 的对角矩阵（存放 $\sigma_1 \dots \sigma_r$）。

为了让 $U$ 和 $V$ 变成完美的方形正交矩阵，我们需要把零空间和左零空间的基向量加进去，即进行补零：

• $\Sigma$ 变成 $m \times n$ 的大矩阵，多出来的部分全是 0。
• $V$ 变成 $n \times n$ 方阵，$U$ 变成 $m \times m$ 方阵。

得：

$$AV = U\Sigma$$

因为 $V$ 是正交矩阵，所以 $V^{-1} = V^T$。方程两侧同乘 $V^{-1}$：

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

SVD 分解成功找到了两组特殊的正交网格 $v$ 和 $u$：把 $v$ 网格输入进矩阵 $A$ 后，它输出的恰好是没有任何扭曲、只有拉伸（或压缩）的 $u$ 网格。

$c.$ 证明

我们证明对于任意矩阵 $A$，都存在 $A = U \Sigma V^T$。

我们从对称矩阵 $AA^T$ 入手来进行证明。带入式子得：

$$A^T A = (U \Sigma V^T)^T (U \Sigma V^T) = V \Sigma^T \underbrace{U^T U}_{I} \Sigma V^T = V (\Sigma^T \Sigma) V^T$$

因为 $\Sigma$ 是对角阵，所以 $\Sigma^T \Sigma = \Sigma^2$（对角线元素变成了 $\sigma^2$），于是：

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

这正是对称矩阵的对角化公式，其中：

• $V$ 是矩阵 $A^T A$ 的特征向量矩阵。因为 $A^T A$ 是对称矩阵，所以它的特征向量 $V$ 必然是相互正交的（这是对称矩阵的性质）。
• $\Sigma^2$ 是 $A^T A$ 的特征值矩阵，奇异值 $\sigma_i = \sqrt{\lambda_i(A^T A)}$。

下面只需要证明使用 SVD 得到的输出空间向量 $u$ 也是互相垂直的。使用 SVD 分解的定义式解出 $u$：

$$A v_i = \sigma_i u_i \quad \Rightarrow \quad u_i = \frac{A v_i}{\sigma_i}$$

我们计算 $u$ 中任意两向量点积 $(u_i)^T u_j$：

$$(u_i)^T u_j = \left( \frac{A v_i}{\sigma_i} \right)^T \left( \frac{A v_j}{\sigma_j} \right) = \frac{v_i^T A^T A v_j}{\sigma_i \sigma_j}$$

由于 $v_j$ 是 $A^T A$ 的特征向量，所以 $A^T A v_j = \sigma_j^2 v_j$，于是有：

$$\text{LHS} = \frac{v_i^T (\sigma_j^2 v_j)}{\sigma_i \sigma_j} = \frac{\sigma_j^2}{\sigma_i \sigma_j} (v_i^T v_j)$$

由于 $v_i$ 彼此正交，因此上式结果为0，从而证毕。

$d.$ 具体计算

给定：

$$A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$$

按照如下步骤计算其 SVD 分解：

1. 计算 $A^TA$：

$$A^T A = \begin{bmatrix} 3 & 4 \\ 0 & 5 \end{bmatrix} \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}$$

2. 计算特征值：特征值多项式 $\lambda^2 - \text{trace} \cdot \lambda + \det = \lambda^2 - 50\lambda + 225 = 0$，解得：

$$\lambda_1 = 45, \quad \lambda_2 = 5$$

由前面推导，奇异值是特征值的平方根：

$$\sigma_1 = \sqrt{45} = 3\sqrt{5}, \quad \sigma_2 = \sqrt{5}$$

3. 求右奇异向量 $V$：求 $A^T A$ 对应于 $\lambda_1=45$ 的特征向量：

$$(A^T A - 45I)x = 0 \Rightarrow \begin{bmatrix} -20 & 20 \\ 20 & -20 \end{bmatrix} x = 0$$

得到 $x = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$。标准化后得到 $v_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}$。

同理，求对应于 $\lambda_2=5$ 的特征向量，得到 $v_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} -1 \\ 1 \end{bmatrix}$。 所以矩阵 $V = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}$。

4. 求左奇异向量 $U$：直接利用 $u_i = \frac{A v_i}{\sigma_i}$ 计算特征向量：计算 $u_1$：

$$A v_1 = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 3 \\ 9 \end{bmatrix}$$ $$u_1 = \frac{A v_1}{\sigma_1} = \frac{1}{\sqrt{45}} \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} 3 \\ 9 \end{bmatrix} = \frac{1}{\sqrt{90}} \begin{bmatrix} 3 \\ 9 \end{bmatrix} = \frac{1}{3\sqrt{10}} \begin{bmatrix} 3 \\ 9 \end{bmatrix} = \frac{1}{\sqrt{10}} \begin{bmatrix} 1 \\ 3 \end{bmatrix}$$

同理计算可得 $u_2 = \frac{1}{\sqrt{10}} \begin{bmatrix} -3 \\ 1 \end{bmatrix}$。所以矩阵 $U = \frac{1}{\sqrt{10}} \begin{bmatrix} 1 & -3 \\ 3 & 1 \end{bmatrix}$。

下面展示两个特殊情况的处理方法：

• 如果特征值为 0，右奇异向量仍然正常计算，左奇异向量需要找一个满足下面要求的向量：
  1. 与所有非零奇异值对应的 $u_j$ 正交
  2. 与其他 $\sigma=0$ 对应的 $u_k$ 正交（如果有多个零奇异值）
  3. 是单位向量

例如给定：

$$A=\begin{bmatrix} 0 & 1 & 0 & 0\\[4pt] 0 & 0 & 2 & 0\\[4pt] 0 & 0 & 0 & 3\\[4pt] 0 & 0 & 0 & 0 \end{bmatrix}$$

容易计算出右奇异矩阵

$$V = \begin{bmatrix} 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix}$$

与前三个特征值不为 0 时的左奇异向量：

1. $u_1 = \dfrac{1}{3} A v_1 = \dfrac{1}{3} A e_4 = \dfrac{1}{3}\begin{pmatrix}0 & 0 & 3 & 0\end{pmatrix}^T = \begin{pmatrix}0 & 0 & 1 & 0\end{pmatrix}^T$
2. $u_2 = \dfrac{1}{2} A v_2 = \dfrac{1}{2} A e_3 = \dfrac{1}{2}\begin{pmatrix}0 & 2 & 0 & 0\end{pmatrix}^T = \begin{pmatrix}0 & 1 & 0 & 0\end{pmatrix}^T$
3. $u_3 = 1\cdot A v_3 = A v_3 = A e_2 = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix}^T$

对于 $\sigma_4=0$，需要找一个与 $u_1$，$u_2$，$u_3$ 正交的单位向量，显然 $e_4 = (0,0,0,1)^T$ 符合条件。

• 如果矩阵不是满秩的，或者是长方形的，我们可能只找到了 $r$ 个 $u$ 和 $v$。根据前面的，对于剩下的 $v$：从 $A$ 的零空间里找一组正交基填进去；对于剩下的 $u$：从 $A^T$ 的零空间里找一组正交基填进去。例如给定下面的秩一矩阵：

$$A=\begin{bmatrix}1 & 2 & 0\\[4pt] 0 & 0 & 0\end{bmatrix}.$$

有：

$$A^T A= \begin{bmatrix} 1 & 2 & 0\\[4pt] 2 & 4 & 0\\[4pt] 0 & 0 & 0 \end{bmatrix}$$

特征值为$\sigma_1=\sqrt{5},\quad \sigma_2=\sigma_3=0$。先计算出下面的右奇异向量与左奇异向量：

$$v_1=\frac{1}{\sqrt{5}}\begin{bmatrix}1\\[4pt]2\\[4pt]0\end{bmatrix},\quad u_1=\begin{bmatrix}1\\[4pt]0\end{bmatrix}$$

矩阵秩为 $r=1$，但 $A$ 是 $2\times3$，我们需要完整的正交矩阵 $V\in\mathbb R^{3\times3}$ 和 $U\in\mathbb R^{2\times2}$。对于剩余的向量按规则填充：

• 对剩余的 $v$，求解 $A x=0$：

$$\begin{bmatrix}1 & 2 & 0\\ 0 & 0 & 0\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix} \Longrightarrow x_1+2x_2=0.$$

容易得零空间单位正交基：

$$v_2=\frac{1}{\sqrt5}\begin{bmatrix}-2\\[4pt]1\\[4pt]0\end{bmatrix},\qquad v_3=\begin{bmatrix}0\\[4pt]0\\[4pt]1\end{bmatrix}.$$

• 对剩余的 $u$，求解 $A^T x=0$：

$$A^T=\begin{bmatrix}1 & 0\\[4pt]2 & 0\\[4pt]0 & 0\end{bmatrix},\quad A^T y=0 \Longrightarrow \begin{bmatrix}y_1\\2y_1\\0\end{bmatrix}=0 \Rightarrow y_1=0.$$

得：

$$u_2=\begin{bmatrix}0\\[4pt]1\end{bmatrix}.$$

于是：

$$A = U\Sigma V^{T} = \begin{bmatrix}1 & 0\\[4pt]0 & 1\end{bmatrix} \begin{bmatrix}\sqrt{5} & 0 & 0\\[4pt]0 & 0 & 0\end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{5}} & -\frac{2}{\sqrt{5}} & 0\\[6pt] \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} & 0\\[6pt] 0 & 0 & 1 \end{bmatrix}^{T}$$

2. SVD 分解的另一个理解角度

我们可以从下面这个新的角度来理解 SVD 分解。考虑下面的瑞利商问题：对于对称矩阵 $S$（如 $A^T A$），我们想找一个向量 $x$，使得 $x$ 经过 $S$ 变换后“拉伸”得最长。也即最大化下面的式子：

$$r(x) = \frac{x^T S x}{x^T x}$$

在微积分中，这个比值的最大值就是 $S$ 的最大特征值 $\lambda_1$，而对应的 $x$ 就是特征向量 $q_1$。

对应到 SVD，对于矩阵 $A$，我们要找一个 $x$（也就是 $v$），使得 $Ax$ 最长（即 $||Ax||$ 最大）：

$$\max \frac{||Ax||}{||x||}$$

这等价于最大化 $\frac{||Ax||^2}{||x||^2} = \frac{x^T A^T A x}{x^T x}$。这正是前面 $S = A^T A$ 的瑞利商问题。

3. PCA

$a.$ 引入

假设我们有 1000 个数据样本并需要分析它们。我们按照以下步骤进行分析：

1. 把数据的平均值减掉、进行中心化。从几何意义上，这将1000 个散点的中心（重心）挪到了坐标原点。
2. 假设这一些数据大致排成了一条直线形状，我们希望找到这条直线，该怎么找到呢？

我们可以从下面两个角度来考虑这个问题。首先是最大化方差视角：我们希望沿着能让点的投影最长的那个方向投影，这样投影出来的点拉得最开，保留了点与点之间最大的差异（方差）。更准确地讲，我们希望所有点的投影长度的平方和最大：

$$\text{Maximize} \sum_{j=1}^n |a_j^T u|^2$$

将这个求和写成矩阵形式：

$$\sum (a_j^T u)^2 = ||A^T u||^2 = u^T A A^T u$$

这正是瑞利商问题（由于归一化，向量的长度为 1、没有分母）！这个方向正是 $AA^T$ 的最大特征向量，也即 SVD 中 $u_1$。

另一个角度是最小化垂直距离视角。我们通常使用的最小二乘拟合直线是让点到直线的垂直（竖直 $y$ 轴）距离最小。而PCA 是正交回归（Orthogonal Regression）。它找的是让点到直线的**几何垂直距离（最短连线）**最小。

这其实就是对前面的视角的几何描述。

对于每一个数据点 $a_j$，它到原点的距离平方（斜边）是固定的，记为 $||a_j||^2$。我们可以把这个向量分解为两个分量（也即直角三角形的两条直角边）：

1. 沿直线的投影：$|a_j^T u_1|^2$（这就是上面说的“方差”）。
2. 垂直于直线的距离：$|a_j^T u_2|^2$（这就是“误差”）。

根据勾股定理有：

$$\underbrace{||a_j||^2}_{\text{固定常数}} = \underbrace{|a_j^T u_1|^2}_{\text{投影长度平方}} + \underbrace{|a_j^T u_2|^2}_{\text{垂直距离平方}}$$

我们希望垂直距离平方这一项最小，等价于希望投影长度平方这一项最大，这正是 SVD 所做的。我们再一次回到了 SVD。

因此可以说：PCA 其实就是对数据矩阵 $A$ 做 SVD。

$b.$ 相关概念

在 SVD 中有：

$$A = \sigma_1 u_1 v_1^T + \sigma_2 u_2 v_2^T + \dots$$

而在 PCA 中，这些项有了新的名字：

• 总方差$T$：数据的总信息量。等于所有奇异值的平方和 $\sum \sigma_i^2$。
• 主成分$u$：
  • $u_1$（第一主成分）：这是 $S$ 的最大特征向量，它解释了最大的方差占比 $\frac{\sigma_1^2}{T}$。
  • $u_2$（第二主成分）：垂直于 $u_1$ 的方向，解释了次要的方差。
• 有效秩$R$：如果 $\sigma_1$ 很大，而 $\sigma_2$ 很小（接近 0），说明数据点虽然在二维平面上，但实际上几乎全落在一条线上。这时我们可以说数据的有效秩是 1。我们只需要保留 $u_1$ 即可，这样就实现了降维。

同时为了量化数据的分布，我们引入协方差矩阵 $S$：

$S = \frac{A A^T}{n-1}$

$S$ 的元素含义如下：

• 对角线元素 $S_{ii}$：方差，代表这一行数据自己本身散得有多开。
• 非对角线元素 $(S_{ij})$：协方差，代表两个变量之间的关系。