最小二乘法拟合直线

Wikipedia，自由的百科全书

本说明用于解释blobtrack程序的DetectNewBlob()函数中的直线拟合部分

问题

假设已知时间序列上的点集 $(x_t, y_t), t=0,1,\cdots, N-1$ ，需要拟合直线 $\begin{pmatrix}x \\ y\end{pmatrix}=\begin{pmatrix}a_x \\ a_y \end{pmatrix}\cdot t+\begin{pmatrix}b_x \\ b_y \end{pmatrix}$ ，也就是分别拟合直线 $\left\{ \begin{matrix}x = a_x\cdot t+b_x \\ y = a_y\cdot t+b_y\end{matrix}\right .$ 。

该问题可以分解为两个完全相同的子问题：

使用点集 $(x_t, t), t=0,1,\cdots, N-1$ ，来拟合(x, t)平面上的直线 $x = a_x\cdot t+b_x$ ；
使用点集 $(y_t, t), t=0,1,\cdots, N-1$ ，来拟合(y, t)平面上的直线 $y = a_y\cdot t+b_y$ 。

下面以拟合(x, t)平面上的直线 $x = a \cdot t+b$ 为例说明问题的求解。

[编辑]

解答

所有的点到拟合出的直线 $x = a \cdot t+b$ 的误差应该为最小，也就是(a,b)分别取什么值的时候，下面这个方程的值（误差）最小：

$\min_{a,b}\left\|\begin{pmatrix}0 & 1 \\ 1 & 1 \\ \vdots & \vdots \\ N-1 & 1 \end{pmatrix} \begin{pmatrix} a\\ b\end{pmatrix} - \begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_{N-1}\end{pmatrix}\right\|_{2} = \min_{a,b} \left\|A \begin{pmatrix}a\\b\end{pmatrix} -\mathbf{x} \right\|_2.$