Home / 机器人经典基础 / SE-Sync：不仅求一张地图，还证明目标值已经不能更低

090｜SE-Sync：不仅求一张地图，还证明目标值已经不能更低

论文：David M. Rosen、Luca Carlone、Afonso S. Bandeira、John J. Leonard，SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group，2016 年首次公开。扩展稿 v2 · 官方代码。

先接住前作的问题

g2o等后端高效求局部非线性最小二乘，但通常不证明当前代价已全局最优；SE-Sync 在特定相对位姿噪声模型上增加凸松弛与证书。

五个前置概念

五个前置概念：

群同步：从带噪相对变换恢复整体一致的状态集合。
凸松弛：扩大或简化可行域，得到较易求解的界。
半正定矩阵：二次型非负的对称矩阵，是 SDP 的约束核心。
Stiefel 流形：列正交矩阵构成的几何空间。
次优性界：候选目标与可靠下界之差，限制可能剩余的改善。

一、问题设定：位姿候选怎样用目标下界检验全局最优

位姿图 SLAM 把机器人在不同地点的相对运动拼起来。因为测量有噪声，一个回路上的相对变换往往不能完全闭合，优化器要找一组最一致的全局位姿。

问题定义与前人局限

“同步”在这里不是相机和 IMU 的时间同步，而是从相对关系恢复一组整体一致的群元素。每个状态 $x_i=(R_i,t_i)$ 属于 $SE(d)$ ，边上测量的是 $x_i^{-1}x_j$ 。

这是图优化后端问题，不负责图像匹配、激光点关联、回环检索或控制策略。图由前端提供；若图不连通，各分量需要分别估计，分量之间的关系无法从缺失测量中凭空恢复。

第 2.2 节用各向同性高斯模型描述平移噪声，用各向同性 Langevin 模型描述旋转噪声。它不是任意鲁棒核、任意完整协方差都直接适用的万能 SLAM 求解器。相对测量也不能决定全局原点和朝向，因此一组整体刚体变换等价的解具有相同目标值。

局部 Gauss–Newton 可以很快得到好解，却通常没有全局证书。通用半正定规划可以处理凸松弛，但对大图直接存储和分解巨大矩阵成本很高。本文要同时解决“有保证”和“能算得动”。

二、由半正定松弛走到低秩求解与证书

1. 原始目标

问题 1 的加权最小二乘形式为：

$\min_{R_i\in SO(d),t_i}\sum_{(i,j)}\kappa_{ij}\|R_j-R_i\tilde R_{ij}\|_F^2 +\tau_{ij}\|t_j-t_i-R_i\tilde t_{ij}\|^2.$

波浪号表示测量， $\kappa,\tau$ 为对应精度权重。旋转残差使用矩阵弦距离，而不是任意选定的李代数角度误差；证书只证明这里定义的目标。换一个损失后不能直接继承同一证书。

2. 先消去平移，再放松旋转约束

固定旋转时，平移最优解来自线性最小二乘。消去它后得到只含旋转的二次形式 $\operatorname{tr}(\tilde Q R^TR)$ 。矩阵 $\tilde Q$ 包含旋转观测以及平移对整体一致性的影响，并不是只做旋转平均再随便拼位置。

设 $Z=R^TR$ 。真实旋转产生的 $Z$ 半正定，且每个对角块为单位矩阵，还带低秩及正确旋转的限制。半正定松弛扩大可行域：

$p_{SDP}^*=\min_Z\operatorname{tr}(\tilde QZ),\qquad Z\succeq0,\quad Z_{ii}=I_d.$

可行域更大，最小值只能更小，因此 $p_{SDP}^*\le p_{MLE}^*$ 。如果松弛解恰好可恢复为合法旋转，就达到原问题同一最优值。这是第 3 节定理 1 的关键逻辑。

3. 证书表达什么

对可行估计 $\hat x$ ，若其代价为 $f(\hat x)$ ，则：

$0\le f(\hat x)-p_{MLE}^*\le f(\hat x)-p_{SDP}^*.$

右边是次优性上界。等于零时证明全局最优；大于零时，只知道尚未证明足够好，不能直接断言候选解一定次优，因为松弛本身可能不紧。

浮点实现要报告可行性、数值容差和证书误差。梯度很小只能说明局部驻点；一个未经充分求解的松弛候选目标值，也不能随意当作已验证下界。

怎样实际构造一个下界？令 $\Lambda$ 为由对称 $d\times d$ 块组成的块对角矩阵，记 $C=\tilde Q-\Lambda$ 。只要 $C\succeq0$ ，任何满足 $Z\succeq0,Z_{ii}=I_d$ 的可行解都有

$\operatorname{tr}(\tilde QZ)=\operatorname{tr}(\Lambda)+\operatorname{tr}(CZ)\ge\operatorname{tr}(\Lambda).$

最后一步成立是因为两个半正定矩阵乘积的迹非负。若候选还满足 $CZ=0$ ，上下界相等，便有最优性证书。这把“找到一个小代价”变成可检查的矩阵条件；梯度小只涉及驻点，不能替代半正定检查。

原创两旋转例。 取两个二维旋转，目标为 $\|R_1-R_2\|_F^2$ ，对应 $\tilde Q=\begin{bmatrix}I_2&-I_2\\-I_2&I_2\end{bmatrix}$ 。候选 $R_1=R_2=I_2$ 给出 $Z=\begin{bmatrix}I_2&I_2\\I_2&I_2\end{bmatrix}$ 。选 $\Lambda=0$ ， $C$ 的特征值为 $0,0,2,2$ ，且 $CZ=0$ ，因此目标值 0 被认证。

相反， $R_1=I_2,R_2=-I_2$ 也是合法二维旋转，并且角度差 $\pi$ 处梯度为零，代价却为 8。对应驻点乘子 $\Lambda=2I_4$ 使 $C$ 出现两个 $-2$ 特征值，无法给出半正定证书。这个例子直接区分驻点与全局最优，不是论文 Cube 数据。下界与互补条件见原文问题6–7及附录C定理7；实际浮点检查还需控制最小特征值误差和可行性误差。

4. 低秩分解与 Riemannian Staircase

为避免直接操作巨大 $Z$ ，令 $Z=Y^TY$ ，使每个块 $Y_i$ 满足 $Y_i^TY_i=I_d$ ，在 Stiefel 流形上优化。低秩表达重新引入非凸性，所以不能只说“已经变凸，因此随便优化都行”。

论文利用一个充分条件：行秩不足的二阶临界点可给出松弛全局解。阶梯方法逐渐增加秩，在相应流形上求解并检查条件；通过结构化 Hessian–向量乘法与稀疏图运算降低成本。达到松弛最优后，若不能直接恢复原问题旋转，则用 SVD 截断与投影给出可行近似，并保留次优性界。

5. 小噪声定理的限度

命题 2 给出依赖真实数据矩阵的正阈值：当扰动谱范数足够小时，松弛具有所需恢复性质。作者采用的是阈值存在性结果，不是通用的“每条边旋转误差低于某角度就保证成功”。实验中的约十五度范围是特定生成模型观察，不能当作该定理的普适常数。

可行候选给出上界，松弛给出下界，只有间隙闭合才形成证书。下面手算这项比较，再把认证与真实地图误差分开。

三、恢复可行位姿，检查上界和下界是否闭合

6. 教学伪代码

输入：连通相对位姿图、与论文模型一致的权重
建立结构化数据矩阵的运算，不必显式存储全部稠密矩阵
消去平移变量；选定初始低秩因子
重复：
    在块 Stiefel 流形上用信赖域法优化
    检查二阶条件及松弛最优性
    若尚未满足，增加秩并沿改进方向继续求解
从已求解松弛获得下界
通过 SVD 与旋转投影恢复可行旋转，再求对应最优平移
比较可行目标与已验证下界
输出：位姿、次优性上界，以及是否达到数值认证条件

这是核心流程而非完备数值代码。收益指标包括目标值、证书间隙和耗时；定位真值误差是另一项，不能被证书间隙替代。

一个自构证书例子

教学构造，未运行。 某张图的候选可行代价为 12.0，经过验证的松弛下界为 11.7，则最多还有 0.3 的目标改进空间；若下界也是 12.0，就可认证最优。如果一个假回环使“真实地图”的代价变成 20，而错误折叠地图代价为 12，证书仍可能认证后者——因为它证明的只是给定目标。

四、分开读证书成功、代价与计算时间

Table 1：先比较两方法的目标值，再看运行时间和次优性上界 — 原论文结果图／表摘引：David M. Rosen、Luca Carlone、Afonso S. Bandeira、John J. Leonard（2016），Table 1，PDF 第 24 页；核对原文。原版权保留。

读图：先比较两方法的目标值，再看运行时间和次优性上界。这里相同最优目标支持速度与证书优势，证书的小数值不是轨迹的米制定位误差。

实验如何验证

证书针对指定目标、松弛与数值容差；通过认证不等于真实几何没有噪声或错误回环，原问题与松弛问题需分开。

项目	原文设置
实现	MATLAB，使用 Manopt 的截断 Newton 信赖域；另实现 Gauss–Newton 对照
硬件	Xeon E3-1505M 2.80 GHz、16 GB RAM，Ubuntu 16.04
预算	最多 500 外层迭代；梯度阈值 $10^{-2}$ 、相对目标改进 $10^{-5}$ ；信赖域每层至多 500 Hessian–向量乘积
初始化	GN 用 chordal 初值；SE-Sync 同时比较随机与同一 chordal 初值；默认阶梯起始秩为 5
Cube	默认 1000 位姿，近邻回环概率 0.1，旋转 RMS 约 10°、平移 RMS 0.20 m；每参数设置 50 次随机实例
大图	sphere、torus、grid 为合成；garage、cubicle、rim 为真实来源图；比较 QR+chord 与 GN+chord
统计边界	Cube 报平均曲线；大图表 1 未给重复计时置信区间；不含图像、激光前端计算

四组证据与不能推出的结论

图 2(a)：旋转噪声与紧致性。 所测 Cube 范围中约十五度 RMS 以内可保持精确恢复松弛的性质；更大噪声时证书间隙可出现。作者也指出高噪声下 GN 可能仍得到很好的解，只是同一松弛无法认证。不能将“未认证”自动标成“算法错误”。

原论文图2：SE-Sync立方体实验中的目标值、计算时间与相对次优性上界十二面板 — David M. Rosen、Luca Carlone、Afonso S. Bandeira、John J. Leonard（2016），图 2，PDF 第 22 页；原文与图注。原版权保留。

读图：每行改变一种条件，每列分别报告目标值、计算时间与相对次优性上界；对数坐标和噪声范围必须同时保留。

图 2(b)–(d)：噪声、图密度与规模。 分别改变参数，有助于隔离影响；它们仍来自规则格点与指定观测生成方式，不覆盖任意恶意假回环或真实前端的相关误差。更多回环是否有益，前提之一是这些边代表可信测量。

表 1：这里两个方法目标值相同。 所有六个大图中，GN 与 SE-Sync 都到达同一个全局最优值；优势主要是速度与可验证性，并不是本方法的地图精度全都更高。garage 耗时 17.81→5.33 s，rim 为 575.42→36.66 s，分别约 3.34 倍和 15.70 倍；这是表内实现与硬件条件的比值。

图 3 与表 1 的证书。 rim 含 10,195 位姿、29,743 测量，报告次优性上界约 $5.639\times10^{-11}$ 。这说明目标在数值精度上被认证，不表示每个位置误差只有 $10^{-11}$ 米。图中的好看轨迹也不代替独立真值精度表。

原论文图3：六个SLAM基准数据集的全局最优解几何形状 — David M. Rosen、Luca Carlone、Afonso S. Bandeira、John J. Leonard（2016），图 3，PDF 第 23 页；原文与图注。原版权保留。

读图：六个子图对应不同图结构；几何外观本身并不构成最优性证明，证书仍来自论文的验证条件。

证据见原文第 5 节。摘要的数量级加速说法应结合具体表格；garage 只有约三倍，不是所有任务都超过十倍。

五、保留噪声模型、松弛紧致性和错误关联

新意是把可验证的凸松弛与可扩展的低秩几何求解结合起来，使大图上也能报告有意义的全局最优性信息。它不是通用非凸优化问题的万能解法。

作者把含外点的鲁棒扩展列为后续方向。我的分析是：即使某个错误测量图的最小值被严格求到，仍可能是一张错误地图；反之，真值附近的解也可能因噪声而不是最小二乘最优。因此复现需要分别检验“求解正确”“模型合适”“观测关联正确”。

对完整各向异性信息矩阵、相关噪声或鲁棒损失的推广，需要重新检查推导和证书。当前官方实现可能有额外接口或优化，不能直接将其能力、耗时倒写成本文原始实验。

六、追问：把所有位姿图信息权重同时乘正常数，最优位姿和证书间隙怎样变？

把所有位姿图信息权重同时乘正常数，最优位姿和证书间隙怎样变？

参考答案：在同一可行域内，目标整体乘 $a>0$ 不改变最小化位置；若下界也按相同数学问题缩放，上界、下界及绝对间隙都乘 $a$ 。因此跨实验比较绝对间隙前要固定目标归一化和数值容差。这个代数检查不说明任何特定噪声模型更真实，也不保证给定数值求解器会走完全相同的迭代。

七、比较另一类可认证鲁棒估计

平行路线：TEASER：错误匹配占多数时，怎样配准点云并检查答案。在含外点的点云配准中追求认证，目标与证书条件不同。

八、自测与参考答案

问题 1：为什么有非零证书间隙，不能断定候选解不是全局最优？

答案： 松弛最优值可能严格低于原问题最优值。即使候选已经达到原问题最优，仍会和松弛下界有距离。非零间隙表示尚未凭这个界完成认证。

问题 2：低秩分解重新变成非凸，意义何在？

答案： 它显著减少计算，同时利用特定几何结构和二阶、秩条件连接回凸松弛的全局解。关键不是“非凸就随便求”，而是阶梯搜索与最优性检查为这种高效表达提供依据。

问题 3：获得全局最优证书后，还应该做什么实验？

答案： 还要用独立真值验证几何误差，检查假回环、噪声模型和权重敏感性，并报告前端与后端总成本。证书解决求解器是否优化到位的问题，不能替代整个机器人系统的正确性评估。