3.1 长度

首先，以一个简单的线性回归问题（一条直线拟合数据的问题），来直观的体会“长度”。
a)对数据（z,d）的最小二乘直线拟合；b)$e_i = d_{i}^{obs} - d_{i}^{pre}$ei​=diobs​−dipre​

那么，最佳的拟合直线所具有模型参数（截距和斜率）将使总误差E最小，即
$E = \sum\limits_{i=1}^{n}e_{i}^{2}=\bf {e^Te} = min$E=i=1∑n​ei2​=eTe=min
式中，总误差$E$E恰恰使向量$\bf e$e的欧几里得长度。

从长度方法的观点来看，最小二乘法是通过寻找预测误差的最小长度所对应的模型参数（截距和斜率）来估计反问题的解。通常来讲在，求解反问题的过程中使用长度方法是最简单的方法，也符合人的直观感受。

3.2 范数==》长度的推广

所谓范数是指对某些长度或大小的度量，其公式如下：
${\|e\|}_{p} = (\sum\limits_{i=1}^{n}e^p)^{\frac{1}{p}}$∥e∥p​=(i=1∑n​ep)p1​
以下三种范数最为常用：
$L_{1}$L1​ norm: $\quad\|\mathbf{e}\|_{1}=\left[\sum_{i}\left|e_{i}\right|^{1}\right]$∥e∥1​=[∑i​∣ei​∣1]
$L_{2}$L2​ norm: $\quad\|\mathbf{e}\|_{2}=\left[\sum_{i}\left|e_{i}\right|^{2}\right]^{1 / 2}$∥e∥2​=[∑i​∣ei​∣2]1/2
$L_{\infty}$L∞​ norm: $\quad\|\mathbf{e}\|_{\infty}=\max _{i}\left|e_{i}\right|$∥e∥∞​=maxi​∣ei​∣
幂次越高的范数给$\mathbf{e}$e中最大元素更大的权重，$L_{\infty}$L∞​表明仅对$\mathbf{e}$e的最大元素施加权重

从上图上看，$|e|$∣e∣的显著性最明显，而$|e^{10}|$∣e10∣最差

那么，最小二乘法究竟该选择哪种长度（即采取哪种范数），这个问题的答案涉及对远离平均趋势的离群数据进行加权的方式,如下图所示：

图中，$L_1$L1​范数给离群点的权重最小。

3.3 线性反问题的最小二乘解

最小二乘能够以一种非常直接的方式推广到一般线性反问题。
$E=\mathbf{e}^{\mathrm{T}} \mathbf{e}=(\mathbf{d}-\mathbf{G} \mathbf{m})^{\mathrm{T}}(\mathbf{d}-\mathbf{G} \mathbf{m})=\sum_{i=1}^{N}\left[d_{i}-\sum_{j=1}^{M} G_{i j} m_{j}\right]\left[d_{i}-\sum_{k=1}^{M} G_{i k} m_{k}\right]$E=eTe=(d−Gm)T(d−Gm)=i=1∑N​[di​−j=1∑M​Gij​mj​][di​−k=1∑M​Gik​mk​]
为避免混乱，对上式进行重新整理：
$E=\sum_{j=1}^{M} \sum_{k=1}^{M} m_{j} m_{k} \sum_{i=1}^{N} G_{i j} G_{i k}-2 \sum_{j=1}^{M} m_{j} \sum_{i=1}^{N} G_{i j} d_{i}+\sum_{i=1}^{N} d_{i} d_{i}$E=j=1∑M​k=1∑M​mj​mk​i=1∑N​Gij​Gik​−2j=1∑M​mj​i=1∑N​Gij​di​+i=1∑N​di​di​

令$\frac{\partial E}{\partial m_{p}}=0$∂mp​∂E​=0
第一项为：
$\begin{aligned} \frac{\partial}{\partial m_{q}}\left[\sum_{j=1}^{M} \sum_{k=1}^{M} m_{j} m_{k} \sum_{i=1}^{N} G_{i j} G_{i k}\right] &=\sum_{j=1}^{M} \sum_{k=1}^{M}\left[\delta_{j q} m_{k}+m_{j} \delta_{k q}\right] \sum_{i=1}^{N} G_{i j} G_{i k} \\ &=2 \sum_{k=1}^{M} m_{k} \sum_{i=1}^{N} G_{i q} G_{i k} \end{aligned}$∂mq​∂​[j=1∑M​k=1∑M​mj​mk​i=1∑N​Gij​Gik​]​=j=1∑M​k=1∑M​[δjq​mk​+mj​δkq​]i=1∑N​Gij​Gik​=2k=1∑M​mk​i=1∑N​Giq​Gik​​

注意：模型参数是相互独立的变量，$\partial m_{i} / \partial m_{j}$∂mi​/∂mj​形式的导数只有在$i=j$i=j时候等于$1$1，而$i \neq j$i​=j是为0，因此$\partial m_{i} / \partial m_{j}$∂mi​/∂mj​克罗内克函数（Kronecker delta）$\delta_{i j}$δij​，包含它的公式可以明显的简化

第二项为：
$-2 \frac{\partial}{\partial m_{q}}\left[\sum_{j=1}^{M} m_{j} \sum_{i=1}^{N} G_{i j} d_{i}\right]=-2 \sum_{j=1}^{M} \delta_{j q} \sum_{i=1}^{N} G_{i j} d_{i}=-2 \sum_{i=1}^{N} G_{i q} d_{i}$−2∂mq​∂​[j=1∑M​mj​i=1∑N​Gij​di​]=−2j=1∑M​δjq​i=1∑N​Gij​di​=−2i=1∑N​Giq​di​

第三项为：
$\frac{\partial}{\partial m_{q}}\left[\sum_{i=1}^{N} d_{i} d_{i}\right]=0$∂mq​∂​[i=1∑N​di​di​]=0

结合三项，可得：
$\frac{\partial E}{\partial m_{q}}=0=2 \sum_{k=1}^{M} m_{k} \sum_{i=1}^{N} G_{i q} G_{i k}-2 \sum_{i=1}^{N} G_{i q} d_{i}$∂mq​∂E​=0=2k=1∑M​mk​i=1∑N​Giq​Gik​−2i=1∑N​Giq​di​

重新写成矩阵形式：
$\mathbf{G}^{\mathrm{T}} \mathbf{G m}-\mathbf{G}^{\mathrm{T}} \mathbf{d}=0$GTGm−GTd=0
假设$\left[\mathbf{G}^{\mathrm{T}} \mathbf{G}\right]^{-1}$[GTG]−1存在（有不存在的时候），那么有如下解：
$\mathbf{m}^{\mathrm{est}}=\left[\mathbf{G}^{\mathrm{T}} \mathbf{G}\right]^{-1} \mathbf{G}^{\mathrm{T}} \mathbf{d}$mest=[GTG]−1GTd

对于维度较大的情况，$\mathbf{G}^{\mathrm{T}} \mathbf{G}$GTG的计算成本可能很高，而且$\mathbf{G}^{\mathrm{T}} \mathbf{G}$GTG极少像$\mathbf G$G那样稀疏。在这种情况下，优先考虑迭代的矩阵求解方案，如双共轭梯度算法（biconjugate gradient method）

3.4 一些最小二乘法的例子

1） 直线拟合问题：

模型是 $d_i =m_1+m_2z_i$di​=m1​+m2​zi​,方程$\mathbf{Gm=d}$Gm=d形式如下：
$\left[\begin{array}{cc} 1 & z_{1} \\ 1 & z_{2} \\ \vdots & \vdots \\ 1 & z_{N} \end{array}\right]\left[\begin{array}{c} m_{1} \\ m_{2} \end{array}\right]=\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]$⎣⎢⎢⎢⎡​11⋮1​z1​z2​⋮zN​​⎦⎥⎥⎥⎤​[m1​m2​​]=⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​
==》
$\mathbf{G}^{\mathrm{T}} \mathbf{G}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ z_{1} & z_{2} & \cdots & z_{N} \end{array}\right]\left[\begin{array}{cc} 1 & z_{1} \\ 1 & z_{2} \\ \vdots & \vdots \\ 1 & z_{N} \end{array}\right]=\left[\begin{array}{cc} N & \sum_{i=1}^{N} z_{i} \\ \sum_{i=1}^{N} z_{i} & \sum_{i=1}^{N} z_{i}^{2} \end{array}\right]$GTG=[1z1​​1z2​​⋯⋯​1zN​​]⎣⎢⎢⎢⎡​11⋮1​z1​z2​⋮zN​​⎦⎥⎥⎥⎤​=[N∑i=1N​zi​​∑i=1N​zi​∑i=1N​zi2​​]

$\mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ z_{1} & z_{2} & \cdots & z_{N} \end{array}\right]\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]=\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} d_{i} z_{i} \end{array}\right]$GTd=[1z1​​1z2​​⋯⋯​1zN​​]⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​=[∑i=1N​di​∑i=1N​di​zi​​]
$\mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ z_{1} & z_{2} & \cdots & z_{N} \end{array}\right]\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]=\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} d_{i} z_{i} \end{array}\right]$GTd=[1z1​​1z2​​⋯⋯​1zN​​]⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​=[∑i=1N​di​∑i=1N​di​zi​​]

$\mathbf{m}^{\mathrm{est}}=\left[\mathbf{G}^{\mathrm{T}} \mathbf{G}\right]^{-1} \mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{cc} N & \sum_{i=1}^{N} z_{i} \\ \sum_{i=1}^{N} z_{i} & \sum_{i=1}^{N} z_{i}^{2} \end{array}\right]^{-1}\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} d_{i} z_{i} \end{array}\right]$mest=[GTG]−1GTd=[N∑i=1N​zi​​∑i=1N​zi​∑i=1N​zi2​​]−1[∑i=1N​di​∑i=1N​di​zi​​]

2 抛物线拟合

模型是$d_{i}=m_{1}+m_{2} z_{i}+m_{3} z_{i}^{2}$di​=m1​+m2​zi​+m3​zi2​，方程$\mathbf{Gm=d}$Gm=d形式如下：
$\left[\begin{array}{ccc} 1 & z_{1} & z_{1}^{2} \\ 1 & z_{2} & z_{2}^{2} \\ \vdots & \vdots & \vdots \\ 1 & z_{N} & z_{N}^{2} \end{array}\right]\left[\begin{array}{c} m_{1} \\ m_{2} \\ m_{3} \end{array}\right]=\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]$⎣⎢⎢⎢⎡​11⋮1​z1​z2​⋮zN​​z12​z22​⋮zN2​​⎦⎥⎥⎥⎤​⎣⎡​m1​m2​m3​​⎦⎤​=⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​
==》
$\mathbf{G}^{\mathrm{T}} \mathbf{G}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ z_{1} & z_{2} & \cdots & z_{N} \\ z_{1}^{2} & z_{N}^{2} & \cdots & z_{N}^{2} \end{array}\right]\left[\begin{array}{ccc} 1 & z_{1} & z_{1}^{2} \\ 1 & z_{2} & z_{2}^{2} \\ \vdots & \vdots & \vdots \\ 1 & z_{N} & z_{N}^{2} \end{array}\right]$GTG=⎣⎡​1z1​z12​​1z2​zN2​​⋯⋯⋯​1zN​zN2​​⎦⎤​⎣⎢⎢⎢⎡​11⋮1​z1​z2​⋮zN​​z12​z22​⋮zN2​​⎦⎥⎥⎥⎤​
$\mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ z_{1} & z_{2} & \cdots & z_{N} \\ z_{1}^{2} & z_{N}^{2} & \cdots & z_{N}^{2} \end{array}\right]\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]=\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} z_{i} d_{i} \\ \sum_{i=1}^{N} z_{i}^{2} d_{i} \end{array}\right]$GTd=⎣⎡​1z1​z12​​1z2​zN2​​⋯⋯⋯​1zN​zN2​​⎦⎤​⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​=⎣⎢⎡​∑i=1N​di​∑i=1N​zi​di​∑i=1N​zi2​di​​⎦⎥⎤​

$\mathbf{m}^{\mathrm{est}}=\left[\mathbf{G}^{\mathrm{T}} \mathbf{G}\right]^{-1} \mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{ccc} N & \sum_{i=1}^{N} z_{i} & \sum_{i=1}^{N} z_{i}^{2} \\ \sum_{i=1}^{N} z_{i} & \sum_{i=1}^{N} z_{i}^{2} & \sum_{i=1}^{N} z_{i}^{3} \\ \sum_{i=1}^{N} z_{i}^{2} & \sum_{i=1}^{N} z_{i}^{3} & \sum_{i=1}^{N} z_{i}^{4} \end{array}\right]^{-1}\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} z_{i} d_{i} \\ \sum_{i=1}^{N} z_{i}^{2} d_{i} \end{array}\right]$mest=[GTG]−1GTd=⎣⎢⎡​N∑i=1N​zi​∑i=1N​zi2​​∑i=1N​zi​∑i=1N​zi2​∑i=1N​zi3​​∑i=1N​zi2​∑i=1N​zi3​∑i=1N​zi4​​⎦⎥⎤​−1⎣⎢⎡​∑i=1N​di​∑i=1N​zi​di​∑i=1N​zi2​di​​⎦⎥⎤​

上图为开普勒第三定律的验证，它阐述了行星轨道半径的立方正比于轨道周期的平方。a)对于太阳系，数据（红圈）用二次方公式$d_i=m_1+m_2z_i+m_3z_{i}^{2}$di​=m1​+m2​zi​+m3​zi2​实现了最小二乘拟合，其中$d_i$di​为半径的立方，$z_i$zi​为周期。b)拟合误差，将数据和误差独立显示的目的是将误差以恰当的尺度画出。数据源于维基百科（Wikipedia）。

3、平面拟合

模型：$d_{i}=m_{1}+m_{2} x_{i}+m_{3} y_{i}$di​=m1​+m2​xi​+m3​yi​，方程$\mathbf{Gm=d}$Gm=d形式如下：
$\left[\begin{array}{ccc} 1 & x_{1} & y_{1} \\ 1 & x_{2} & y_{2} \\ \vdots & \vdots & \vdots \\ 1 & x_{N} & y_{N} \end{array}\right]\left[\begin{array}{c} m_{1} \\ m_{2} \\ m_{3} \end{array}\right]=\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]$⎣⎢⎢⎢⎡​11⋮1​x1​x2​⋮xN​​y1​y2​⋮yN​​⎦⎥⎥⎥⎤​⎣⎡​m1​m2​m3​​⎦⎤​=⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​
==》
$\mathbf{G}^{\mathrm{T}} \mathbf{G}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ x_{1} & x_{2} & \cdots & x_{N} \\ y_{1} & y_{2} & \cdots & y_{N} \end{array}\right]\left[\begin{array}{ccc} 1 & x_{1} & y_{1} \\ 1 & x_{2} & y_{2} \\ \vdots & \vdots & \vdots \\ 1 & x_{N} & y_{N} \end{array}\right]$GTG=⎣⎡​1x1​y1​​1x2​y2​​⋯⋯⋯​1xN​yN​​⎦⎤​⎣⎢⎢⎢⎡​11⋮1​x1​x2​⋮xN​​y1​y2​⋮yN​​⎦⎥⎥⎥⎤​
$=\left[\begin{array}{ccc} N & \sum_{i=1}^{N} x_{i} & \sum_{i=1}^{N} y_{i} \\ \sum_{i=1}^{N} x_{i} & \sum_{i=1}^{N} x_{i}^{2} & \sum_{i=1}^{N} x_{i} y_{i} \\ \sum_{i=1}^{N} y_{i} & \sum_{i=1}^{N} x_{i} y_{i} & \sum_{i=1}^{N} y_{i}^{2} \end{array}\right]$=⎣⎢⎡​N∑i=1N​xi​∑i=1N​yi​​∑i=1N​xi​∑i=1N​xi2​∑i=1N​xi​yi​​∑i=1N​yi​∑i=1N​xi​yi​∑i=1N​yi2​​⎦⎥⎤​

$\mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ x_{1} & x_{2} & \cdots & x_{N} \\ y_{1} & y_{2} & \cdots & y_{N} \end{array}\right]\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{N} \end{array}\right]=\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} x_{i} d_{i} \\ \sum_{i=1}^{N} y_{i} d_{i} \end{array}\right]$GTd=⎣⎡​1x1​y1​​1x2​y2​​⋯⋯⋯​1xN​yN​​⎦⎤​⎣⎢⎢⎢⎡​d1​d2​⋮dN​​⎦⎥⎥⎥⎤​=⎣⎢⎡​∑i=1N​di​∑i=1N​xi​di​∑i=1N​yi​di​​⎦⎥⎤​

$\mathbf{m}^{\mathrm{est}}=\left[\mathbf{G}^{\mathrm{T}} \mathbf{G}\right]^{-1} \mathbf{G}^{\mathrm{T}} \mathbf{d}=\left[\begin{array}{ccc} N & \sum_{i=1}^{N} x_{i} & \sum_{i=1}^{N} y_{i} \\ \sum_{i=1}^{N} x_{i} & \sum_{i=1}^{N} x_{i}^{2} & \sum_{i=1}^{N} x_{i} y_{i} \\ \sum_{i=1}^{N} y_{i} & \sum_{i=1}^{N} x_{i} y_{i} & \sum_{i=1}^{N} x_{i} y_{i}^{2} \end{array}\right]^{-1}\left[\begin{array}{c} \sum_{i=1}^{N} d_{i} \\ \sum_{i=1}^{N} x_{i} d_{i} \\ \sum_{i=1}^{N} y_{i} d_{i} \end{array}\right]$mest=[GTG]−1GTd=⎣⎢⎡​N∑i=1N​xi​∑i=1N​yi​​∑i=1N​xi​∑i=1N​xi2​∑i=1N​xi​yi​​∑i=1N​yi​∑i=1N​xi​yi​∑i=1N​xi​yi2​​⎦⎥⎤​−1⎣⎢⎡​∑i=1N​di​∑i=1N​xi​di​∑i=1N​yi​di​​⎦⎥⎤​

上图是使用平面拟合来检测地质断层上发生地震的例子，（圆圈）西北太平洋千岛群岛俯冲带发生的地震。$x$x坐标轴指向北，$y$y坐标轴指向东。地震散布在一个由最小二乘确定的倾斜平面附近。数据来自美国地质调查局（United States Geological Survey, USGS）。