投影、最小二乘拟合与QR分解笔记

Posted on 2021-04-29 Views:

投影

高中的时候就学过，向量 $\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}$ 的列空间上（假设的列向量线性无关）。我们一样考虑 $\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$ 是

列向量的线性组合，可以写作 $\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^{\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^{\mathrm T}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$ 没有关系），这个我们老熟悉了。

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

什么时候存在准确解？ $\boldsymbol b$ 要在的列空间 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$

如果要最小化

，那么

关于 $\boldsymbol{\hat x}$ 的所有分量的导数都为

：

$\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$

令

第

列的列向量为 $\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$

这就是上面我们通过投影推出的方程。

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

矩阵的Gram-Schmidt正交化

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

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

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

比较简单的一个算法称为Gram-Schmidt正交化。设的列向量为 $\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}$

即对于第

个列向量通过减去其在所有之前的（完成正交化的）向量上的投影来确保其和前面的向量都正交。

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

从变到的过程没有改变列空间，所以不会改变投影矩阵，但计算投影矩阵的开销大大降低了：

$P = Q\left(Q^{\mathrm T}Q\right)^{-1}Q^{\mathrm T} = QQ^{\mathrm T}$

QR分解

Gram-Schmidt正交化的过程可以看作是在原矩阵上进行列变换，而列变换是可以用矩阵表示的。类比从高斯消元导出LU分解的思路，我们可以从Gram-Schimidt正交化导出一个矩阵的QR分解：

我们有

，可以通过Gram-Schmidt正交化算出

，但

怎么计算呢？因为 $Q^{\mathrm T}Q=I$ ，所以只要在等式两边同时乘以 $Q^{\mathrm T}$ ，就得到 $R=Q^{\mathrm T}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}$ 表示的，所以

时， $\boldsymbol{q_i}^{\mathrm T}\boldsymbol{a_j} = 0$ 。所以

其实是一个上三角阵：

$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}$

再观察

的各个非零位置的值以及Gram-Schimidt的公式，其实

是可以在计算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}$

注：因为

是一个方阵，所以我们这里能够把 $\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$