在投影之后接到最小二乘法。过了一段时间已经忘记了章节编排了，所以看到最小二乘接在投影后面吓了一跳，仔细看看才恍然大悟，于是又把自己观念上相隔很远的两个概念联系到一起了，可喜可贺。

最小二乘的动机

在中学课本，最小二乘通常作为寻找一条直线以最好地拟合若干采样点这类问题的解决方案出现。在Strang的书中，这一问题同样被用作重要的例子，但是书中也提供了更一般的抽象：对于关于 $\mathbf{x}$ 的方程 $\mathbf{Ax = b}$ 而言，由于种种原因，如有效方程数大于变元个数，我们无法得到完美的解。因此，我们转而允许引入一定的误差，寻求相对最优的解，使得误差最小。在这一情形下，我们用误差的范数 $\Vert\mathbf{Ax - b}\Vert$ ​来衡量误差大小。举一例来自原书的拟合直线问题。

问题：找到一条直线 $y = c_0 + c_1x$​，使之距离点 $(0, 6)$​，$(1, 0)$ ​和 $(2, 0)$ ​最近。

分析：假定我们希望找到一条完美的直线，那么将数据代入直线方程，我们得到

$$ \begin{align} 6 & = c_0 + 0\cdot c_1 \\ 0 & = c_0 + 1\cdot c_1 \\ 0 & = c_0 + 2\cdot c_1 \end{align} $$

写成矩阵和向量的形式，我们同样能得到 $\mathbf{Ax = b}$ ​的形式，其中

$$ \mathbf{A} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix},\ \mathbf{x} = \begin{bmatrix} c_0 \\ c_1 \end{bmatrix},\ \mathbf{b} = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix}. $$

上面已经提到，解 $\mathbf{x}$ 可以不是完美的，我们只需要找到最好的、使得误差最小的解。

最小二乘与投影

那么，这个问题和投影有什么关系呢？

把转化后的问题重新写成 $\mathbf{b = p + e = Ax + e}$ 的形式，我们会发现，原方程的无解和新方程的求解也可以用另一种方式看待。我们把 $\mathbf{A}$ 视为其列向量张成的向量空间，而 $\mathbf{b}$ 落在了向量空间外。我们可以在 $\mathbf{A}$ 的范围内最大限度地表示出 $\mathbf{b}$ 的分量，并且保证误差 $\mathbf{e}$ 最小，这就回归到了上一节投影中同样的情景。只不过在投影一节中，我们在投影的分解中用正交性 $\mathbf{p}^{\rm T}\mathbf{e} = 0$ 来加以约束，回避了“误差最小”的定义。而在上文，我们提出了 $\Vert \mathbf{Ax - b}\Vert$ 这种衡量方式。接下来我们会证明投影分解所得到的 $\Vert \mathbf{e}\Vert$ ​正是最小的。

假设 $\mathbf{A}^{\rm T}\mathbf{A}$​​ 可逆，则有 $\mathbf{b = Ax + e}$​​，其中 $(\mathbf{Ax})^{\rm T}\mathbf{e} = 0$ ​​。$\forall\ \mathbf{x’}$​​​​​，
$$
\mathbf{b = Ax + e = Ax’ + A(x - x’) + e}.
$$

在新的分解方式中，计算误差的大小：

$$ \begin{align} \Vert\mathbf{Ax' - b}\Vert & = \Vert\mathbf{A(x' - x) - e}\Vert \\ & = \Vert\mathbf{A(x' - x)}\Vert - 2\mathbf{(x' - x)}^{\rm T}\mathbf{A}^{\rm T}\mathbf{e} + \Vert\mathbf{e}\Vert \\ & = \Vert\mathbf{A(x' - x)}\Vert + \Vert\mathbf{e}\Vert \ge \Vert\mathbf{e}\Vert \end{align} $$

所以，将 $\mathbf{b}$ 投影到 $\mathbf{A}$ 正是上述问题的解法。从几何直观和微积分出发，我们也能得到相同的结论。实际上，通过微积分方法求误差范数 $\Vert \mathbf{Ax - b}\Vert$ 的极小值时，也会经过求解 $\mathbf{A}^{\rm T}\mathbf{Ax} = \mathbf{A}^{\rm T}\mathbf{b}$​ ​的过程，这和按照投影矩阵公式计算的过程是很类似的。

同样地，如果 $\mathbf{A}^{\rm T}\mathbf{A}$ 不可逆，我们实际上无法找到新问题的唯一解。比如，我们无法找到唯一的直线来拟合点 $(0, 0)$ 和 $(0, 2)$ ，所有经过点 $(0, 1)$ 的直线都会得到同样大小的误差。书中提到，奇异值分解针对这种情况提供了相对可接受的解。

最小二乘的延伸

上面给出的例子都是二维平面上用直线拟合若干个点，在此基础上我们也不难拓展到一些更高维的情形。比如，我们可以设想用平面拟合3个或以上的点，这并不改变 $\mathbf{b = Ax + e}$ 的结构，而仅仅是增加了维度。

对于简单的非线性拟合，如 $n$ 次多项式，各项的计算包括了非线性的 $x^k$ ，但是各项的组合依然是线性的，因为 $y = \sum{c_i x^i}$ 。所以在求解最优的系数时，我们只需根据多项式的次数对 $\mathbf{A}$ ​​的写法稍加调整。比如抛物线的拟合：

$$ \mathbf{A} = \begin{bmatrix} 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \\ \vdots & \vdots & \vdots \\ 1 & x_3 & x_3^2 \end{bmatrix},\ \mathbf{x} = \begin{bmatrix} c_0 \\ c_1 \\ c_2 \end{bmatrix}. $$