Epipolar a personal journal

最小二乘问题(十一)

我们来看非线性最小二乘问题的线性化子问题:

假如我们不能保证 $J_r$ 列满秩,我们套用上一篇末尾的正则化方法,将这一子问题改写为:

这时,我们在每一步迭代时便会在“尽可能最小化当前线性化函数”和“尽可能保持步伐稳健”之间进行折衷。那么这会影响到我们最终收敛到局部极值么?注意看,如果我们已经在局部极值附近,此时 $\|\Delta x\|^2\to 0$,也就是说第二项自然就消失了。换句话说,在局部极值点附近,我们的问题与 Gauss-Newton 中的线性化子问题是相同的。

再来看看这个常数 $\lambda$ ,当 $\lambda \to 0$ 时,我们得到了 Gauss-Newton,此时我们通过二阶近似来逼近目标函数。当 $\lambda \to \infty$ 时,根据标准方程

这意味着,此时我们的优化步采用的是梯度下降步。

也就是说,通过调节 $\lambda$ ,我们的优化算法在 Gauss-Newton 步和梯度下降步之间平衡。此外,采用了这种方法后,在每次子问题求解后,更新变量时无需再采用步长控制,可以直接使用 $x\gets x + \Delta x$ 。 这是因为 $\lambda$ 自带了步长控制的效果。

这个方法被称为 Levenberg-Marquardt 算法,是一种广泛使用的非线性最小二乘问题的数值优化算法。

那么,吹了一篇 LM 算法,究竟什么时候要 GN 步,什么时候要梯度下降步呢?Jacobian 不满秩时 GN 有多糟糕呢? 为啥 LM 就好了呢? 我们下一篇介绍。

小软件:Hourglass

Hourglass - The simple countdown timer for Windows

Hourglass is the most advanced simple countdown timer for Windows. Just enter a time in just about any format, and hit Enter.

一个漂亮并且精简的倒计时小工具~

之后也会陆续记录各种遇到的实用小软件,免得每次想用时候记不得叫啥~

最小二乘问题(十)

在我们这一系列文章的最一开始,我们对标准形式的 $\min \|Ax-b\|^2$ 有着如下的要求:

这其中对 $A$ 的满秩要求是非常重要的,因为我们优化这一问题的方式是求解标准方程,得到:

结合前面的条件,我们知道方程有解当且仅当 $A^TA$ 可逆。而如果 $\mathrm{rank}(A)<n$ ,$\mathrm{rank}(A^TA)\leq\mathrm{rank}(A)<n$ 一定不可逆。

在秩亏的情形下,我们的解 $x$ 有无穷多,这是因为对于任意的 $z\in\mathrm{ker}(A^TA)$ ,$A^TA(x+z)=A^TAx$ 。此时,我们的问题是欠约束的。

为了解决秩亏问题,我们可以引入 $A$ 的伪逆 $A^\dagger$ 。将问题的解写作:

利用 SVD 分解,若矩阵 $A=U\Sigma V^T$,则 $A^\dagger = V\Sigma^\dagger U^T$ ,这里 $\Sigma^\dagger = \mathrm{diag}(\mathrm{inv}(\sigma_1), \mathrm{inv}(\sigma_2), \dots, \mathrm{inv}(\sigma_n))$. 相比一般的矩阵求逆,由于秩亏矩阵存在为 0 的奇异值,我们特别引入了专用的倒数函数:

我们回到原始的最小化问题,$Ax-b$ 几何上对应于求 $b$ 在 $A$ 的列空间上的投影,利用上面的 SVD 分解结果,我们知道 $U^T b$ 中对应非零奇异值的行便对应了这个投影,剩余的部分是垂直于 $A$ 列空间的余项($Ax$ 永远无法表达的部分)。完整的 $A^\dagger b$ 恰好给出了不包含余项的部分,同时它在 $A$ 的右零空间投影也是零,所以它是对 $Ax-b=0$ 的最好逼近,同时也保证了 $\|x\|$ 最小。

有关上面内容的详细证明,可以参考其它资料,或者尝试自行推导。从结论上讲,$x=A^\dagger b$ 求解了下面的问题:

这种处理方法虽然可以解决任意的线性最小二乘,但它的缺点也是明显的:SVD 分解通常需要很大的运算量。通过观察问题的解,我们“希望”最小化原始问题的同时最小化 $x$ 的模长,这就诱使我们转而采用下面的带正则化最小二乘:

它的标准方程为 $(\lambda I+A^TA)x = A^Tb$ ,当 $\lambda>0$ 时,$x$ 左侧的系数矩阵一定可逆。为了能够更好近似原始最小问题的结果,我们需要 $\lambda$ 尽可能小。否则我们就会在两项之间进行一个折衷,最终的结果并不能真正最小化 $\|Ax-b\|^2$ 。

但在非线性最小二乘中,我们会看到这一正则化会带来一种新的最小化算法。它可以保证我们收敛到局部最优,同时它比标准的 Gauss-Newton 具有更好的稳定性。

简单粗暴的旋转小量

在 SLAM 问题中通常含有姿态变量,上一篇文章中我们举了一个旋转作为变量的例子。在文章里我们还引入了一些晦涩的东西,比如流形、切空间、Lie 群……

不过我们有一种简单粗暴的方法来理解旋转和旋转群。要想说明这一切,我们还是先回到数学中引入群的动机。

群的发明是为了能够研究各种各样的对称现象。以镜面(镜像变换)为例,我们将一个右撇子放在镜子前,镜子里出现的就是一个左撇子,反过来类似。不过我们关心的并不是左撇子还是右撇子,我们关心镜像变换这个现象本身。我们还知道镜像的镜像就等于什么都没有变——不管你最初拿来的是苹果还是梨都一样。

那么,如果将 { 不变, 镜像 } 作为一个集合,并且把一个操作(不妨叫乘法)用来表示这个集合里的元素按照先后顺序进行变换操作,我们就知道

不变 x 不变 = 不变

不变 x 镜像 = 镜像

镜像 x 不变 = 镜像

镜像 x 镜像 = 不变

进一步地,我们还发现对于集合里任意选取的三个元素 A B C ,它们之间的操作总是满足

(A x B) x C = A x (B x C)

这样,对于集合里的元素,我们就发现了四个有趣的现象:

  1. 有一个单位元素 E (不变),它与任何元素 X 先后进行变换都得到那个元素 X 。
  2. 对于任何元素 X ,有一个元素 inv(X) ,它与 X 先后进行变换总得到 E ,并且 inv(E) = E 。
  3. 对于任意两个元素 X 和 Y,它们先后进行变换后总得到这个集合里的一个已知的变换。
  4. 对于任意三个元素 X Y Z ,它们按照某个顺序变换时,结合的顺序不影响结果。

这四个现象对于广泛的对称现象都是适用的,于是我们把满足这四个现象的集合以及对应的乘法放在一起,叫做一个群。

一个集合的全体置换操作便构成一个群,一般叫置换群。对于一个方程来讲,它的全部根可以相互置换而不影响方程的诸多性质,这个根的置换群就叫 Abel 群。计算机里使用的有限位数的二进制整数对加法封闭,而当加法产生溢出时则会关于一个上界求余后折回,这全体可表示的二进制整数关于加法构成了一个同余加法群……我们有各种各样的群。

不过上面我们举例子的这些群都有个特点:它们的元素都是离散的元素。离散元素的群使得很多如导数、积分等等的分析工具失效。而 Lie 群是一类特殊的群,这类群都是连续(光滑)的,因此我们可以用微积分工具进行研究。

旋转群就是一个 Lie 群,很容易可以验证旋转群的集合满足上面的四个条件。但同时我们可以看到一个与一个旋转可以任意接近地存在无数多其它的旋转。这便是旋转群连续的一个感性认识。旋转群的连续加上旋转这个操作本身的特点,使得这个群有了特殊的几何结构——我们可以把零旋转附近的连续结构通过旋转放置到这个群内任何一个元素的附近,从而得到对这个元素附近的连续结构的描述——而这就是 Lie 群的一个思想。当我们想要研究两个距离比较远的元素时,不妨考虑这两个元素之间的一条连续的路径,我们可以沿着这个路径,用一个个局部的操作来一点点从一个元素逼近到另一个元素——这是 Lie 群的连续性带给我们的好处,当然这个代价也是很大的,其中一个例子便是 Lie 群和它伴随的 Lie 代数上的 BCH 公式。

这里我们不去讨论这些技术细节,因为一旦展开,我们就要面临大量晦涩难懂的数学定义和公式。但我们仅从上面的这个“对称”的认识来理解旋转小量的叠加。

我们的思路很简单:1. 看看零旋转附近;2. 想办法把零旋转附近的结构放置到任意旋转处。

对于第一件事,在最小二乘问题(九)中我们提到了 $\lfloor dr \times \rfloor$ 的小增量。既然是增量,把它加上 $I$,我们就得到了零旋转附近的旋转增量表示 $(\lfloor dr \times \rfloor + I)$ 。对于第二件事,如果我们想把这个结构放到旋转 $R$ 的位置,最简单的方式就是把它用 $R$ 旋转一下!

因此我们就得到了在那篇文章中提到的小旋转的扰动模型 $R\oplus dr = (\lfloor dr \times \rfloor + I) R$。

当然有人会问为什么不把 $R$ 左乘?这是个 convention 的问题,当然不同的 convention 背后对应了不同(相似)的理论推导。

希望上面的这些介绍能够让你对这个结论有一个直观的感性认识,并且方便你在相关问题中直接记忆住结论。但如果你想深入探究它背后的规则,还是要认真进行一番推导的。这里推荐 Timothy Barfoot 的著作 State Estimation for Robotics 1

  1. State Estimation for Robotics - A Matrix Lie Group Approach, Barfoot, T. D., 2016 (online). 

最小二乘问题(九)

对于函数 $h(x) = 0$ ,如果有向量函数 $f: \mathbb{R}^s \to \{x\in\mathbb{R}^n | h(x)=0\}$ 使得 $h(f(p))=0$ ,并且 $f$ 为满射。那么流形 $h$ 上的最小二乘可以改写为:

这是我们喜闻乐见一般最小二乘的形式。但是这类向量函数并不总是有理想的性质,比如它们可能会在定义域内存在奇异点。

我们以旋转变换的 Rodrigues 参数化为例,一个在三维空间中绕着轴 $k$ ($\|k\|=1$)转动 $\theta$ 的旋转可以用向量 $v = k\theta$ 表示。

在这种参数化表示下,将一个点 $x$ 进行旋转得到 $R(x;v)$ 的变换为:

从表达式可以看出来,$v=0$ 是它的奇异点。在这一点处我们可以通过取极限的方法来延拓它的值和导数。通过 $\lim_{v\to 0}\frac{\partial R(x;v)}{\partial v}$ 来逼近它的导数,可以得到:

但在其它点处……呵呵我就不算了……

这里这个奇异点处的导数形式简单,我们来研究一下如何利用它。

全体三维旋转构成了三维标准正交群 $\mathbb{SO}(3)$ 。群所代表的是对称性质,标准正交群的对称性质非常好:它经过任意的三维旋转仍然得到自己。那么当我们有一个非零的旋转,我们可以先将它旋转到零,然后研究在零点加入旋转小量后的性质,然后再旋转回去(假装成旋转就是在原地发生)。这样,我们就可以使用上面那个零点处的导数。

我们把这个思路包装起来,每次加入的小旋转记作 $dv$,原始的旋转记作 $R$ ,把这个原始的旋转“归零”、“加入小旋转”、“复位”的操作假装成“在旋转上添加小旋转”,用 $R \oplus dv$ 表示。其实(经过了一系列理论推导)它就是:

有了这么一个工具,如果优化目标变量里出现了旋转,我们可以把子优化写成下面这样:

还是加一个小量,对小量做优化,只不过小量不再是传统的加法了。通过这种特殊的加法,我们保证了目标变量依旧属于拥有某个特殊的群。

数学上,我们把这类群叫做李群(Lie Group),而那个加号是从李群导出的李代数上对应的加法。标准正交群 $\mathbb{SO}(n)$,标准欧几里得群 $\mathbb{SE}(n)$ 都是李群,它们都有对应的李代数以及对应的加法。有了这些,当一个变量属于某个已知的李群结构,你可以方便地定义你的加号,然后直接套用到最小二乘中,从而保证解满足结构约束。当然,这套术语也可以拿去吹牛了。

嘛……不过从本质上,它就是我们上一篇介绍的流形上的最小二乘的一类特殊情形。