0.0 看到一个讨论：跨学科不同思考角度

最小二乘准确来说是损失函数，梯度下降是优化方法。
线性最小二乘的超定方程通常可以通过一步解法、SVD分解来求解；
非线性的最小二乘可以通过牛顿高斯迭代、LM算法、梯度下降求解。

1.0 齐次线性方程组的解、SVD、线性最小二乘法

链接：https://blog.csdn.net/DSbatigol/article/details/9625211

1.1 齐次线性方程组

AX=0
在非齐次方程组中，A到底有没有解析解，由增广矩阵来判断：
(r(A | b) =r(A | 0)=r(A) )

r(A)=未知数个数n（约束较强）
1.A是方阵
由克莱姆法则可知：
如果A是n*n的方阵而且r（A）=n，那么该方程组有唯一的零解。
2.A不是方阵，A是m×n的(m>n)
由另一个定理：齐次线性方程解空间维数 = n - r(A) 可知，该解空间维数为0, 也就是说该解空间只含有零向量。

1.1.1.2 r(A)<未知数个数n（约束不够）
这里A是不是方阵已经无所谓了，也没有什么法则可以用，就只分成一种情况。
由齐次线性方程组解空间维数 = n - r(A) >0，所以该齐次线性方程组有非零解，而且不唯一（*度为 n - r(A))。

1.1.2 非齐次线性方程组

AX=b

在非齐次方程组中，A到底有没有解析解，可以由增广矩阵来判断：
r(A)<r(A | b) 方程组无解；
r(A)=r(A | b) =n，方程组有唯一解；
r(A)=r(A | b) <n，方程组无穷解；
r(A)>r(A | b) 不可能，因为增广矩阵的秩大于等于系数矩阵的秩（在矩阵中加入一列，其秩只可能增大，不可能变小）。

1.2 SVD

1.2.1 在matlab的用法：

1. [V D] =eig(A’*A);D为A’*A的特征值对角矩阵，V为对应的特征向量。找到最小特征值对应的V中的特征向量即为最小二乘解。
2. 使用SVD分解矩阵A，[U S V] = svd(A); U 由 A*A’的特征向量组成，V 由 A’*A的特征向量组成，因此，奇异值矩阵S中最小的奇异值对应的V中的奇异向量即为最小二乘解。

1.2.2 MATLAB中a./b与a/b的区别以及左除和右除

a/b相当于a乘b的逆
a./b是a的每个元素与b的每个元素对应相除
A\B : 表示inv(A)B 解Ax=B
B/A:表示Binv(A) 解xA=B

• 应用举例：对于超定方程（非齐次线性方程的一种）的最小二乘解的情况。A*X =b。在matlab中使用一个左除命令（matlab：A\b）就可以得到最小二乘意义下的解。这个解没有模制的限制，就是实际的解。

1.3线性最小二乘法——齐次/非齐次

1.4 非齐次线性最小二乘：采用Vertical distance，竖直距离

直线拟合。这里(ATA)-1被称为A的伪逆。因为根据可逆性质，可逆矩阵一定为方阵，而这里A并不是为方阵。所以称为A的伪逆。

非齐次线性方程组不同情况下的解：欠定、适定、超定。

当 A的秩等于r 小于n，因此 在之前的例子 n是2 ，2列 ，因此 如果秩小于2 ，那么我们只有一个点 ，因此 ，该问题的答案是 取A得逆 ， 然后 将所有可能的线性解加上A的零空间 因此此问题有许多的答案

当A的秩等于n时 在之前的线性拟合的例子中 A的秩为2 （这）说明了A的许多不同行 不同点 但是 他们确实拟合于同一直线 而确切的答案是 仅仅是A的逆乘以b

当A的秩大于n，通过伪逆来求解 在MATLAB中这非常简单 就是A\b 而其为我们计算了伪逆

1.4.1 超定方程组非齐次线性最小二乘解

https://www.cnblogs.com/monoSLAM/p/5252917.html

举例：${a_1}{x_1}+{a_2}{x_2}+{a_3}{x_3}=b$a1​x1​+a2​x2​+a3​x3​=b，其中$({a_1},{a_2},{a_3},b)$(a1​,a2​,a3​,b)为测量已知量，$({x_1},{x_2},{x_3})$(x1​,x2​,x3​)为待求量。
那么只需要三组$({a_1},{a_2},{a_3},b)$(a1​,a2​,a3​,b)就可以求出$({x_1},{x_2},{x_3})$(x1​,x2​,x3​)。实际情况是某次实验不止测了三组数据——超定方程组，需要采用最小二乘。

a，如何转化为最小二乘形式：
例子：y = ax+b，已知（x,y）求（a,b）？
标准化：

带入测量数据：

例1：$y=ax+b{x^2}$y=ax+bx2，已知$(x,{x^2},y)$(x,x2,y)，求$（a,b）$（a,b）？
转化为标准形式：

带入测量数据：

例2：

转化为标准形式：

带入测量数据：

总结：对于线性表达式，通过适当的变型即可。

在例1中，通过选取x和x^2为基实现了线性化。
对于非线性表达式，可以通过合适的基、变型，有时候也可以转化为标准形式，如例1、例2。

b， 标准形式下最小二乘的求解：
对于（1）式，最小二乘的求解，相当于求解正规方程：
${A^T}AX={A^T}B$ATAX=ATB

标准形式下最小二乘解为：
$X={\left({{A^T}A}\right)^{-1}}{A^T}B$X=(ATA)−1ATB

图源：https://blog.csdn.net/u013802188/article/details/40181601

理论上，有正规方程组可以得到线性最小二乘问题的精确解，但是由于正规方程组会出现条件数平方效应（叉积矩阵的条件数是原矩阵条件数的平方），所以往往得不到所期待的效果。https://blog.csdn.net/LCCFlccf/article/details/84875534

用QR分解求非齐次线性最小二乘法的最优闭式解

参考：https://blog.csdn.net/LCCFlccf/article/details/84875534
参考：https://blog.csdn.net/qq_29721419/article/details/69676770

QR分解法是目前求一般矩阵全部特征值的最有效并广泛应用的方法，一般矩阵先经过正交相似变化成为Hessenberg矩阵，然后再应用QR方法求特征值和特征向量。它是将矩阵分解成一个正规正交矩阵Q与上三角形矩阵R，所以称为QR分解法，与此正规正交矩阵的通用符号Q有关。可以巧妙的绕过了条件数被平方的操作

1.5齐次线性最小二乘，采用：Perpendicular distance 垂直距离

a、齐次线性最小二乘的标准形式：

AX = 0

其中A为测量数据构成的矩阵与向量，X为待求参数向量。

这里主要针对方程数多于未知元素的情形–超定方程组。

b、齐次方程组的最小二乘解的约束

因平凡解 X = 0不是我们感兴趣的解，因此我们主要是寻求该方程组的非零解。

注意，如果 X 是这个方程组的解，那么对于任何标量k，使得kX也是解，因此可以建立一个合理的约束：||X||=1的解：

齐次最小二乘相当于求解：
$min||AX|| 且 ||X||=1$min∣∣AX∣∣且∣∣X∣∣=1
或者求解:
$min\frac{||AX||^2}{||X||}$min∣∣X∣∣∣∣AX∣∣2​

c、齐次方程组的最小二乘解——SVD分解得到“解”
通过前面a、b两部分的说明，此时问题的标准形式为：求使||AX||最小化并满足||X|| = 1时的X。其结论为：
$A^TA$ATA最小特征值对应的特征向量即为待求解

SVD分解——齐次线性最小二乘

对A矩阵SVD分解:
$A=UDV^T$A=UDVT
那么问题变成：
$min||UDV^TX|| 且 ||X||=1$min∣∣UDVTX∣∣且∣∣X∣∣=1

由于：
$min||UDV^TX|| = min||DV^TX||$min∣∣UDVTX∣∣=min∣∣DVTX∣∣
即U矩阵不影响范数。

同时
$||X||=||V^TX||$∣∣X∣∣=∣∣VTX∣∣
和U矩阵一样，V矩阵不影响范数。

则有：
$min||DV^TX|| 且 ||V^TX||=1$min∣∣DVTX∣∣且∣∣VTX∣∣=1

令 ||y|| = 1，
$min||Dy|| 且 ||y||=1$min∣∣Dy∣∣且∣∣y∣∣=1

由SVD分解的规则可知，D是对角元素按降序排列的一个对角矩阵，因此该问题的解是：
$y=(0,0,0...0,1)^T$y=(0,0,0...0,1)T
它具有一个非零元素1并在最后的位置上。

$X=||V^Ty|| 就是V的最后一列。$X=∣∣VTy∣∣就是V的最后一列。

齐次下的直线拟合。注意最后方程组的解是V的最后一列。但SVD分解直接中得到的是VT，因此对应也就是VT的最后一行。

只有通过矩阵A计算奇异值U D V的转置 行向量之间相互正交

取VT的最后一行 或者V的最后一列
那便是我们用来最小化ax等于0的向量

齐次线性方程组不同情况下的解：欠定、适定、超定。

1.5.2 带约束方程组的最小二乘解

$min||AX|| 且 ||X||=1 且||CX=0||(公式一)$min∣∣AX∣∣且∣∣X∣∣=1且∣∣CX=0∣∣(公式一)

求解算法总结：

a、通过对C进行SVD分解，求出 $C=UDV^T$C=UDVT 。（如果C的行数少于列数，则在C矩阵的后面添加若干行0从而扩展成方阵）
b、如果对角矩阵D有r个非零对角元素，此时C的秩为 r 且C的行空间由$V^T$VT的前 r 行生成。
c、C的行空间的正交补${C^\bot}$C⊥由余下的行生成，记${C^\bot}$C⊥为V的消去前 r 列得到的矩阵
d、则 $C{C^\bot}=0$CC⊥=0，对比$CX=0$CX=0，可以得到：
X的解由${C^\bot}$C⊥的列生成，把所有满足这一条件的 X 记为：$X={C^\bot}{X'}$X=C⊥X′。

由于${C^\bot}$C⊥的列具有正交性，因此：$||X||=||{C^\bot}{X'}||=||{X'}||$∣∣X∣∣=∣∣C⊥X′∣∣=∣∣X′∣∣

此时，公式一 变成：

$\min||A{C^\bot}{X'}|| 且|{X'}||=1$min∣∣AC⊥X′∣∣且∣X′∣∣=1

1.6 非线性最小二乘

非线性的最小二乘可以通过牛顿高斯迭代、LM算法、梯度下降求解。
参考：https://blog.csdn.net/tina_ttl/article/details/56833251
参考：https://www.jianshu.com/p/bf6ec56e26bd

2.0 Epipolar Geometry

使用方法：

有了对极几何的模型，2D-2D的相机姿态可以通过如下过程求解：

①通过多组对应点（Correspondence）进行帧间匹配，求出本质矩阵E。

②通过对E进行分解求出外参数R和t，即相机姿态。
参考：https://www.cnblogs.com/clarenceliang/p/6704970.html

2.1 对极几何原理

对极几何成立的条件就是两张或多张影像观测到同一场景(物体)。

其中c0、c1为两个相机中心，p为空间中一点，p在c0、c1对应像平面上的投影分别为x0、x1。c0、c1连线与像平面的交点e0、e1称为极点（Epipoles），l0、l1称为极线（Epipolar Lines），c0、c1、p三点组成的平面称为极平面（Epipolar Plane）。

给定Bob的视点，存在一条共轭线穿过Mike的视点。

要想计算对极几何，需要空间中至少8对3D对应点对。注意是三维点坐标而不是像素平面内的二维坐标。

在上图中，以Bob的第一人称坐标系(相机坐标系)，x轴向右，y轴向下，z轴指向前方。这样对Bob而言，就有一个非常简单的相机投影矩阵P1。对于Mike而言，他的相机投影矩阵就是旋转R、平移t还有内参矩阵K。

如上图所示，Bob用手指向了建筑物的角点X1(在Bob的坐标系下度量)，Mike用手指向Bob，在他们之间形成了一个向量t，这个t是在Mike的坐标系下衡量的。

与此同时，Mike也可以指向Bob指向的点，这个点在Mike的坐标系下为X2。可以看到X1和X2是同一个点，只是在不同视角下的坐标。

因此，在上图中就有三条线：第一条是Bob和Mike之间的三维平移向量t(在Mike的坐标系下度量)；第二条是X2，由Mike指向建筑物的角点(在Mike坐标系下度量)；第三条是由Bob指向同一个角点，它在Mike的坐标系下定义为RX1或者X2-t。这样三条线可以组成一个平面，这个平面的法向量也很显而易见，t和X2作叉乘，即可得到该平面的法向量。当然，以“矩阵”的角度看向量时，把t转成对应的反对称矩阵与X2相乘即可。这样的话，X2-t这个向量肯定垂直于该平面的法向量。把它与平面法向量相乘结果为0，这样就可以得到一个等式(左上角所示)。对其进行整理化简，就可以写成第三行的形式。对于中间这部分，记为本质矩阵E。

可以看到，E是由t和R做叉乘得到的，所以这个简单的3×3矩阵包含了两个相机之间的相对旋转与平移。而且从上式也可以看出来它也相对好求，只需要一些对应点对即可。再温馨提示***意X1是Bob坐标系下的3维点，X2是Mike坐标系下的3维点。假如获得了多对对应点，就可以能求出E，既然E是由t和R叉乘得到的，所以得到E了以后就可以用一些数学方法分解得到R和t。

刚刚介绍了，Bob和Mike之间的三个向量形成了一个平面，这个平面与Mike的像平面相交，得到的交线就是极线(Epipolar Line)。而当他们同时指向另一个角点的时候，会发现这个平面以及它与Mike像平面的交线也跟着变化了。不同的点对应着不同的平面和极线，平面的方向随着我们指向的3D点而不断变化。值得注意的是在Mike像平面中的所有极线都会交于一点，这一点便成为极点(Epipole)。之所以出现这样的情况也是很容易理解的：因为不管这些平面如何变化，构成这个平面的向量之一t是不变的，t与Mike像平面的交点(如果像面足够大的话)也就是极点。

如上图所示，在Bob像平面中的x1可以写作是Bob相机坐标系中的X1的λ1倍。理解这句话需要用到以前学过的齐次坐标的知识，在齐次坐标中，所有的点都是用向量表示的。同理在Mike像平面中的x2可以写作是Mike相机坐标系中的X2的λ2倍，而且向量x2与该平面的法向量垂直。

同时我们可以合并EX1，E和X1的乘积是一个3维向量，这个向量可以看作是齐次坐标系下的一条直线。首先温习一下齐次坐标系下的直线表示：对于齐次坐标系下的两个点A和B，经过A、B的直线就等于从相机光心指向A形成的向量Va、指向B形成的向量Vb的叉积。换句话说就是直线AB就是Va、Vb构成平面的法向量。有了这个知识以后再来看EX1，把E写开就是：t×R·X1。先看R·X1它其实就是表示将Bob相机坐标系下的坐标旋转到了Mike的相机坐标系下，而且还在由t、X1、X2构成的平面内，这样的话t再与它做叉乘，得到的就是这个平面的法向量。而X2本身就是在这个平面里面的，所以X2再和这个法向量相乘结果为0。λ2X2也自然与EX1叉乘为0，所以说Mike像平面中的这一点x2经过EX1这条线。EX1就是经过X2点的在Mike像平面里的极线。

同理反向推导一下就可以得到X1在Bob像平面中的极线为$X2^TE$X2TE。


而对于Bob像平面中的极点和Mike像平面中的极点可分别按上图中的公式求解，形成一个方程组，用最小二乘做SVD分解即可求解得到e1或e2向量，也就是齐次表示的极点坐标。极点可以看作是两个相机光心之间的向量，因此两个相机一定都会在这条线上(只能知道在这条线上或者说方向上，但不知道具体在哪里)。