最小二乘问题总结

刺骨的言语ヽ痛彻心扉 2021-11-19 16:20 527阅读 0赞

### 最小二乘问题总结 ###

*  1.题外话
 *  2.最小二乘基础概念
 *  3.线性最小二乘问题的求解方法
 *  4.非线性最小二乘问题的求解方法
 *   *  4.1 最快下降法
     *  4.2 高斯牛顿法
     *  4.3 LM阻尼最小二乘法
     *  4.4 Dog-Leg最小二乘法

# 1.题外话 #

最近在学习深蓝学院的VIO课程，最小二乘问题的求解作为基础知识，在VIO的优化过程中非常重要。因此在这里对课程内容和查阅的资料做个总结，以便能够加深对最小二乘问题的理解。

# 2.最小二乘基础概念 #

最小二乘问题泛指具有如下形式的问题。  
 m i n f ( x ) = 1 2 ∑ i = 1 m r i 2 ( x ) (1) minf(x) =\\frac\{1\}\{2\}\\displaystyle\\sum\_\{i=1\}^\{m\}r\_\{i\}^2(x) \\tag\{1\} minf(x)=21i=1∑mri2(x)(1)

其中m一般指实例的个数， r i ( x ) r\_\{i\}(x) ri(x)指残差，即预测值与观测值的差， f ( x ) f(x) f(x)称为损失函数（或代价函数，cost function），根据模型的不同有线性模型和非线性模型，分为线性最小二乘和非线性最小二乘。

最小二乘问题的主要思想就是求解未知参数 ，使得预测值与观测值之差（即误差，或者说残差）的平方和达到最小。

最小二乘问题也可以写成如下的向量形式。

令  r ( x ) = ( r 1 ( x ) , r 2 ( x ) , r 3 ( x ) . . . r m ( x ) ) T r(x) = (r\_1(x),r\_\{2\}(x),r\_\{3\}(x)...r\_\{m\}(x))^T r(x)=(r1(x),r2(x),r3(x)...rm(x))T，则(1)式可表达为  
 f ( x ) = 1 2 ∣ ∣ r ( x ) ∣ ∣ 2 (2) f(x) = \\frac\{1\}\{2\}||r(x)||^2\\tag\{2\} f(x)=21∣∣r(x)∣∣2(2)

# 3.线性最小二乘问题的求解方法 #

线性最小二乘求解较为方便。我们假设模型为  
 y = θ 1 x 1 + θ 2 x 2 + θ 3 x 3 + . . . + θ n x n (3) y= \\theta\_\{1\} x\_\{1\}+\\theta\_\{2\} x\_\{2\}+\\theta\_\{3\} x\_\{3\}+...+\\theta\_\{n\} x\_\{n\}\\tag\{3\} y=θ1x1\+θ2x2\+θ3x3\+...\+θnxn(3)  
即  
 y = θ T ∗ x (4) y =\\theta^T \*\\boldsymbol x\\tag\{4\} y=θT∗x(4)

其中 θ = ( θ 1 , θ 2 , θ 3 , . . . , θ n ) T \\theta = (\\theta\_\{1\}, \\theta\_\{2\}, \\theta\_\{3\}, ... ,\\theta\_\{n\})^T θ=(θ1,θ2,θ3,...,θn)T ，  x = ( x 1 , x 2 , x 3 , . . . , x n ) T \\boldsymbol x= (x\_\{1\},x\_\{2\}, x\_\{3\}, ... ,x\_\{n\})^T x=(x1,x2,x3,...,xn)T。

假设有 m m m组样本，则预测值为  y i y\_\{i\} yi，测量值为  y ^ i = b i \\hat y\_\{i\}=b\_\{i\} y^i=bi， i ∈ ( 1... m ) i\\in(1...m) i∈(1...m)。则残差函数可以表示为  
 r i ( θ ) = y i − y ^ i = θ T ∗ x i − b i = \[ x 11 x 12 . . . x 1 n x 21 x 22 . . . x 2 n ⋮ x m 1 x m 2 . . . x m n \] \[ θ 1 θ 2 ⋮ θ n \] − \[ b 1 b 2 ⋮ b n \] = X θ − b (5) r\_\{i\}(\\theta) =y\_\{i\}-\\hat y\_\{i\} = \\theta^T \*\\boldsymbol x\_\{i\}-b\_\{i\}=\\left\[ \\begin\{matrix\} x\_\{11\} & x\_\{12\} &... & x\_\{1n\}\\\\ x\_\{21\} & x\_\{22\} &... & x\_\{2n\} \\\\ & \\vdots \\\\ x\_\{m1\} & x\_\{m2\} &... & x\_\{mn\} \\end\{matrix\}\\right\] \\left\[ \\begin\{matrix\} \\theta\_\{1\} \\\\ \\theta\_\{2\}\\\\ \\vdots \\\\ \\theta\_\{n\} \\end\{matrix\}\\right\]-\\left\[ \\begin\{matrix\} b\_\{1\} \\\\ b\_\{2\}\\\\ \\vdots \\\\ b\_\{n\} \\end\{matrix\}\\right\]=X\\theta-b\\tag\{5\} ri(θ)=yi−y^i=θT∗xi−bi=⎣⎢⎢⎢⎡x11x21xm1x12x22⋮xm2.........x1nx2nxmn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡θ1θ2⋮θn⎦⎥⎥⎥⎤−⎣⎢⎢⎢⎡b1b2⋮bn⎦⎥⎥⎥⎤=Xθ−b(5)

将其写成最小二乘的形式即为  
 f ( θ ) = 1 2 ∣ ∣ X θ − b ∣ ∣ 2 (6) f(\\theta) = \\frac\{1\}\{2\}||X\\theta-b||^2 \\tag\{6\} f(θ)=21∣∣Xθ−b∣∣2(6)

--------------------

线性最小二乘问题如何求解呢？

我们可以进行如下处理：  
 f ( θ ) = 1 2 ∣ ∣ X θ − b ∣ ∣ 2 = 1 2 ( θ T X T X θ − b T X θ − θ T X T b + b T b ) (7) f(\\theta) = \\frac\{1\}\{2\}||X\\theta-b||^2 = \\frac\{1\}\{2\}(\\theta^TX^TX\\theta-b^TX\\theta-\\theta^TX^Tb+b^Tb)\\tag\{7\} f(θ)=21∣∣Xθ−b∣∣2=21(θTXTXθ−bTXθ−θTXTb\+bTb)(7)

上式对 θ \\theta θ求导，并令导数等于零可得  
 ∂ f ( θ ) ∂ θ = X T X θ − X T b = 0 (8) \\frac\{\\partial f(\\theta) \}\{\\partial \\theta\}=X^TX\\theta-X^Tb = 0\\tag\{8\} ∂θ∂f(θ)=XTXθ−XTb=0(8)  
即  
 θ = ( X T X ) − 1 X T b (9) \\theta = (X^TX)^\{-1\}X^Tb\\tag\{9\} θ=(XTX)−1XTb(9)  
式(9)即为线性最小二乘问题的解的矩阵形式。

# 4.非线性最小二乘问题的求解方法 #

非线性最小二乘问题则不然，它要复杂得多，没有办法变换为矩阵方程形式，以至于它必须将问题化简为每一步均为可以直接求解的子问题，整个求解过程是迭代的。

求解非线性最小二乘问题的方法有很多种。为了介绍方便，我们重新表述一下最小二乘问题的形式。我们将最小二乘问题表述为：  
 F ( x ) = 1 2 ∑ i = 1 m f i 2 ( x ) = 1 2 ∣ ∣ f ( x ) ∣ ∣ 2 = 1 2 f ( x ) T f ( x ) (10) F(x) =\\frac\{1\}\{2\}\\displaystyle\\sum\_\{i=1\}^\{m\}f\_\{i\}^2(x) =\\frac\{1\}\{2\}||f(x)||^2=\\frac\{1\}\{2\}f(x)^Tf(x) \\tag\{10\} F(x)=21i=1∑mfi2(x)=21∣∣f(x)∣∣2=21f(x)Tf(x)(10)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 1]

## 4.1 最快下降法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 2]

## 4.2 高斯牛顿法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 4]

## 4.3 LM阻尼最小二乘法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][20190829221547581.jpg]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 7]

## 4.4 Dog-Leg最小二乘法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][20190829222612572.jpg]

https://blog.csdn.net/fangqingan\_java/article/details/48951191  
https://blog.csdn.net/qq\_40913605/article/details/86675157  
https://zhuanlan.zhihu.com/p/38128785  
https://blog.csdn.net/jinshengtao/article/details/89066810  
https://blog.csdn.net/stihy/article/details/52737723?hmsr=toutiao.io&utm\_medium=toutiao.io&utm\_source=toutiao.io  
https://blog.csdn.net/baoxiao7872/article/details/79914083

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70]: /images/20211119/d04b0cc494364201b6adfb6ec55eb452.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 1]: /images/20211119/32b572152e504dd69a47225474d9ce9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 2]: /images/20211119/be4aa1f22e794c3faaefd8bef5b902b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 3]: /images/20211119/9be2ad57826348ae848ec63f4e08eae9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 4]: /images/20211119/a5b8dd1f518e4f7cb44940756ecf1425.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 5]: /images/20211119/c224465edb32473a91d9c90f89fb91cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 6]: /images/20211119/cebdef73222540e28a766da295972a44.png
[20190829221547581.jpg]: /images/20211119/d9298e61f3d14f2aa2d729db2018bdf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 7]: /images/20211119/9a6de4bea3ff45c1aaf26b1e2e5af6a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 8]: /images/20211119/a54d5c54f3df41a7a52ffb20ec0dd138.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 9]: /images/20211119/d0c02daa062e415fad8d65455b58123b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 10]: /images/20211119/aa4c1ca0f1c64c4db253fad34388bd1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 11]: /images/20211119/d554ff3648e04107bb5d68e1cb4f3790.png
[20190829222612572.jpg]: /images/20211119/e8eb695824e340bdb7b97489b31202de.png