前言

我们考虑一个实际问题，假设两变量y和t之间存在某种规律，不妨用函数y=f(t)表示，能否通过测量y关于t的变化，亦即通过测量y在t上的若干个取值t_1,t_2,\cdots,t_m上的值y_1,y_2,\cdots,y_m（这一过程称为采样），来总结出函数f的具体形式？

最小二乘法

假设令\mathbf{t}=\begin{bmatrix}t_1\\t_2\\ \vdots \\t_n\end{bmatrix}，\mathbf{y}=\begin{bmatrix}y_1\\y_2\\\vdots\\y_n\end{bmatrix},\mathbf{1}=\begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix},则假设引出方程
::: align-center
k\mathbf{t}+b\mathbf{1}=\mathbf{y}

:::
现实生活中此方程一般无解，即几何上不严谨的说即\mathbf{y}并不在k\mathbf{t}+b\mathbf{1}张成的空间内，但我们可以试图去寻找一组k,b使得\mathbf{y}-k\mathbf{t}-\mathbf{b}尽可能小

记\mathbf{A}=\begin{bmatrix}\mathbf{t} & \mathbf{1}\end{bmatrix},\mathbf{x}=\begin{bmatrix}k\\b\end{bmatrix}，则问题变为求解
::: align-center
\min_{x\in R^2}||\mathbf{y-Ax}||

:::

容易知道\mathbf{Ax}应该是\mathbf{y}在\mathcal{R}(A)上的正交投影，此时距离||\mathbf{r}||最小

由于\mathbf{r}=\mathbf{y-Ax}\perp\mathcal{R}(A)（减去以后只剩下了垂直的分量），因此\mathbf{b-Ax}\in\mathcal{R}(A)^{\perp}=\mathcal{N}(A^T)
关于为什么，请看这篇文章(*)
则
::: align-center
\mathbf{A}^T(\mathbf{b-Ax})=\mathbf{0}，得\mathbf{A}^T\mathbf{Ax}=\mathbf{A}^T\mathbf{b}

:::

等号左边\mathbf{A}^T\mathbf{Ax}\in\mathcal{R}(A^TA)，等号右边\mathbf{A}^T\mathbf{b}\in\mathcal{R}(A^T)，由上面(*)得方程等号两边在同一空间内，则方程一定有解

我们不妨设t_i不完全相同，则\mathbf{A}列满秩，则\mathbf{A}^T\mathbf{A}可逆，方程解唯一
::: align-center
\mathbf{x}=(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^T\mathbf{y}

:::
计算后我们就会发现这就是一元线性回归的结果

正则化方法

事实上，刚才我们已经得到了最小二乘问题的一种解法，即求解\mathbf{A}^T\mathbf{Ax}=\mathbf{A}^T\mathbf{b}，这称为正则化方法，结合LU分解可得正则化方法的一般求解基本步骤
LU分解请见这篇文章

1. 计算\mathbf{C}=\mathbf{A}^T\mathbf{A},\mathbf{d}=\mathbf{A}^T\mathbf{b}
2. 计算\mathbf{C}的LDLT分解
3. 求解下三角方程组\mathbf{Lz=d}（回代法）
4. 求解对角方程组\mathbf{Dy=z}
5. 求解上三角方程组\mathbf{L}^T\mathbf{x}=\mathbf{y}（前代法）

正交化方法

我们还可以使用正交化方法寻找\min_{x\in R^2}||\mathbf{y-Ax}||，这需要用到QR分解
QR分解请见这篇文章
假设\mathbf{A}的QR分解为\mathbf{A=QR}=\begin{bmatrix}Q_1 & Q_2\end{bmatrix}\begin{bmatrix}\mathbf{R_1}\\O\end{bmatrix}=\mathbf{Q_1R_1}，其中\mathbf{R_1}是经过重新分块后得到的行满秩矩阵

因为\mathbf{Q}是正交矩阵，则\mathbf{Q}^T也是正交矩阵，又因正交变换是保距变换，故
||\mathbf{y-Ax}||^2=||\mathbf{Q}^T(\mathbf{b-QRx})||^2=||\begin{bmatrix}\mathbf{Q_1}^Tb\\\mathbf{Q_2}^Tb\end{bmatrix}-\begin{bmatrix}\mathbf{R_1}\\O\end{bmatrix}\mathbf{x}||^2=||\mathbf{Q_1}^T\mathbf{b}-\mathbf{R_1x}||^2+||\mathbf{Q_2}^Tb||

此方程在\mathbf{Q_1}^T\mathbf{b}=\mathbf{R_1x}时最小，而\mathbf{R}是上三角矩阵，这意味着可用前代法方便求解，故正交化方法的一般求解步骤为

1. 计算\mathbf{A}的简化QR分解\mathbf{A=Q_1R_1}
2. 计算\mathbf{c=Q_1}^T\mathbf{b}
3. 求解上三角方程组\mathbf{R_1x=c}（前代法）