slam数学基础——最小二乘

2023-11-06

一、前言

1. 最小二乘是一类特殊形式的最优化求解问题，相比于其他优化问题，求解方式比较简洁

2.最小二乘被广泛应用于各种实际问题的建模，在求解实际工程问题中有着广泛的应用，例如 slam 中随处可见最小二乘的声影

二、线性最小二乘法

1. 预备知识

1. $A\in R^{m,n}$ , rank(null_space) + rank(A) = n

2. 齐次线性方程组求解

$Ax=0, A\in R^{m,n}, x\in R^n, 0\in R^m$ (1)

$x=0$ 肯定是该方程组的一个解

a. 存在唯一零解: rank(null_space) = 0, 等价于 rank(A) = n. 等价于 $A$ 的各个列向量线性无关

b. 存在除了零解以外的其他解: rank(null_space)>0, 等价于 rank(A) < n，等价于 $A$ 的各个列向量线性相关

3. 非齐次线性方程组求解

$Ax=b, A\in R^{m,n}, x\in R^n, b\in R^m$ (2)

解的形式: 特解+通解: 若 $x_1$ 是 $Ax=0$ 的解， $x_2$ 是 $Ax=b$ 的一个解，那么 $x_1+x_2$ 也是 $Ax=b$ 的一个解

a. 没有解: $b$ 向量不在 $A$ 的列向量张成的向量空间

b. 唯一解: $b$ 向量在 $A$ 的列向量张成的向量空间, 且 rank(null_space) = 0 ( $x_1$ 只有唯一零解 )

c. 无穷多个解: $b$ 向量在 $A$ 的列向量张成的向量空间, 且 rank(null_space) > 0 ( $x_1$ 有多个解 )

2. 非齐次最小二乘

1. 定义

$x=argmin_{x} ||Ax-b||^2$ (3)

2.和求解线性方程组的联系

当求解(2)时，若该方程无原始解满足该方程，那么这时候需要求一个最小二乘解 ${x}'$ ，也就是等价于求解 (3)

注意：最小二乘解并不是原始解

3. 求解

$A{x}'$ 在 $A$ 的列向量张成的向量空间， $b$ 向量不在 $A$ 的列向量张成的向量空间，若要使得 $b-Ax'$ 最小，

当且仅当 $b-Ax'$ 与 $A$ 的列向量张成的向量空间的正交时， $b-Ax'$ 最小，如下图:

那么有 $A^T*(b-Ax')=0$ (4)

得到 $A^T* Ax'=A^T*b$ (5)

最后通过求解式(5) 可以得到最小二乘解， (5) 可以通过 SVD 求解

3. 齐次最小二乘

1. 定义

$x=argmin_{x} ||Ax||^2, s.t. ||x||=1$ (6)

2.和求解线性方程组的联系

当求解(1)时，若该方程没有非零解满足该方程，那么那么这时候需要求一个最小二乘解 ${x}'$ ，也就是等价于求解 (6)

3. 求解

将矩阵 A SVD 分解， $A=UDV^T$ (7)

展开为: $A=UDV^T = \begin{pmatrix} u_{1} & u_{2} & \cdots & u_r \end{pmatrix} * \begin{pmatrix} \sigma_1 & \cdots & \cdots& 0\\ 0 & \sigma_2 & \cdots & 0 \\ \vdots &\vdots & \ddots & \vdots\\ 0 & \cdots & \cdots& \sigma_r \end{pmatrix} * \begin{pmatrix} v_1^T \\ v_2^T \\ \vdots \\ v_r^T \\ \end{pmatrix}$ (8)

其中 $r$ 为矩阵的秩, $U$ ， $V$ 的各个列向量互相正交，且对角矩阵中的奇异值按照从大到小的顺序排列，那么有：

$A=UDV^T = \sigma_1*u_1*v_1^T + \sigma_2*u_2*v_2^T + .... + \sigma_r*u_r*v_r^T$ (9)

结论: 最小二乘解 ${x}'$ 是最小奇异值对应的 $V$ 的列向量 $v_r$

此时， $A*x'= \sigma_1*u_1*v_1^T*v_r + \sigma_2*u_2*v_2^T*v_r + .... + \sigma_r*u_r*v_r^T*v_r$

$= 0 + 0 + ... + \sigma_r = \sigma_r$ (10)

若取 $V$ 的其他列向量， $A*x'=\sigma_i (i\neq r ) > \sigma_r$

三、非线性最小二乘

1. 定义

$x=argmin_{x} ||f(x)-b||^2$ (11)

2. 求解流程

局部泰勒展开，求迭代 $\bigtriangleup x$ , 然后有： $x^{k+1}=x^{k} + \bigtriangleup x$ (12)

3. Gauss-Newton 法

四、非线性和线性最小二乘的讨论

1. 线性最小二乘对应全局最优解，非线性最小二乘无法保证全局最优，最终结果受初始值影响较大，容易陷入局部最优

2. 线性最小二乘: 若坐标用齐次坐标表示，对应齐次最小二乘；若坐标用非齐次坐标表示，对应非齐次最小二乘

3. 线性最小二乘不用迭代，可通过SVD求解效率高。非线性最小二乘需要迭代求解，求解时间不可控

4. 一般线性最小二乘对应着 DLT 算法，作为初始值。非线性最小二乘通过最小化某些 error_term，对线性求解的结果进一步优化. 例如求解单应性矩阵

5. 举例: 二维平面直线拟合

a. 非齐次线性最小二乘: y=kx+b, error = y_mea - y_predict

b. 非齐次最小二乘: ax+by+c=0

c. 非线性最小二乘: error = y_mea 到直线的距离

五、M-Esimation

1. 引入 Loss function，抑制 outliers

六、Reference

1. MIT：Gilbert Strang Linear Algebra （公开课）
2. Robotics-perception - University of Pennsylvania- Jianbo Shi （公开课）

声明：本博客内容原创，谢绝转载，若有错误的地方，还请及时指出。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

slam 基础

Slam