Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration
Connor Holmes, Abhishek Goudar, Timothy D. Barfoot
cs.RO
2026-09-03
CP-Cert从候选解走进中心路径再取对偶证书，专门处理加了冗余约束后对偶不唯一的紧SDP。数据关联认证比Mosek快两到三个数量级，立体位姿证书约1到2毫秒。
机器人里大量非凸问题可以写成 QCQP，再用 Shor 松弛变成凸 SDP。松弛紧时，局部解一旦对上 SDP 最优值，就能发全局最优证书。最快的路是：局部求解器出候选，再解对偶乘子、检查证书矩阵半正定。
麻烦在紧松弛常常靠冗余约束撑起来，候选处对偶不唯一，线性方程欠定。这时社区只能把 SDP 整段交给内点法。Mosek 一类求解器过几百维就难实时。数据关联、矩阵加权位姿配准都落在这个退化区间。
CP-Cert 的观察：中心路径上每一点的对偶是唯一的，μ→0 时对偶收敛到 SDP 的 KKT 乘子。手里已经有一个秩一候选，不必从解析中心冷启动。
算法把候选 X̂=xxᵀ 加 δI 推进 PSD 锥内部，用代价约束形式的中心路径（用 ε 代替障碍参数 μ，ε 只依赖原变量即可初始化），再沿中心路径走回候选。这是一趟原变量的往返，目的是把对偶乘子带出来。不必走到精确极限：互补性低于 τc、证书矩阵加 τp I 能 Cholesky，就可以提前停。候选不是全局最优或松弛不是秩紧时，原迭代会偏离 x̂，用 Frobenius 角超过阈值判失败。
线性瓶颈是 Schur 补系统。求解用预条件共轭梯度，预条件子根据候选构造，并利用稀疏和并行，避免内点法反复分解大矩阵。Loraine 也用 PCG 解低秩 SDP，但不利用已有候选来初始化和做预条件。
数据关联这边给了一套新的 SDP 松弛，借鉴 Lovász-theta，在机器人点云上经验秩紧，可用 CP-Cert 认证。再接到立体相机流水线：SuperPoint + LightGlue 出匹配，RAFT-Stereo 出视差，逆立体模型出带各向异性协方差的三维点，CLIPPER 出团，CP-Cert 认证关联和矩阵加权配准。
Stanford Bunny 仿真 900 次试验，842 次松弛秩紧。CP-Cert 的混淆表（占秩紧试验百分比）：
| 局部方法 | TP（认证且全局） | FN（全局却未认证） |
| CLIPPER | 83.02% | 0.24% |
| Mosek 全局解 | 99.29% | 0.71% |
| PMC | 50.83% | 0.00% |
| RANSAC | 22.45% | 0.00% |
没有把局部最小错误认证成全局（FP 全 0）。α≥0.6 时秩紧比例 100%，α 取 0.5–2 时 CLIPPER 的内点最适合配准。
运行时间上，关联数增加时 CP-Cert 和 Mosek 都近似立方，常数差两到三个数量级；离群比例升到很高、约束近 2 万时，成功认证仍约 100 ms。小规模位姿 SDP（n=13, m=21）成功时 0.9–1.1 ms，Mosek 4.2–7.3 ms，大约五倍。
真实立体流水线，帧间隔 0.05–1.0 s，关联认证成功率 93.6%–94.1%，位姿证书 100%。平均平移误差 0.0025–0.0210 m，旋转 0.040–0.293°。关联成功认证 351–981 ms，失败则到 2–4.6 s；位姿证书稳定在 1.2–1.5 ms。
冗余约束把松弛变紧，也把「局部求解再认证」这条快路堵死。CP-Cert 专治这个退化，让 CLIPPER 一类图方法可以在近实时给出「这是全局最优团」的证明，而不是再解一遍 SDP。立体相对位姿可以接到证书后的内点上。这是认证器，不是更准的前端。
前提是秩紧，Bunny 上仍有 58/900 次不秩紧。超参一堆（扰动 δ、ε 策略、角度阈值），换问题要调。失败路径比成功路径慢，因为早停逻辑不对称。关联 SDP 随匹配数立方涨，1 秒已经是流水线里最贵的一步。立体实验声明没为误差最小化调参，数字不能当 SOTA 配准精度读。和通用低秩 SDP 求解器比，它必须先有一个候选。