线性和非线性最小二乘问题的各种解法

您所在的位置：网站首页 › 残差曲线收敛大于1 › 线性和非线性最小二乘问题的各种解法

线性和非线性最小二乘问题的各种解法

2023-03-11 11:24| 来源: 网络整理| 查看: 265

Author:盒子先生KingO 码字不易，欢迎点赞关注，欢迎私信交流。以下内容为个人学习笔记，参考网址见文末。一、最小二乘问题概念

最小二乘问题是为了找到测量值和模型预测值之间的最小误差，该问题可以简单的表示为：

$\min \|\text{模型} - \text{误差} \|^2 = \min_x\| e(x) \|^2 \\$ SLAM过程可以转化为最大似然估计问题，而最大似然估计问题可以转化为最小二乘问题。

假设目标函数为 F(x) ，误差函数为 f(x) ，则其最小二乘可以表示为：

$\min F(x)=\frac{1}{2}\|f(x)\|_{2}^{2} \\$ 其中， F(x) 为损失函数， f(x) 为残差函数，定义为：

$\mathbf{F}(\mathbf{x})=\frac{1}{2} \sum_{\mathrm{i}=1}^{\mathrm{m}}\left(\mathrm{f}_{\mathrm{i}}(\mathbf{x})\right)^{2}=\frac{1}{2} \mathbf{f}^{\top}(\mathbf{x}) \mathbf{f}(\mathbf{x})=\frac{1}{2}\|\mathbf{f}(\mathbf{x})\|_{2}^{2} \\$

若残差函数

为线性函数，则问题为：线性最小二乘问题若残差函数 f(x)

为非线性问题，则问题为：非线性最小二乘问题二、线性最小二乘问题：非齐次方程组，Ax = b

$\min _{x}\|A x-b\| \\$

2.1 正规方程组(对于线性超定方程组： $A\in R^{m \times n}$ , m n

)

A^TAx = A^Tb

需要求

的逆2.2 QR分解( $A\in R^{m\times n}$ ，

， $\text{rank}(A) = n$ ， A^TA

对称且可逆)

$\min_x{\|Ax-b\|}=\min_x{\|QRx-b\|}=\min_x{Rx-Q^Tb} \\$

2.3 Cholesky分解( $A\in R^{m\times n}$ ，

， $\text{rank}(A) = n$ ， A^TA

对称且可逆)

$A^TA = LL^T \\$

$A^TAx = A^Tb \\$

$LL^Tx= A^Tb \longrightarrow L^Tx = y, \, \,Ly = A^Tb \\$

2.4 SVD分解(对于亏秩超定方程组： $A\in R^{m\times n}$ ， $\text{rank}(A) = rn$ )

$\mathrm{A}=\mathrm{U}_{\mathrm{m} \times \mathrm{m}}\left[\begin{array}{cc}\sum_{\mathrm{r} \times \mathrm{r}} & 0_{\mathrm{r} \times(\mathrm{n}-\mathrm{r})} \\0_{(\mathrm{m}-\mathrm{r}) \times \mathrm{r}} & 0_{(\mathrm{m}-\mathrm{r}) \times(\mathrm{n}-\mathrm{r})}\end{array}\right] \mathrm{V}_{\mathrm{n} \times \mathrm{n}}^{\mathrm{T}} \\$

$U^TU=E,\, V^TV=E \\$

$\begin{array}{l}\underset{\mathrm{x}}{\arg \min }\|\mathrm{Ax}-\mathrm{b}\|_{2}^{2}=\underset{\mathrm{x}}{\arg \min }\left\|\mathrm{U}^{\mathrm{T}} \mathrm{Ax}-\mathrm{U}^{\mathrm{T}} \mathrm{b}\right\|_{2}^{2}\\=\underset{\mathrm{x}}{\arg \min }\left\|\mathrm{U}^{\mathrm{T}} \mathrm{U}\left[\begin{array}{cc}\Sigma & 0 \\0 & 0\end{array}\right] \mathrm{V}^{\mathrm{T}} \mathrm{x}-\mathrm{U}^{\mathrm{T}} \mathrm{b}\right\|_{2}^{2}\\=\underset{\mathrm{x}}{\arg \min }\left\|\left[\begin{array}{cc}\Sigma & 0 \\0 & 0\end{array}\right] \mathrm{V}^{\mathrm{T}} \mathrm{x}-\mathrm{U}^{\mathrm{T}} \mathrm{b}\right\|_{2}^{2}\\=\underset{\mathrm{x}}{\arg \min }\left\|\left[\begin{array}{cc}\Sigma & 0 \\0 & 0\end{array}\right]\left[\begin{array}{l}\alpha_{1} \\\alpha_{2}\end{array}\right]-\left[\begin{array}{l}\beta_{1} \\\beta_{2}\end{array}\right]\right\|_{2}^{2}\\=\underset{\mathrm{x}}{\arg \min }\left\|\left[\begin{array}{c}\Sigma \alpha_{1} \\0\end{array}\right]-\left[\begin{array}{l}\beta_{1} \\\beta_{2}\end{array}\right]\right\|_{2}^{2}\\=\underset{\mathrm{x}}{\arg \min }\left\|\Sigma \alpha_{1}-\beta_{1}\right\|_{2}^{2}+\left\|\beta_{2}\right\|_{2}^{2}\\\rightarrow \Sigma \alpha_{1}=\beta_{1}\\\left[\begin{array}{l}\alpha_{1} \\\alpha_{2}\end{array}\right]=\mathrm{V}^{\mathrm{T}} \mathrm{x},\left[\begin{array}{l}\beta_{1} \\\beta_{2}\end{array}\right]=\mathrm{U}^{\mathrm{T}} \mathrm{b}\\\alpha_{1}=\Sigma^{-1} \beta_{1}, \mathrm{x}=\mathrm{V}\left[\begin{array}{l}\alpha_{1} \\\alpha_{2}\end{array}\right]\end{array} \\$

在上面的解法中，由于 $\alpha_2$ 是一个任意向量，因此求出的不是唯一的。即亏秩方程的最小二乘解不唯一。可以选择范数最小的最小二乘解作为亏秩方程的解，即 $\alpha_2=\vec 0$ 。

可以通过正交矩阵分块，将SVD最小二乘解进一步化简：

$\begin{array}{c}\mathrm{U}=\left[\mathrm{U}_{1}, \mathrm{U}_{2}\right], \mathrm{V}=\left[\mathrm{V}_{1}, \mathrm{~V}_{2}\right] \\\mathrm{U}_{1} \in \mathrm{R}^{\mathrm{m} \times \mathrm{r}}, \mathrm{V}_{1} \in \mathrm{R}^{\mathrm{n} \times \mathrm{r}} \\\alpha_{1}=\Sigma^{-1} \beta_{1} \\{\left[\begin{array}{l}\alpha_{1} \\\alpha_{2}\end{array}\right]=\left[\begin{array}{l}\mathrm{V}_{1}^{\mathrm{T}} \\\mathrm{V}_{2}^{\mathrm{T}}\end{array}\right] \mathrm{x}} \\{\left[\begin{array}{l}\beta_{1} \\\beta_{2}\end{array}\right]=\left[\begin{array}{l}\mathrm{U}_{1}^{\mathrm{T}} \\\mathrm{U}_{2}^{\mathrm{T}}\end{array}\right] \mathrm{b}} \\\mathrm{V}_{1}^{\mathrm{T}} \mathrm{x}=\Sigma^{-1} \mathrm{U}_{1}^{\mathrm{T}} \mathrm{b} \\\mathrm{x}=\mathrm{V}_{1} \Sigma^{-1} \mathrm{U}_{1}^{\mathrm{T}} \mathrm{b}\end{array} \\$

SVD也适用于列满秩矩阵的最小二乘求解，实际上SVD分解是最常用的线性最小二乘解法之一。

三、线性最小二乘问题：齐次方程，Ax=03.1 超定齐次方程组

对于齐次方程组 $A_{m\times n} = 0,mn$ ，其最小二乘解就是 的SVD分解后的 的最后一个列向量。

证明： $\begin{array}{c}\mathrm{A}=\mathrm{U}\left[\begin{array}{c}\Sigma \\0\end{array}\right] \mathrm{V}^{\mathrm{T}} \\\mathrm{Ax}=\mathrm{U}\left[\begin{array}{c}\Sigma \\0\end{array}\right] \mathrm{V}^{\mathrm{T}} \mathrm{x}=0 \\\mathrm{y}=\mathrm{V}^{\mathrm{T}} \mathrm{x}, \Sigma \mathrm{y}=0\end{array} \\$ 也就是说，求 Ax=0

，转换为求 $\sum y =0$ 的最小二乘解 $\begin{aligned}& \underset{\mathrm{y}}{\arg \min }\|\Sigma \mathrm{y}\|_{2}^{2} \\=& \underset{\mathrm{y}}{\arg \min } \mathrm{y}^{\mathrm{T}} \Sigma^{\mathrm{T}} \Sigma \mathrm{y} \\=& \underset{\mathrm{y}}{\arg \min } \sum_{\mathrm{i}=1}^{\mathrm{n}} \sigma_{\mathrm{i}}^{2} \mathrm{y}_{\mathrm{i}}^{2} \\& \text { s.t. } \quad\|\mathrm{y}\|0\end{aligned} \\$ $\sum$ 对角线元素由大到小排列，则满足： $\mathrm{y}=\left[0,0, \ldots, 0, \mathrm{y}_{\mathrm{n}}\right]^{\mathrm{T}}, \mathrm{y}_{\mathrm{n}} \neq 0$ 时，获得 $\sum y$ 的最小二乘解。 $\mathrm{V}^{\mathrm{T}} \mathrm{x}=\mathrm{y}, \mathrm{x}=\mathrm{V} \mathrm{y}=\mathrm{y}_{\mathrm{n}} \mathrm{v}_{\mathrm{n}}\\ if \quad\|\mathrm{y}\|_{2}=1\\ then\quad\mathrm{x}=\mathrm{v}_{\mathrm{n}} \\$ 进一步，超定齐次线性方程组 Ax=0

的最小二乘解还等于

的最小特征值对应的特征向量：

$\begin{array}{c}\mathrm{A}=\mathrm{U}\left[\begin{array}{c}\Sigma \\0\end{array}\right] \mathrm{V}^{\mathrm{T}} \\\mathrm{A}^{\mathrm{T}} \mathrm{A}=\mathrm{V}\left[\begin{array}{ll}\Sigma & 0\end{array}\right]\left[\begin{array}{l}\Sigma \\0\end{array}\right] \mathrm{V}^{\mathrm{T}}=\mathrm{V}^{2} \mathrm{~V}^{\mathrm{T}} \\\mathrm{A}^{\mathrm{T}} \mathrm{Ax}=\mathrm{V} \Sigma^{2} \mathrm{~V}^{\mathrm{T}} \mathrm{x}=0 \\\mathrm{y}=\mathrm{V}^{\mathrm{T}} \mathrm{x}, \Lambda=\Sigma^{2}, \Lambda \mathrm{y}=0\end{array}\\$

四、非线性最小二乘问题

常规的思路就是对目标函数 F(x) 进行求导，当其导数为0的时候，求的最优解，最终求得最优值。

注：导数为0的点，不一定是极值点，也可能是鞍点。

然后，若 F(x) 不容易直接求导，这是需要使用迭代法，使得 F(x) 下降，逐步迭代，取得最小值，流程如下：

给定某个初始值 $x_{0}$ ；对于第

次迭代，寻找一个增量 $\Delta x_{k}$ ，使得误差 $\left|f\left(x_{k}+\Delta x_{k}\right)\right|_{2}^{2}$ 达到极小值；若 $\Delta x_{k}$ 足够小，则停止迭代：否则，令 $x_{k+1}=x_{k}+\Delta x_{k}$ ，返回第2步。

此时，最小二乘问题变成了如何寻找下降增量 $\Delta x_k$ 。

非线性优化的所有迭代求解方案，都需要用户提供一个 良好的初始值。

4.1 牛顿法

对于一元函数 f(x) ，对其在 x=x_0 处进行二阶泰勒展开：

$f(x)=f\left(x_{0}\right)+f^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)+\frac{f^{\prime \prime}\left(x_{0}\right)}{2}\left(x-x_{0}\right)^{2}+o\left(x-x_{0}\right)^{2} \\$

忽略二阶及以上项。

$g(x)=f\left(x_{0}\right)+f^{t}\left(x_{0}\right)\left(x-x_{0}\right)+\frac{f^{\prime \prime}\left(x_{0}\right)}{2}\left(x-x_{0}\right)^{2} \\$

$g^{\prime}(x)=f^{t}\left(x_{0}\right)+f^{\prime \prime}\left(x_{0}\right)\left(x-x_{0}\right) \\$

令 g'(x_1)=0 ，此时 x_1 就是极值。

故：

$f^{\prime}\left(x_{0}\right)+f^{\prime \prime}\left(x_{0}\right)\left(x_{1}-x_{0}\right)=0\\$

则：

$x_{1}=x_{0}-\frac{f^{\prime}\left(x_{0}\right)}{f^{\prime \prime}\left(x_{0}\right)} \\$

以此类推，可以得到迭代公式：

$x_{n+1}=x_{n}-\frac{f^{\prime}\left(x_{n}\right)}{f^{\prime \prime}\left(x_{n}\right)} \\$

一般来说，矩阵一阶导数称作雅可比矩阵，二阶导数矩阵称作海塞矩阵，所以迭代形式变为：

$\Delta x=-\frac{f^{\prime}\left(x_{n}\right)}{f^{\prime \prime}\left(x_{n}\right)}=-\frac{J}{H} \\$

即：

$H\Delta x = -J \\$

特点：

要求给定的方程需要二阶可导非凸函数的海森矩阵不一定有逆数据较大的时候，海塞矩阵的计算量偏大适用于最优值附近4.2 梯度下降法

梯度下降是用于找到可微函数的局部最小值的一阶迭代优化算法，为了使用梯度下降找到函数的局部最小值，采取与该数在当前点的梯度（或近似梯度）的负值成比例的步骤。

梯度下降法基于以下观测原理得到：

如果实值函数 f(x) 在点 x=a 处可微且有定义，那么函数 f(x) 在点处，沿着梯度的反方向 $-\Delta f(a)$ 下降的最快。

假设点，满足：

$b=a-\gamma \Delta f(a) \quad \text { s.t } \quad \gamma0 \quad \& \quad \gamma \rightarrow 0 \\$

那么：

$f(a)\ge f(b) \\$

通过这种方式，可以找到极小值。

迭代公式：

$x_{n+1}=x_{n}-\gamma \Delta f\left(x_{n}\right) \\$

缺点：

梯度下降法每次都以梯度的反方向下降，所以，有可能会容易走出锯齿路线，从而增加迭代次数。适用于迭代的开始阶段，最优值附近震荡，收敛慢4.3 高斯牛顿法

牛顿法和梯度下降法都是针对目标函数 F(x) 来进行求解的，这样不可避免地需要求解海塞矩阵。为了避免该问题，直接对误差函数 f(x) 进行优化求解。

对 $f(x+\Delta x)$ 进行一阶泰勒展开：

$f(x+\Delta x) \approx f(x)+J(x)^{T} \Delta x+o(\Delta x) \\$

最小二乘问题即求 $\Delta x$ 使 $|f(x+\Delta x)|_{2}^{2}$ 有最小值。

$\Delta x^{*}=\arg \min \frac{1}{2}\|f(x+\Delta x)\|_{2}^{2} \approx \arg \min \frac{1}{2}\left\|f(x)+J(x)^{T} \Delta x\right\|_{2}^{2} \\$

展开得：

$\begin{array}{l}m(x)=\frac{1}{2}\left\|f(x)+J(x)^{T} \Delta x\right\|^{2}=\frac{1}{2}\left(f(x)+J(x)^{T} \Delta x\right)^{T}\left(f(x)+J(x)^{T} \Delta x\right) \\=\frac{1}{2}\left(\|f(x)\|^{2}+2 f(x) J(x)^{T} \Delta x+\Delta x^{T} J(x) J(x)^{T} \Delta x\right.\end{array} \\$

为了求极值，对其求导：

$m^{\prime}(x)=J(x) f(x)+J(x) J(x)^{T} \Delta x \\$

令 m'(x) = 0 ，则：

$J(x) J(x)^{T} \Delta x=-J(x) f(x) \\$

优点：

避免求海塞矩阵，减小计算量

缺点：

只有半正定性，当为奇异矩阵时，稳定性差，算法不收敛。如果求出来的步长 Δx_k

太大，会导致其局部近似不精确，严重的时候，可能无法保证迭代收敛容易和梯度下降法一样，陷入锯齿状，导致迭代次数较长。4.4 列文伯格-马夸特法(LM法)

该方法是在高斯牛顿法的基础上进行的改进，基本思路和高斯牛顿法一样。

在高斯牛顿法的缺点中，可以看到，有一点使容易进入锯齿状，导致迭代的次数较长。所以，为了避免其步长过大导致的问题，该方法提出了信赖区域 ，设定一个区域。使得步长能够受到控制。

在更新迭代的过程中，为了判定近似值的好坏，设定了一个评判指标：

$\rho=\frac{f(x+\Delta x)-f(x)}{J(x)^{T} \Delta x} \\$

$\rho$ 接近1，近似是好的，不需要更改 $\rho$ 太小，则实际减少的值小于近似减少的值，近似较大，需要缩小近似的范围； $\rho$ 太大，则实际减少的值大于近似减少的值，近似较小，需要扩大近似的范围；

算法流程：

1、给定某个初始值 $x_{0}$ ；

2、对于第次迭代，在高斯牛顿法的基础上加入信赖区域 :

$\min \frac{1}{2}\left\|f\left(x_{k}\right)+J\left(x_{k}\right)^{T} \Delta x_{k}\right\|^{2}, \quad s.t \quad\left\|D \Delta x_{k}\right\|^{2} \leq \mu \\$

其中， $\mu$ 是信赖半径，为系数矩阵。

3、计算近似指标 $\rho$ :

$\rho=\frac{f(x+\Delta x)-f(x)}{J(x)^{T} \Delta x} \\$

4、根据经验值，设定 :

若 $\rho\frac{3}{4}$ ，则设置 $\mu=2 \mu$ ，跳转第6步；若 $\rho\frac{1}{4}$ ，则设置 $\mu=0.5 \mu$ ，跳转第6步；若 $\rho$ 大于设定的阈值，则跳转至第5步，求解 $\Delta x_{k}$ ，令 $x_{k+1}=x_{k}+\Delta x_{k}$ 。

5、求解增量方程 : $(H+\lambda I) \Delta x_{k}=g$

6、若 $\Delta x_{k}$ 足够小，则停止迭代，否则，返回第2步。

增量方程，通过拉格朗日函数求解：

$\min \frac{1}{2}\left\|f(x)+J(x)^{T} \Delta x\right\| \quad \text { s.t } \quad\|D \Delta x\mu\|_{2} \\$

构建拉格朗日函数， $\lambda$ 是系数因子：

$L(\Delta x, \lambda)=\frac{1}{2}\left\|f(x)+J(x)^{T} \Delta x\right\|^{2}+\frac{\lambda}{2}\left(\|D \Delta x\|^{2}-\mu\right) \\$

化简后求导：

$J(x) f(x)+J(x) J^{T}(x) \Delta x+\lambda D^{T} D \Delta x=0 \\$

即：

$\left(J J^{T}+\lambda D^{T} D\right) \Delta x=-J f \\$

通常用来代替 D^TD ，即：

$(JJ^T+\lambda I) \Delta x = -Jf \\$

4.5 四种优化总结

设定最小二乘问题为：

$\min F(x)=\frac{1}{2}\|f(x)\|_{2}^{2} \\$

针对

进行优化梯度下降法和牛顿法分别是对 F(x)

进行一阶泰勒展开和二阶泰勒展开然后求导令0的结果，针对 f(x)

进行优化高斯牛顿法是对 f(x)

进行一阶泰勒展开，代入 F(x)

求导令0的结果 LM法可以看作是梯度下降法和高斯牛顿法的结合： $\lambda$ 较大的时候，公式变为梯度下降法 $\lambda$ 较小的时候，公式变为高斯牛顿法4.6 鲁棒核函数（M估计）

在前面的非线性最小二乘问题中，我们最小化误差项的二范数平方和，作为目标函数。当出现误匹配时，误差就会很大，如果我们再使用平方，这个误差就会更大。算法将试图调整这条边所连接的节点的估计值，使它们顺应这条边的无理要求。由于这个边的误差真的很大，往往会抹平了其他正确边的影响，使优化算法专注于调整一个错误的值。

出现这种问题的原因是，当误差很大时，二范数增长得太快了。于是就有了核函数的存在。 核函数保证每条边的误差不会太大以至于掩盖掉其他的边。这种核函数称之为鲁棒核函数。

常见的鲁棒核函数有Huber 核：

$\mathrm{H}(\mathrm{e})=\left\{\begin{array}{ll}\frac{1}{2} \mathrm{e}^{2} & \text { if }|\mathrm{e}|\delta \\\delta\left(|\mathrm{e}|-\frac{1}{2} \delta\right) & \text { otherwise }\end{array}\right. \\$

当误差大于某个阈值 $\delta$ 后，函数增长由二次形式变成了一次形式，相当于限制了梯度的最大值。同时，Huber 核函数又是光滑的，可以很方便地求导。

参考网址

https://zhuanlan.zhihu.com/p/113946848

https://blog.csdn.net/u011178262/article/details/120816301

https://blog.csdn.net/qq_41035283/article/details/121605035

【本文地址】

线性和非线性最小二乘问题的各种解法

线性和非线性最小二乘问题的各种解法

今日新闻

推荐新闻