MIT线性代数总结笔记——最小二乘法（矩阵法）

在很多时候，我们在求解 $Ax=b$ 方程时，如果A的列数太多，混入一些不准确的数据，此时方程时无解的，我们需要求解出最优解。这时候就需要使用最小二乘法来进行拟合。在讲解最小二乘法之前需要一些知识作为铺垫。

一、四个基本子空间

首先我们知道，对于一个 $m×n$ 的矩阵 $A$ 有四个子空间：列空间、行空间、零空间、左零空间。

列空间 ( $C(A)$ )：列空间是 $R^m$ 的子空间，是矩阵 $A$ 的列向量的线性组合的集合构成的空间，每个列向量有 $m$ 个分量，设矩阵 $A$ 的秩为 $r$ ，则 $A$ 有 $r$ 个主列，这 $r$ 个主列就是列空间的一组基，一组基中有 $r$ 个向量，所以列空间维数是 $r$ 。
行空间（ $C(A^T)$ ）：行空间是 $R^n$ 的子空间，是矩阵 $A$ 各行向量的线性组合的集合构成的空间，可以化为 $A$ 转置的列空间，因此行空间的秩也是 $r$ ，每个行向量有 $n$ 个分量，所以行空间的维数也是r。
零空间（ $N(A)$ ）：零空间是 $R^n$ 的子空间,是由 $Ax=0$ 的解所构成的空间。由于x本质是A列向量的线性组合， $A$ 一共有 $n$ 个列向量，所以 $A$ 的秩为 $r$ 时，自由列有 $n-r$ 列， $x$ 中有 $n-r$ 个自由变元，也就有 $n-r$ 个基向量，因此维数也是 $n-r$ 。
左零空间（ $N(A^T)$ ）：左零空间是 $R^m$ 的子空间，是由 $A^Ty = 0$ 的解的线性组合构成的空间，维数为 $m-r$ 。

二、子空间与正交

接着，我们会发现，这四个子空间中存在正交关系。我们知道，在空间中证明两个向量是正交关系只需要判断两向量的内积是否为0。那么在子空间中也是如此。空间的正交定义是：一个空间中的任意一个向量都与另一个空间中的任意一个向量正交。

零空间与行空间是正交的，证明起来非常容易。我们将 $Ax=0$ 写成下图的形式，很轻易就能证明，每一个行向量乘上 $x$ 向量都为0，由于行向量是行空间的一组基，因此可以代表全部的行向量，这就满足了空间正交的定义。

$\left[\begin{matrix}R_1 \\ R_2 \\ ... \\ ... \\ R_m\end{matrix} \right] \left[\begin{matrix}x_1 \\ x_2 \\ ... \\ ... \end{matrix} \right] = \left[\begin{matrix}R_1(x_1,x_2 ...) \\ R_2(x_1,x_2 ...) \\ ............ \\ ............ \\R_m(x_1,x_2 ...) \end{matrix} \right] = \left[\begin{matrix}0 \\ 0 \\ . \\.\\0 \end{matrix} \right]$

不光行空间与零空间是正交关系，我们也可以轻易推出列空间和左零空间也是正交关系。
我们假设在一个 $R^3$ 空间中，不难想象，假设矩阵 $A$ 的行空间是二维平面（ $r=2$ ），那么其零空间就是一条线（ $n-r = 1$ ），又因为是正交关系，所以可知，零空间就是行空间二维平面的法向。因此，行空间与零空间之间关系类似于将空间一分为二，得到两个正交的子空间，我们把这称为 $R^n$ 空间的正交补。

三、子空间投影

向量-向量的投影问题

Figure1: 向量-向量投影问题。图片来源：作者自制

如图1， $p$ 为 $b$ 在 $a$ 上的投影，写作 $p = xa$ （ $x$ 为倍数），根据向量减法得到，投影方向 $e = b-p$ 。根据向量正交则内积为零的性质（ $a$ 垂直于 $e$ ）可得
$a^Te = a^T(b-p) = a^T(b-ax) = 0$
这时再将 $p=xa$ 带入，可得
$p = a \frac{a^Tb}{a^Ta} = \frac{aa^T}{a^Ta} b$
这里我们可以将 $\frac{aa^T}{a^Ta}$ 看作一个矩阵，称为投影矩阵 $P$ 。

向量-平面的投影问题

如图2， $a1$ ， $a2$ 为构成平面的一组基， $p$ 在平面上。所以有 $p = \hat{x_1}a_1 + \hat{x_2}a_2$ ，或者直接写作 $p = A\hat{x}$ ， $A=\left[\begin{matrix}a_1&a_2\end{matrix} \right]$ (其中 $a_n$ 为列向量)， $\hat{x} = \left[\begin{matrix}\hat{x_1}\\\hat{x_2}\end{matrix} \right]$ 。

Figure2: 向量-平面投影问题。图片来源：作者自制

由于 $e$ 是垂直于平面的向量， $e = b-p$ ，那么我们可以用内积形式表达 $e$ 和 $a_1$ 、 $a_2$ 的垂直关系： $a_1^T(b-A\hat{x}) = 0$ 、 $a_2^T(b-A\hat{x}) = 0$ ，写成矩阵形式得：
$\left[\begin{matrix}a_1^T\\a_2^T\end{matrix} \right](b-A\hat{x}) = \left[\begin{matrix}0\\0\end{matrix} \right]$
即
$A^T(b-A\hat{x}) = 0$

上文已述，列空间与左零空间是正交关系，图2中的向量 $a1$ 、 $a2$ 正是列空间中的向量， $e$ 又垂直于这个平面，也就是说， $e$ 位于 $A$ 的左零空间中。
我们继续展开式子：
$A^Tb-A^TA\hat{x} = 0$
得到：
$\hat{x} = (A^TA)^{-1}A^Tb$
代入 $p=A\hat{x}$ 得：
$p = A\hat{x} = A(A^TA)^{-1}A^Tb$
这样我们就得到了向量p与向量b之间的投影关系，进而得到了投影矩阵：
$P = A(A^TA)^{-1}A^T$
这也是投影矩阵的一般情况。那么 $P$ 有哪些性质呢？我们知道 $A^TA$ 是一个 $n×n$ 矩阵，并且是可逆的对称矩阵。对称矩阵的转置还是它本身，因此观察公式我们能得出

$P^T = P$

接着，根据图像，如果我们将b投影到A的列空间上两次，得到的结果依然是 $p$ ，因此有

$P^2 = P$

证明：
$P^2 = P×P = A(A^TA)^{-1}A^T A(A^TA)^{-1}A^T = A(A^TA)^{-1}A^T=P$

那么投影矩阵有什么用呢？举例来说，它应该能产生出一个投影，如果让 $P$ 和 $b$ 相乘，此时在极端情况下，如果 $b$ 位于列空间中时，那么有 $Pb=b$ ；如果 $b$ 垂直于列空间，那么有 $Pb=0$ ，此时的 $b$ 就在左零空间中。一般情况下会有一个分量在列空间里，另一个分量在左零空间中。

因此，一个向量 $b$ 总有两个分量，一个分量在 $A$ 的列空间中（也就是 $p$ ），另一个分量垂直于 $A$ 的列空间（位于左零空间，也就是 $e$ ）。而投影矩阵的作用就是保留列空间中的那个分量，拿掉垂直于列空间的分量。

由此我们可以分别表示出 $p$ 和 $e$ ：
$p = Pb$
$e = b-p = b-Pb = (I-P)b$
这里(I-P)也可以看作是一个投影矩阵，作用于 $b$ 向量，投影到左零空间中。 $e$ 被表示出来后，我们就可以控制误差了。

四、最小二乘法

有了上述知识的铺垫接下来就可以进入最小二乘法了。其实最小二乘法就是一种投影，最后就是保证误差最小，使用最小二乘法其实就是为了解决 $Ax=b$ 无解的情况。

我们从一个案例开始：
例. 求解：三个点 $(1,1)$ ， $(2,2)$ ， $(3,2)$ 拟合的直线方程
我们设最优直线方程为： $b=C+Dt$ ，带入三个点得： $C+D=1$ 、 $C+2D=2$ 、 $C+3D=2$
写成矩阵形式为：
$\left[\begin{matrix}1 & 1 \\ 1 & 2 \\ 1 & 3 \end{matrix} \right] \left[\begin{matrix}C \\ D \end{matrix} \right] = \left[\begin{matrix}1 \\ 2\\2 \end{matrix} \right]$
其中，
$A = \left[\begin{matrix}1 & 1 \\ 1 & 2 \\ 1 & 3 \end{matrix} \right], \hat{x} = \left[\begin{matrix}\hat{C} \\ \hat{D} \end{matrix} \right], b= \left[\begin{matrix}1 \\ 2\\2 \end{matrix} \right]$
列出矩阵方程后会发现 $Ax=b$ 无解，为了求近似的 $\hat{x}$ ，由于 $Ax = b$ 可能无解，那么只能求解最接近的那个可解问题，因为 $Ax$ 总是在列空间里，而 $b$ 不一定在，所以我们要把 $b$ 变为列空间中最为接近的向量，这样就把问题转化为了 $A\hat{x} = p$ ，误差就是投影距离 $e = b-p$ 。就有
$A^Tb = A^TA\hat{x}$
求解：
$A^TA = \left[\begin{matrix}1 & 1 &1 \\ 1 & 2 & 3 \end{matrix} \right] \left[\begin{matrix}1 & 1 \\ 1 & 2 \\ 1 & 3 \end{matrix} \right] = \left[\begin{matrix}3 & 6 \\ 6 & 14 \end{matrix} \right]$
$A^Tb = \left[\begin{matrix}1 & 1 &1 \\ 1 & 2 & 3 \end{matrix} \right] \left[\begin{matrix}1\\2 \\ 2\end{matrix} \right] = \left[\begin{matrix} 5 \\ 11 \end{matrix} \right]$
解得：
$\hat{x} = \left[\begin{matrix} \frac{2}{3} \\ \frac{1}{2} \end{matrix} \right]$
固拟合直线为： $y =\hat{C} +\hat{D}x = \frac{2}{3}+ \frac{1}{2}x$

我们也可以通过求偏导，求极值，从导数的角度来求得拟合直线，可以先表示出误差 $|Ax-b|$ ，为了便于计算，我们去求它们的平方和：
$|e|^2 = |Ax-b|^2$
那么总误差 $E = e_1^2+e_2^2+e_3^2$ ，求 $E$ 的最小值 $E_{min}$ 即可。

求出 $\hat{C}$ 和 $\hat{D}$ 后三个点各自的误差也可以求得，只需带入三个点的坐标即可得到三个 $p$ ，通过 $e = b-p$ ，最终我们得到了：
$b = \left[\begin{matrix} 1 \\ 2\\2 \end{matrix} \right], p = \left[\begin{matrix} \frac{7}{6}\\\frac{10}{6}\\\frac{13}{6} \end{matrix} \right], e = \left[\begin{matrix} -\frac{1}{6}\\\frac{2}{6}\\-\frac{1}{6} \end{matrix} \right]$

我们就得到了如下性质：

误差向量 $e$ 与投影向量 $p$ 垂直；
误差向量 $e$ 还垂直与列空间中的每一个向量。

最后需要注意，最小二乘法存在一定的局限性，那就是最小二乘法很容易受到离群量的影响。如果数据中有误差过大的点，那么它会对整个结果带来巨大的影响。