最小二乘法的求解

1.最小二乘法的求解

已知有一个这样的方程组：

Ax=b$Ax=b$

其中A∈Rm×n$A\in R^{m\times n}$ ; x∈Rn×k$x\in R^{n\times k}$, b∈Rm×k$b\in R^{m\times k}$

当 m=n$m=n$ 时，且 ranA=n$ranA=n$ 时，这是一个适定方程组，有唯一解 x=A−1b$x=A^{-1}b$

当 m<n$m<n$ 时，或者 ranA<n$ranA<n$ 时，这是一个欠定方程组，有无穷多个解。对于这种情况，我们使用 ran(A)$ran(A)$ 中与 b$b$ 距离最近的向量对应的 x$x$ 作为最小二乘解。而相应的 ran(A)$ran(A)$ 中的这个向量就是 b$b$ 在空间 ran(A)$ran(A)$ 中的投影。

当 m>n$m>n$ 时，即方程的个数大于未知数的个数，最小二乘超定系统问题。

超定问题是最小二乘的关键，最小二乘的的意思就是最小化残差(residual)的平方和。

给定 m$m$ 个数据，(a1,b1)$(a_1,b_1)$, (a2,b2)$(a_2,b_2)$,…,(am,bm)$(a_m,b_m)$, 以及一个模型函数 b=f(a,x)$b=f(a,x)$ ，其中{x1,x2,...,xn}$\{x_1,x_2,...,x_n\}$就是要估计的参数，该参数的估计就是通过最小化如下残差的平方和求得：

S=∑mi=1∥bi−f(ai,xi)∥2$S=\sum _{i=1}^m\Vert b_i-f(a_i,x_i){\Vert }^2$

其中残差为 ri=bi−f(ai,xi)$r_i=b_i-f(a_i,x_i)$ 根据残差函数关于未知参数是否线性，可以最把小二乘分为线性最小二乘和非线性最小二乘。

我们一般讨论的是线性最小二乘法。

线性最小二乘是解决线性回归问题的常用方法，有一个闭式解。线性最小二乘残差函数可以表示为：ri=bi−aixi$r_i=b_i-a_i{x}_i$

另最小二乘的几何表示：

如图所示，b$b$ 不在 rand(A)$rand(A)$ 中，所以 Ax_0是$是$ran(A)空间对向量$空间对向量$b$ 在欧式空间范数下的最好估计。此时

∀x∈Rn,(Ax,b−Ax0)=0$\mathrm{\forall }x\in R^n,(Ax,b-A{x}_0)=0$

等价于 xTAT(b−Ax0)=0$x^T{A}^T(b-A{x}_0)=0$

由于x的任意性，所以

AT(b−Ax0)=0$A^T(b-A{x}_0)=0$

整理得 x0=(ATA)−1ATb=A+b$x_0=(A^{T}A{)}^{-1}{A}^{T}b=A^{+}b$

其中 A+=(ATA)−1AT$A^{+}=(A^{T}A{)}^{-1}{A}^T$ 称为 A$A$ 的伪逆矩阵。

2.数值解法

原问题等价于： min∥Ax−b∥22$min\Vert Ax-b{\Vert }_2^2$

记 f(x)=∥Ax−b∥22=(Ax−b)T(Ax−b)=xTATAx−2bTAx+bTb$f(x)=\Vert Ax-b{\Vert }_2^2=(Ax-b{)}^T(Ax-b)=x^T{A}^{T}Ax-2b^{T}Ax+b^{T}b$ ，对 x 求导得：

Δf=2(ATAx−ATb)=0$\mathrm{\Delta }f=2(A^{T}Ax-A^{T}b)=0$

解得，x=(ATA)−1ATb=A+b$x=(A^{T}A{)}^{-1}{A}^{T}b=A^{+}b$

SVD数值分解

原问题：min∥Ax−b∥$min\Vert Ax-b\Vert$ ，∥..∥$\Vert ..\Vert$ 代表范数，取欧几里德范数，让每个方程的误差平方和最小，就是求取解 xi$x_i$ 使得 Ax−b$Ax-b$ 的误差最小，即等式最逼近真实值。

将矩阵 A$A$ 进行SVD分解：A=UΣ2VT$A=U{\mathrm{\Sigma }}^2{V}^T$ ，矩阵 A 的伪逆矩阵为 X+=VΣ+UT$X^{+}=V{\mathrm{\Sigma }}^{+}{U}^T$；

所以 x=X+b=VΣ+UTb$x=X^{+}b=V{\mathrm{\Sigma }}^{+}{U}^{T}b$，其中，Σ+${\mathrm{\Sigma }}^{+}$ 是 Σ$\mathrm{\Sigma }$ 的伪逆矩阵，可以通过对其对角线的元素求倒数，然后转置得到。

x=VΣ+UTb$x=V{\mathrm{\Sigma }}^{+}{U}^{T}b$

QR分解

将矩阵 A∈Rm×n$A\in R^{m\times n}$进行QR分解：Q$Q$ 为一个 m×n 的正交矩阵，R$R$ 为一个 n×n 的下三角矩阵，

将误差写成如下形式：r=b−Ax$r=b-Ax$ ，再对矩阵 A$A$ 进行 QR$QR$ 分解，得 A=QR$A=QR$ ，

则误差式可以写成： r=b−QRx$r=b-QRx$ ；等式两边同时左乘一个 QT$Q^T$ 矩阵，得 QTr=QTb−QTQRx$Q^{T}r=Q^{T}b-Q^{T}QRx$ ；由于 QTQ$Q^{T}Q$ 是一个 m×m 的单位矩阵，所以可以分为两个部分：n×n 和 (m-n)×(m-n) ，分别用 u$u$ 和 v$v$ 表示，这样残差平方和函数变为：

S=∥r∥2=rTr=rTQQTr=uTu+vTv$S=\Vert r{\Vert }^2=r^{T}r=r^{T}Q{Q}^{T}r=u^{T}u+v^{T}v$

由于 v∈R(m−n)×(m−n)$v\in R^{(m-n)\times (m-n)}$ 和 x∈Rn×k$x\in R^{n\times k}$ 没有关系，所以当 误差 u=0$u=0$ 时，才能使得残差的平方和 S$S$ 最小，即 因为 Rx=QTb$Rx=Q^{T}b$ ；R$R$ 为下三角矩阵，所以通过回代可以很容易地求解出 x$x$ 的值。

最终： Rx=QTb$Rx=Q^{T}b$

在实际应用中，因为数值稳定性的要求 ，dense matrix 往往用QR求解 ，对于大型的稀疏矩阵则多用Cholesky分解（LU分解）。