不经意间推导出奇异值分解

# 数学中的联系：从头推导 SVD 来源：https://stillthinking.net/posts/connections-in-math-svd/ 免责声明：本文未使用任何 AI 工具撰写。任何错误、别扭的句子和奇怪的跑题内容，都是 100% 纯天然、散养、手工制作的。 ## 到底怎么才能真正学会东西？ 长久以来，我一直在问自己，真正理解或掌握某个数学概念意味着什么。我认为这可以延伸到其他领域，但数学的许多概念往往与日常生活特别疏远，至少对我来说，很难建立起直观而自然的理解——那种能让你抓住概念的基础结构，以后无需咨询或只需少量咨询就能自己重新构建细节的理解。 我有过几次真正抓住某个领域一般性结构的感受，让我能够仅凭当前的理解来自我表达或推导事实。一个很好的例子是我第一次接触实分析。起初它看起来非常混乱和困难，但过了一段时间，你抓住了主要概念的结构，基本上就能自己运用这些概念了。 但有一件事花了我太长时间才明白：传统的数学书籍往往无法给你一条能够抓住结构或更直观、更自然地理解概念（以便以后能重新构建它）的路径。这是因为大多数数学书都是以最终形式化的版本来呈现数学，但它们隐藏了达到这些结果所走过的路：那条路往往是杂乱、实验性、试错和尝试性的。 本博客假设你已经具备基础的数学知识。从头教起并不现实，但我的目标是写下一些帮助我理解概念的连接点。 ## 从某处开始 我选择从线性代数开始。它是最实用、最易入门的数学领域之一。当我被引入线性代数的核心概念“奇异值分解”时，我花了不少时间才真正理解它是什么。我认为大多数书未能简单解释它的原因，仅仅是因为它们通常从正式陈述的最终结论开始，这对读者来说毫无意义。我认为引入动机至关重要，即说明它最初为何被创造出来。应用数学中的大多数事物都源于某人试图解决的特定问题。 线性代数是一个很好的起点，不仅因为它比更高级的非线性领域简单，还因为它与许多其他领域相连，如微积分、信息论、图像处理、机器学习等等。它有点像基础或中心领域，尽管我认为无论你从哪儿开始，如果深入挖掘，最终都会连接到其他领域——而在线性代数中这一点尤为明显。 让我们自然地引出 SVD，甚至不用刻意瞄准它。 线性变换的**矩阵**可以基于所选的输入和输出基，以不同方式写出同一个线性变换。为了看清这一点，我们刻意选取一个简单的线性映射——让 x 轴拉伸 3 倍，y 轴保持不变： \[ \mathbf{A}(x, y) = (3x,\ y) \] 在**标准基**下，它的矩阵直接读取出基向量落在哪里： \[ M = \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix} \] 再清晰不过了：“拉伸一个轴”。 现在用**倾斜基**（非标准正交基）描述**同一个映射**： \[ P = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}, \qquad P^{-1} = \begin{pmatrix} 2 & -1 \\ -1 & 1 \end{pmatrix} \] 同一个变换在这个基下的矩阵是 \(P^{-1} M P\)： \[ P^{-1} M P = \begin{pmatrix} 2 & -1 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} = \begin{pmatrix} 5 & 4 \\ -2 & -1 \end{pmatrix} \] 同样的变换。对每个实际向量的作用相同。但它现在看起来像是缩放、剪切和符号翻转的任意纠缠——你绝对猜不到它只是“把 x 拉伸 3 倍”。 > 复杂性从来不在映射本身，而在基。 有时我们可以**对角化**一个矩阵，只需选一个新基，使得 \(\mathbf{A}\) 的矩阵变成对角阵（这只有在 \(\mathbf{A}\) 具有特征向量基时才可行，目前我们暂不证明这一点）。当然，并非所有线性变换都有特征向量组成的基。事实上，有些线性变换甚至不是方阵（例如输入维度和输出维度不同）。对于输出维度和输入维度不同的线性变换，我们甚至无法谈论特征向量，因为特征向量在尺度上保持不变，这显然要求输入和输出维度相同。 当我们**能够**对角化一个矩阵时，一件有趣的事情发生了：我们可以清楚地看到，线性变换本身基本上就是一个简单的非均匀缩放，只是由于表示矩阵所选的基而伪装得更复杂（与之前我们演示的操作相反——我们曾展示过，一个简单缩放可以用更复杂的矩阵形式表示）。因此，我们将可对角化线性变换 \(\mathbf{A}\) 的矩阵 \(M\) 写成： \[ M = P^{-1} D P \] 那么 \(M\) 就**相似**于一个对角阵。所以，这个可能很复杂的 \(M\)，本质上只是矩阵对角线上的一些数（其余都是零）加上一个特殊的基变换矩阵 \(\mathbf{P}\)。这对于在计算机中存储和高效进行矩阵乘法来说非常理想。我们可以将数据转换到 \(\mathbf{P}\) 的参考系一次，然后用对角阵进行数百万次矩阵乘法（很容易），最后再用 \(\mathbf{P}^{-1}\) 转换回原框架。这种简化之所以可能，是因为我们从线性变换 \(\mathbf{A}\) 中提取出了**结构**。 什么时候不能对角化一个矩阵呢？如果一个可对角化矩阵只是在某个特殊坐标框架下的伪装缩放，那么当我们无法对角化时，意味着该线性变换不仅仅是伪装缩放（实际上，这等价于 \(\mathbf{A}\) 不能由特征向量基构成——试试自己证明这一点）。例如，如果 \(\mathbf{A}\) 是二维旋转，它就没有两个独立实特征向量（它根本没有实特征向量；旋转会移动平面内的每一个方向！）。如果 \(\mathbf{A}\) 是二维剪切，类似地，它也一定不能被对角化。 那么，我们能否像对待可对角化线性变换那样，从任意线性变换中提取结构呢？如果可以，我们可能会获得一些好处，就像对角阵带来的好处一样…… 直觉上，我们可以看看一个 \(N\) 维单位球体经过一般线性变换会发生什么：它可能是非单射的，即某些方向会被压缩为 0（球体会塌成圆盘）；它可能会以任意倍数拉伸其他方向（这样球体或圆盘就会变成椭球体或椭圆）；它可能通过任意轴以任意角度旋转其他方向；也可能将球体剪切到其他方向（剪切后的球体仍然是一个旋转过的椭球体）。这个简单的事实可以写成如下形式： \[ s_i\,\mathbf{u}_i = \mathbf{A}\mathbf{v}_i \] 其中 \(s_i\) 是一个**标量**——拉伸因子——而 \(\mathbf{u}_i\) 是一个单位输出方向。就是这样。我们分离了 \(\mathbf{u}_i\) 和 \(\mathbf{v}_i\)，不再要求它们是特征向量；它们只是任意向量。上面的表达式并没有引入新的事实，它只是任何线性变换都会发生的事情，但它确实抓住了我们的感觉：单位球面会以某种方式映射为旋转后的椭球体，只要你将 \(s_i\) 视为缩放因子、将 \(\mathbf{u}_i\) 视为新的旋转方向。 我们现在的感觉是，一个线性变换可能执行多种操作（旋转、剪切、缩放），类似于我们对角化的情形，这些操作有可能被分解并隔离出来，从而在看似复杂的变换中揭示出一些更简单的结构。 正如我们之前看到的，倾斜基不适合表示线性变换的矩阵，因为它们会混合坐标基向量：每个基向量在其他基向量上的投影非零。这里很自然的下一步是看看当基 \(\mathbf{u}_i\) 和 \(\mathbf{v}_i\) 是标准正交时会发生什么。我们能否总是要求 \(\mathbf{u}_i\) 和 \(\mathbf{v}_i\) 是标准正交的呢？我们会看到可以，这是一个有趣且简洁的事实。 看一下我们在要求什么。对于**输出**向量是标准正交的： \[ \tag{1} i \neq j \implies \left<\mathbf{A}\mathbf{v}_i, \mathbf{A} \mathbf{v}_j\right> = 0, \qquad \left<\mathbf{A}\mathbf{v}_i, \mathbf{A} \mathbf{v}_i\right> = 1 \] 同时我们希望**输入**向量也是标准正交的： \[ \tag{2} i \neq j \implies \left<\mathbf{v}_i, \mathbf{v}_j \right> = 0, \qquad \left<\mathbf{v}_i, \mathbf{v}_i\right> = 1 \] 现在，一件非常有趣的事情发生了。将输出的内积改写，把 \(\mathbf{A}\) 移到另一边（利用 \(\left<\mathbf{A}x, y\right> = \left<x, \mathbf{A}^T y\right>\)）： \[ \tag{1.1} \left<\mathbf{A}\mathbf{v}_i, \mathbf{A}\mathbf{v}_j\right> = \left<\mathbf{v}_i,\ \mathbf{A}^T\mathbf{A}\,\mathbf{v}_j\right> = \mathbf{v}_i^{T} \mathbf{A}^T \mathbf{A}\, \mathbf{v}_j \] 到目前为止，没有什么新东西——只是重写同一个表达式。但现在 \(\mathbf{A}^T \mathbf{A}\) 明确出现了，它是一个对称矩阵！取任意（可能非方）矩阵 \(C\)，组成 \(C^T C\)，得到的一定是对称矩阵。这里一个非常重要的事实是：对称矩阵**总是具有标准正交的特征向量基**（这就是谱定理）。所以让我们**选择** \(\mathbf{v}_i\) 正好为 \(\mathbf{A}^T\mathbf{A}\) 的标准正交特征向量。这立即就得到了 (2)，即输入的标准正交性，不需要额外条件。但关键是，这个选择也自动给出了 (1)，即输出的正交性。看看 \(i\neq j\) 的非对角情况。由于 \(\mathbf{v}_j\) 是 \(\mathbf{A}^T\mathbf{A}\) 的特征向量，有 \(\mathbf{A}^T\mathbf{A}\,\mathbf{v}_j = \lambda_j \mathbf{v}_j\)，所以： \[ \tag{1.2} i \neq j \implies \left<\mathbf{A}\mathbf{v}_i, \mathbf{A}\mathbf{v}_j\right> = \mathbf{v}_i^{T} \mathbf{A}^T \mathbf{A}\, \mathbf{v}_j = \lambda_j\, \mathbf{v}_i^{T} \mathbf{v}_j = \lambda_j \cdot 0 = 0 \] 输出正交的原因正是输入是 \(\mathbf{A}^T\mathbf{A}\) 的正交特征向量。我们不需要单独要求输出正交性——它自动从输入的选择中推出。而这些输出的长度正是缩放因子： \[ \left<\mathbf{A}\mathbf{v}_i, \mathbf{A}\mathbf{v}_i\right> = \lambda_i \] 所以 \[ s_i = \|\mathbf{A}\mathbf{v}_i\| = \sqrt{\lambda_i} \] 然后归一化得到标准正交输出方向 \(\mathbf{u}_i = \mathbf{A}\mathbf{v}_i / s_i\)。 因此，一般来说，我们无法找到一个标准正交基使得 \(\mathbf{A}\) 本身对角化——但我们可以**总是**为对称矩阵 \(\mathbf{A}^T\mathbf{A}\) 找到一个标准正交基，而这正是我们一直在寻找的输入基。 ## \(\mathbf{A}\) 的秩与 \(\mathbf{A}^T\mathbf{A}\) 的秩 另一个值得注意的事实是，\(\mathbf{A}\) 的秩与 \(\mathbf{A}^T \mathbf{A}\) 的秩**相同**，稍后会用到，我们先证明它。 考虑 \(\mathbf{A}: \mathbb{R}^N \to \mathbb{R}^M\)。由秩-零化度定理，\(\operatorname{rank}(\mathbf{A}) = N - \dim \operatorname{Ker}(\mathbf{A})\)，其中 \(N\) 是**输入**维度（核存在于输入空间 \(\mathbb{R}^N\) 中）。现在注意 \(\mathbf{A}^T\mathbf{A}\) 是 \(N\times N\)（因为 \(\mathbf{A}^T\) 是 \(N\times M\)，\(\mathbf{A}\) 是 \(M\times N\)），所以它也映射 \(\mathbb{R}^N \to \mathbb{R}^N\)，同样的秩-零化度定理给出 \[ \operatorname{rank}(\mathbf{A}^T\mathbf{A}) = N - \dim \operatorname{Ker}(\mathbf{A}^T\mathbf{A}) \] 两个映射的定义域维度都是 \(N\)，所以要证明秩相等，只需证明它们的核相等： \[ \operatorname{Ker}(\mathbf{A}) = \operatorname{Ker}(\mathbf{A}^T\mathbf{A}) \] **证明**： (1) 首先，\(\operatorname{Ker}(\mathbf{A}) \subseteq \operatorname{Ker}(\mathbf{A}^T\mathbf{A})\)——容易的方向： \[ \mathbf{v} \in \operatorname{Ker}(\mathbf{A}) \implies \mathbf{A}\mathbf{v} = 0 \implies \mathbf{A}^T(\mathbf{A}\mathbf{v}) = 0 \implies \mathbf{v} \in \operatorname{Ker}(\mathbf{A}^T\mathbf{A}). \] (2) 现在证 \(\operatorname{Ker}(\mathbf{A}^T\mathbf{A}) \subseteq \operatorname{Ker}(\mathbf{A})\)——不那么显然的方向。起初似乎无法阻止一个**不在** \(\mathbf{A}\) 核中的向量 \(\mathbf{v}\) 使得 \(\mathbf{A}\mathbf{v}\) 落在 \(\mathbf{A}^T\) 的核中，从而即使 \(\mathbf{A}\mathbf{v} \neq 0\) 也有 \(\mathbf{A}^T\mathbf{A}\mathbf{v} = 0\)。但结果证明这不会发生。假设 \(\mathbf{A}^T\mathbf{A}\mathbf{v} = 0\)，则 \(\mathbf{A}^T(\mathbf{A}\mathbf{v}) = 0\)，所以 \(\mathbf{A}\mathbf{v} \in \operatorname{Ker}(\mathbf{A}^T)\)。有两种情况： - 要么 \(\mathbf{A}\mathbf{v} = 0\)，则 \(\mathbf{v} \in \operatorname{Ker}(\mathbf{A})\)，得证； - 要么 \(\mathbf{A}\mathbf{v} \neq 0\)，这将使得**非零**向量同时属于 \(\operatorname{Im}(\mathbf{A})\)（因为 \(\mathbf{A}\mathbf{v}\) 本就是 \(\mathbf{A}\) 的输出）和 \(\operatorname{Ker}(\mathbf{A}^T)\)。但第二种情况是不可能的，因为 \[ \operatorname{Im}(\mathbf{A})^\perp = \operatorname{Ker}(\mathbf{A}^T) \implies \operatorname{Im}(\mathbf{A}) \cap \operatorname{Ker}(\mathbf{A}^T) = \{\mathbf{0}\} \] （一个子空间与其正交补只共享零向量）。所以 \(\mathbf{A}\mathbf{v} = 0\)，即 \(\mathbf{v} \in \operatorname{Ker}(\mathbf{A})\)。∎ 证明第二个方向还有一种更简洁、自包含的方法，直接利用内积的正定性： \[ \mathbf{A}^T\mathbf{A}\,\mathbf{v} = 0 \implies \mathbf{v}^T\mathbf{A}^T\mathbf{A}\,\mathbf{v} = 0 \implies (\mathbf{A}\mathbf{v})^T(\mathbf{A}\mathbf{v}) = 0 \implies \|\mathbf{A}\mathbf{v}\|^2 = 0 \implies \mathbf{A}\mathbf{v} = 0. \] 最后一步正是正定性：只有零向量的长度为零。两种方法均可；第一种联系了四个基本子空间，第二种直接指向内积。 在组装任何东西之前，我们先暂停一下，列出我们现在知道的关于**任意**线性映射 \(\mathbf{A}\)（一个 \(M\times N\) 矩阵）的信息。我们最初的目标是对一般映射做类似于对角化的事。