投影

高中的时候就学过，向量 \(\boldsymbol b\) 在 \(\boldsymbol a\) 上的投影为 \[ \boldsymbol p = \frac{\boldsymbol a^{\mathrm T}\boldsymbol b}{\boldsymbol a^{\mathrm T}\boldsymbol a} \cdot \boldsymbol a \] 当时推导主要利用了点积的几何意义 $a b = |a||b|$。在代数意义上上式是怎么推导的呢？

其实也不难：注意到 \(\boldsymbol b\) 和其投影 \(\boldsymbol p\) 的差一定是垂直于基向量 \(\boldsymbol a\) 的。因为 \(\boldsymbol p\) 与 \(\boldsymbol a\) 平行，设 \(\boldsymbol p = x\boldsymbol a\) \[ \begin{aligned} \boldsymbol a^{\mathrm T}\left(\boldsymbol b - x\boldsymbol a\right) &= 0 \\ \Rightarrow \boldsymbol a^{\mathrm T}x\boldsymbol a &= \boldsymbol a^{\mathrm T}\boldsymbol b \\ \Rightarrow x\boldsymbol a^{\mathrm T}\boldsymbol a &= \boldsymbol a^{\mathrm T}\boldsymbol b \\ \Rightarrow x &= \frac{\boldsymbol a^{\mathrm T}\boldsymbol b}{\boldsymbol a^{\mathrm T}\boldsymbol a} \end{aligned} \] 我们就得到了一开始的结论。如果把 \(\boldsymbol a\) 写到左边（因为是向量的实数积所以可以交换） \[ p = \boldsymbol a\cdot \frac{\boldsymbol a^{\mathrm T}\boldsymbol b}{\boldsymbol a^{\mathrm T}\boldsymbol a} = \frac{\boldsymbol a\boldsymbol a^{\mathrm T}}{\boldsymbol a^{\mathrm T}\boldsymbol a}\boldsymbol b \] 我们这下看清楚了：将 \(\boldsymbol b\) 转变为其在 \(\boldsymbol a\) 上的投影的是一个矩阵！这个矩阵 \(P = \frac{\boldsymbol a\boldsymbol a^{\mathrm T}}{\boldsymbol a^{\mathrm T}\boldsymbol a}\) 被称为投影矩阵。

代数推导和投影矩阵有啥用？它们可以让我们把投影从投影到一个向量推广到投影到向量空间。

考虑如何把一个向量 \(\boldsymbol b\) 投影到矩阵 \(A = \begin{bmatrix} \boldsymbol {a_1} &\boldsymbol {a_2} &\cdots &\boldsymbol {a_n}\end{bmatrix}\) 的列空间上（假设 \(A\) 的列向量线性无关）。我们一样考虑 \(\boldsymbol b\) 与 \(\boldsymbol p\) 的差，其一定垂直于 \(C(A)\)，自然也垂直于 \(\boldsymbol {a_1} \cdots \boldsymbol {a_n}\)，于是就有： \[ \boldsymbol {a_k} ^{\mathrm T}\left(\boldsymbol b - \boldsymbol p\right) = 0, \quad k = 1,2,\cdots,n \] 或者写在一起： \[ \begin{bmatrix} \boldsymbol {a_1}^{\mathrm T} \\ \boldsymbol {a_2}^{\mathrm T} \\ \vdots \\ \boldsymbol {a_n}^{\mathrm T} \\ \end{bmatrix} \left(\boldsymbol b - \boldsymbol p\right) = \boldsymbol 0 \Rightarrow A^{\mathrm T} \left(\boldsymbol b - \boldsymbol p\right) = \boldsymbol 0 \] 因为 \(\boldsymbol p \in C(A)\)，所以 \(\boldsymbol p\) 是 \(A\) 列向量的线性组合，可以写作 \(\boldsymbol p = A\boldsymbol x\)。于是我们就得到了方程 \[ A^{\mathrm T} \left(\boldsymbol b - A\boldsymbol x\right) = \boldsymbol 0 \Rightarrow A^{\mathrm T}A\boldsymbol x = A^{\mathrm T}\boldsymbol b \] 因为 \(A\) 的列是线性无关的，所以 \(A^{\mathrm T}A\) 是可逆的（这个我们待会证明），于是我们可以解得 \[ \boldsymbol x = \left(A^{\mathrm T}A\right)^{-1}A^{\mathrm T}\boldsymbol b \] 即 \[ \boldsymbol p = A\left(A^{\mathrm T}A\right)^{-1}A^{\mathrm T}\boldsymbol b \] 此时我们很清楚地看到，投影矩阵是 \(P = A\left(A^{\mathrm T}A\right)^{-1}A^{\mathrm T}\)。

我们接下来证明之前我们用到的一个结论：\(A^{\mathrm T}A\) 可逆的充分必要条件是 \(A\) 的列向量线性无关。

我们发现这个结论等价于：\(A^{\mathrm T}A\) 和 \(A\) 有相同的零空间。

怎么证明？一个方向是简单的： \[ A\boldsymbol x = \boldsymbol 0 \Rightarrow A^{\mathrm T}\left(A\boldsymbol x\right) = \boldsymbol 0 \Rightarrow A^{\mathrm T} A\boldsymbol x = \boldsymbol 0 \] 反方向的证明需要一些技巧： \[ A^{\mathrm T} A\boldsymbol x = \boldsymbol 0 \Rightarrow \boldsymbol x^{\mathrm T} A^{\mathrm T} A\boldsymbol x = 0 \Rightarrow \left(A\boldsymbol x\right)^{\mathrm T}A\boldsymbol x = 0 \Rightarrow A\boldsymbol x = \boldsymbol 0 \] 倒数第二步写得有点花里胡哨其实就是向量自己和自己的点积，如果是零的话显然原向量就是零。

证毕。

最小二乘拟合

投影和最小二乘拟合是怎么联系起来的呢？

线性拟合的本质是用给定的若干列向量的线性组合表示另一个向量。

比如我有一组数据 \(\boldsymbol x,\boldsymbol y\)，我的模型是 \(y = a + bx\)，拟合的过程就是用向量 \(\boldsymbol 1\) 和 \(\boldsymbol x\) 的线性组合表示 \(\boldsymbol y\) 的过程： \[ \begin{bmatrix} 1 &x_1 \\ 1 &x_2 \\ \vdots &\vdots\\ 1 &x_n \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} \] “线性拟合” 的线性指的是这种组合的线性，和模型本身的线性是没有关系的。模型里面有二次项不要紧，只要二次项和其他项是线性组合的，那也不过是在左边的矩阵里多了一个列向量而已： \[ \begin{bmatrix} 1 &x_1 &x_1^2 \\ 1 &x_2 &x_2^2 \\ \vdots &\vdots &\vdots \\ 1 &x_n &x_n^2 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} \] 那么我们发现线性拟合的本质其实就是解一个形如 \(A\boldsymbol x = \boldsymbol b\) 的方程组（这里的 \(\boldsymbol x\) 表示模型中各项的系数，和上面表示自变量的 \(\boldsymbol x\) 没有关系），这个我们老熟悉了。

但是事情不太妙的就是 \(A\) 又高又瘦，方程组比未知数多，所以几乎肯定不存在准确解。

什么时候存在准确解？\(\boldsymbol b\) 要在 \(A\) 的列空间 \(C(A)\) 里。

所以如果只能求近似解，我们可以考虑把 \(\boldsymbol b\)“近似到”\(C(A)\) 中的一个最近的向量，然后就能求解了。

这个 “近似” 的过程其实就是投影。在 \(C(A)\) 中 \(\boldsymbol b\) 的投影肯定最接近 \(\boldsymbol b\)，因为只有二者的差是和 \(C(A)\) 垂直的，这很符合我们的代数直觉。

所以联系之前的投影的推导，假设这个投影向量是 \(A\boldsymbol{\hat{x}}\)，我们直接写出方程和解： \[ A^{\mathrm T} \left(\boldsymbol b - A\boldsymbol{\hat{x}} \right) = \boldsymbol 0 \Rightarrow \boldsymbol{\hat{x}} = \left(A^{\mathrm T}A\right)^{-1}A^{\mathrm T}\boldsymbol b \] 这就叫 “最小二乘拟合”。

如果非要较真，从微积分的角度理解一波也是可以的：定义拟合的误差函数为 \[ L= \left|\boldsymbol b - A\boldsymbol{\hat x}\right| = \sum_{i = 1}^n \left(\boldsymbol b_i - \left(A\boldsymbol{\hat x}\right)_i\right)^2 \] 如果要最小化 \(L\)，那么 \(L\) 关于 \(\boldsymbol{\hat x}\) 的所有分量的导数都为 \(0\)： \[ \frac{\mathrm d L}{\mathrm d\boldsymbol{\hat x}_k} = 2\sum_{i = 1}^n A_{i, k} \left(\left(A\boldsymbol{\hat x}\right)_i - \boldsymbol b_i\right) = 0, \quad \forall k = 1, 2, \cdots, n \] 令 \(A\) 第 \(i\) 列的列向量为 \(\boldsymbol a_i\)，那么上面也可以写成 \[ \frac{\mathrm d L}{\mathrm d\boldsymbol{\hat x}_k} = 2\boldsymbol a_k^{\mathrm T} \left(A\boldsymbol{\hat x} - \boldsymbol b\right) = 0, \quad \forall k = 1, 2, \cdots, n \] 并在一起得 \[ 2A^{\mathrm T}\left(A\boldsymbol{\hat x} - \boldsymbol b\right) = 0 \] 这就是上面我们通过投影推出的方程。

\(L\) 中的平方项也是最小二乘中 “二” 的由来。

矩阵的 Gram-Schmidt 正交化

我们发现无论是投影还是最小二乘拟合，计算 \(A^{\mathrm T}A\) 和它的逆都是绕不过去的一步。\(A^{\mathrm T}A\) 本身就有一些特殊的性质，比如说其一定是正方阵，一定是对称的（通过转置等于自身易证）。但是这些性质在计算的时候帮助不大。如果我们能够优化 \(A\) 的形态从而简化 \(A^{\mathrm T}A\) 和它的逆的计算，那么各种算法的效率都会高上不少。

注意到 \(A^{\mathrm T}A\) 中的每一个位置都是 \(A\) 两个列向量的点积。如果 \(A\) 当中的列向量是两两正交的，那么 \(A^{\mathrm T}A\) 就变成了一个对角阵。对角阵的逆不要太好算！更进一步，如果 \(A\) 的每一个列向量都是单位向量，那么 \(A^{\mathrm T}A\) 就是单位阵，连逆都不用求了！

所以说啊，正交是个好东西。那对于一个矩阵 \(A\)，通过什么样的方式将其列向量完成正交化呢？

比较简单的一个算法称为 Gram-Schmidt 正交化。设 \(A\) 的列向量为 \(\boldsymbol {a_1},\cdots, \boldsymbol{a_n}\)，则向量正交化之后的结果 \(\boldsymbol{q_i}\) 可以这么计算： \[ \boldsymbol{q_i} = \boldsymbol{a_i} - \sum_{j = 1}^{i - 1} \frac{\boldsymbol{q_j}^{\mathrm T}\boldsymbol{a_i}}{\boldsymbol{q_j}^{\mathrm T}\boldsymbol{q_j}} \boldsymbol{q_j} \] 即对于第 \(i\) 个列向量通过减去其在所有之前的（完成正交化的）向量上的投影来确保其和前面的向量都正交。

最后，把所有的 \(\boldsymbol{q_i}\) 除以其模完成归一化，我们就可以得到一个标准正交列向量组成的矩阵 \(Q\)，满足 \(Q^{\mathrm T}Q = I\)。（线性代数中常使用 \(Q\) 表示列向量标准正交的矩阵）

从 \(A\) 变到 \(Q\) 的过程没有改变列空间，所以不会改变投影矩阵，但计算投影矩阵的开销大大降低了： \[ P = Q\left(Q^{\mathrm T}Q\right)^{-1}Q^{\mathrm T} = QQ^{\mathrm T} \]

QR 分解

Gram-Schmidt 正交化的过程可以看作是在原矩阵上进行列变换，而列变换是可以用矩阵表示的。类比从高斯消元导出 LU 分解的思路，我们可以从 Gram-Schimidt 正交化导出一个矩阵的 QR 分解： \[ A = QR \] 我们有 \(A\)，可以通过 Gram-Schmidt 正交化算出 \(Q\)，但 \(R\) 怎么计算呢？因为 \(Q^{\mathrm T}Q=I\)，所以只要在等式两边同时乘以 \(Q^{\mathrm T}\)，就得到 \(R=Q^{\mathrm T}A\)。或者用 \(Q\) 和 \(A\) 的列向量表示： \[ R = \begin{bmatrix} \boldsymbol{q_1}^{\mathrm T} \\ \boldsymbol{q_2}^{\mathrm T} \\ \vdots \\ \boldsymbol{q_n}^{\mathrm T} \end{bmatrix} \begin{bmatrix} \boldsymbol{a_1} &\boldsymbol{a_2} &\cdots &\boldsymbol{a_n} \end{bmatrix} = \begin{bmatrix} \boldsymbol{q_1}^{\mathrm T}\boldsymbol{a_1} &\boldsymbol{q_1}^{\mathrm T}\boldsymbol{a_2} &\cdots &\boldsymbol{q_1}^{\mathrm T}\boldsymbol{a_n} \\ \boldsymbol{q_2}^{\mathrm T}\boldsymbol{a_1} &\boldsymbol{q_2}^{\mathrm T}\boldsymbol{a_2} &\cdots &\boldsymbol{q_2}^{\mathrm T}\boldsymbol{a_n} \\ \vdots &\vdots &\ddots &\vdots \\ \boldsymbol{q_n}^{\mathrm T}\boldsymbol{a_1} &\boldsymbol{q_n}^{\mathrm T}\boldsymbol{a_2} &\cdots &\boldsymbol{q_n}^{\mathrm T}\boldsymbol{a_n} \end{bmatrix} \] 注意到，因为 \(\boldsymbol{q_i}\) 正交于所有 \(\boldsymbol {q_j}(i < j)\)，而 \(\boldsymbol{a_j}\) 又是由 \(\boldsymbol{q_1},\cdots,\boldsymbol{q_j}\) 表示的，所以 \(i > j\) 时，\(\boldsymbol{q_i}^{\mathrm T}\boldsymbol{a_j} = 0\)。所以 \(R\) 其实是一个上三角阵： \[ R = \begin{bmatrix} \boldsymbol{q_1}^{\mathrm T}\boldsymbol{a_1} &\boldsymbol{q_1}^{\mathrm T}\boldsymbol{a_2} &\cdots &\boldsymbol{q_1}^{\mathrm T}\boldsymbol{a_n} \\ 0 &\boldsymbol{q_2}^{\mathrm T}\boldsymbol{a_2} &\cdots &\boldsymbol{q_2}^{\mathrm T}\boldsymbol{a_n} \\ \vdots &\vdots &\ddots &\vdots \\ 0 &0 &\cdots &\boldsymbol{q_n}^{\mathrm T}\boldsymbol{a_n} \end{bmatrix} \] 再观察 \(R\) 的各个非零位置的值以及 Gram-Schimidt 的公式，其实 \(R\) 是可以在计算 Gram-Schmidt 正交化的时候顺便算出来的。

QR 分解有什么用呢？之前我们说正交化不改变投影矩阵，原因是 “正交化不改变列空间”，QR 分解能让我们在代数上证明这一点： \[ \begin{aligned} P &= A\left(A^{\mathrm T}A\right)^{-1}A^{\mathrm T} \\ &= QR\left(R^{\mathrm T}Q^{\mathrm T}QR\right)^{-1}R^{\mathrm T}Q^{\mathrm T} \\ &= QR\left(R^{\mathrm T}R\right)^{-1}R^{\mathrm T}Q^{\mathrm T} \\ &= QRR^{-1}\left(R^{\mathrm T}\right)^{-1}R^{\mathrm T}Q^{\mathrm T} \\ &= QQ^{\mathrm T} \end{aligned} \] 注：因为 \(R\) 是一个方阵，所以我们这里能够把 \(\left(R^{\mathrm T}R\right)^{-1}\) 改写成 \(R^{-1}(R^{\mathrm T})^{-1}\)。\(\left(A^{\mathrm T}A\right)^{-1}\) 是不能这么转换的，因为长方阵不存在常规意义上的逆。

类似地，QR 分解还简化了最小二乘拟合的计算： \[ \boldsymbol{\hat{x}} = \left(A^{\mathrm T}A\right)^{-1}A^{\mathrm T}\boldsymbol b = R^{-1}Q^{\mathrm T}\boldsymbol b \]