精读笔记
Problem Setting
这篇论文实际处理的是 factor-graph 形式机器人状态估计中的 certifiable global optimization 落地问题。已有 GTSAM/g2o 路线提供了很成熟的建模和局部求解，但本质上仍是非凸 least squares，初始化差时会掉进坏局部极小。另一方面，SDP relaxation 可以给全局最优或最优性证书，但 naive monolithic SDP 会把所有 lifted 变量堆进一个大 PSD 矩阵，计算上很快不可接受。
真正困难点不是写出某个 pose graph 的 SDP，而是如何在通用 factor graph 接口下自动产生一个既保留稀疏结构、又等价于原 monolithic relaxation 的 SDP。关键矛盾是：因子图建模的价值来自局部性和稀疏性，而标准 SDP lifting 容易把这种局部性抹平；如果不能把稀疏性传递到 convex relaxation，global optimality 的代价会远高于实际机器人系统可接受范围。
Motivation
已有路线各自卡在不同位置。局部优化器的问题不是速度，而是不提供全局保证；SE-Sync/Riemannian staircase 等方法能利用低秩结构，但通常针对特定同步/PGO 形式，且需要专门推导；已有 chordal sparse SDP 在机器人里多用于链式 localization 或 trajectory-like 问题，泛化到更复杂图结构时往往需要人工分解。
作者抓住的缺口是：机器人社区已经广泛使用 GTSAM 表达稀疏图结构，而 GTSAM 内部的变量消元和 Bayes tree 本身就是一种 chordal completion 机制。也就是说，构造 chordally decomposed SDP 所需的 clique/separator 信息其实已经存在于因子图求解器里，只是之前没有被用来生成 SDP relaxation。论文的动机很务实：把 certifiable estimation 从“专家手工推 SDP”推进到“从 factor graph 自动生成 sparse SDP”。
Core Idea
核心思想可以概括为：不要为每个估计问题手写 SDP，也不要求解一个全局大 PSD 矩阵；而是把 factor graph lift 成 QCQP 后，直接用 Bayes tree 的 clique 作为 SDP 的 PSD block。这样，SDP 的变量组织方式从“全局 dense moment matrix”变成“局部 clique moment matrices + separator consistency”。
这个改变的本质是把 convex relaxation 的计算图对齐到 factor graph 的 chordal structure。它引入的 inductive bias 不是统计意义上的先验，而是图结构先验：只在由消元产生的 maximal cliques 内维护完整二阶关系，在 clique 交集上维护一致性。相比 prior work 的区别在于，链式 chordal decomposition 是人工利用特殊拓扑；这里把 decomposition 委托给通用变量消元，因此原则上可处理 ring、tree、稀疏 SLAM 图等非纯链结构。它的 generality 来自图算法自动化，不来自 relaxation 理论的根本扩展。
Method
方法中真正必要的机制有三步。
第一，lifting 到 QCQP。原始状态可能在 SO(d)/SE(d) 上，误差和约束非线性；通过引入 homogenization constant 和 lifted monomials，把 cost、primary constraints、substitution constraints 都写成二次形式。它解决的是 SDP relaxation 的入口问题：只有把问题变成 QCQP，Shor-type SDP 才能统一生成。关键点是 lifting 尽量不改变原始 factor graph 的连接关系，否则后续稀疏性会被提前破坏。
第二，利用变量消元构造 chordal completion。原始稀疏图通常不是 chordal，直接做 PSD decomposition 需要 chordal sparsity pattern。GTSAM 的 elimination ordering，例如 COLAMD/METIS，会产生 Bayes net/Bayes tree；其 maximal cliques 正好对应 chordal completion 后的 clique。这个步骤解决的是“如何自动获得 SDP block 结构”的问题。
第三，构造 clique-based SDP。每个 Bayes tree clique 对应一个小 PSD matrix，局部 cost/constraints 被分配到对应 clique；不同 clique 在 shared variables 上施加 equality consistency。这样得到的 SDP 与 monolithic SDP 在 chordal decomposition 条件下等价，但求解代价主要取决于最大 clique size 而不是总变量数。
实现上集成 GTSAM 和 MOSEK、支持 Rot2/Rot3/Pose2/Pose3 与若干 Frobenius/Prior factor，这些是可用性的贡献，但从机制上看属于把已有数学路线产品化。
Key Insight / Why It Works
最关键的 insight 是：Bayes tree 不只是局部优化里的稀疏线性代数工具，也可以作为 SDP relaxation 的 chordal decomposition certificate。也就是说，factor graph elimination 产生的 clique/separator 结构，正好对应 Fukuda-style sparse SDP matrix completion 定理所需要的 maximal cliques 和 intersection constraints。
方法有效的主要原因不是 relaxation 更强，而是计算组织更正确。monolithic SDP 的瓶颈来自大 PSD cone；将其替换为多个小 PSD cone 后，interior-point 或 conic solver 的主成本与最大 block 规模强相关。对于 chain/ring 这类 treewidth 很低的图，clique size 基本不随节点数增长，因此 runtime 可近似线性。这是本文实验线性 scaling 的真正来源。
最可能的核心贡献是“把 GTSAM Bayes tree 自动转化为 chordally decomposed SDP”的软件/结构桥接。lifting、Shor relaxation、chordal SDP decomposition 都是已有工具；新意在于把这些拼成一个可从常规 factor graph 自动触发的 pipeline。相比之下，支持若干变量/因子类型、MOSEK Fusion API、模板元编程等主要是 engineering。
需要注意：global optimality 的 claim 依赖 relaxation tightness，而 chordal decomposition 本身只保证与 monolithic SDP relaxation 等价，并不保证 relaxation 对原非凸问题 tight。文中在实验问题上说 relaxation known tight 或观察到全局解，但没有系统分析 tightness 边界。因此本文更像是在解决 certifiable estimation 的 scalability/interface 问题，而不是解决 certifiability 本身的数学充分条件问题。
Relation To Prior Work
这篇最接近三条线：SE-Sync/Riemannian staircase 的 certifiable PGO；Dümbgen/Barfoot 系列的 chordal sparse global estimation；以及 GTSAM/Bayes tree 的 factor graph 稀疏推断。
与 SE-Sync 的本质差异在于利用的结构不同。SE-Sync 主要利用 SDP 解的低秩结构，通过 Burer-Monteiro/Riemannian staircase 避免显式大 SDP；本文则保留 convex SDP 形式，但利用 aggregate sparsity/chordal decomposition 把 PSD cone 拆小。前者偏低秩非凸求解加证书，后者偏稀疏凸优化。
与此前 chain-like chordal sparse 方法相比，本文的实质新增信息是自动化和拓扑泛化：不是手工针对链结构写分解，而是通过 Bayes tree 支持一般稀疏图的 chordal completion。这个创新在理论上不深，但在机器人软件生态里很关键。
与通用 sparse SDP 工具 COSMO/TSSOS 等相比，本文优势不是 solver 算法，而是建模入口：机器人用户可以从 GTSAM factor graph 出发，不需要显式写 polynomial SDP 或控制低层 decomposition。换句话说，它属于“把 convex certification 接入 factor-graph backend”的系统型演化。
Dataset / Evaluation
实验覆盖两个合成/受控问题：3D ring pose-graph SLAM 和 2D chain localization。它们确实能验证核心机制的一部分：当 graph treewidth 低、lifted factor 保持局部、relaxation tight 时，chordal SDP 可以接近局部优化器的 scaling，同时避免随机初始化导致的坏局部最优。
但 evaluation 的覆盖面偏窄。chain 和 ring 都是非常有利于 chordal decomposition 的稀疏结构，最大 clique 很小；这不足以支撑“arbitrary factor graphs 上 scalable”的强结论。文中没有真实数据集、没有大规模实际 SLAM benchmark、没有高回环密度图、没有多传感器高阶因子，也没有 outlier/robust cost 场景。
对比也不完整。monolithic SDP 作为 baseline 说明 decomposition 有效，但这是预期结果；local LM random/ground-truth 说明局部优化依赖初始化，也不新。真正需要比较的是 SE-Sync/Riemannian staircase、其他 chordal sparse conic solvers、不同 elimination ordering，以及 redundant constraints 对 tightness/稀疏性的影响。文中未充分说明这些。
Limitation
第一，scalability 上限由 treewidth 决定。论文强调问题规模 N 增大时近似线性，但这只在 chain/ring 等低 treewidth 图上成立。对于 dense loop closures、视觉因子连接大量变量、bundle adjustment 中 landmark-camera 复杂耦合，Bayes tree clique size 可能迅速变大，PSD block 维度也会爆炸。
第二，lifting 维度是隐含成本。Pose3 等变量 lift 后的 D 不小，PSD block 规模按 clique 中 lifted variables 总维度平方增长。即使节点图稀疏，单个 clique 内的 PSD cone 也可能很重。论文没有充分量化 lifted dimension 与 solver time 的关系。
第三，global optimality 依赖 relaxation tightness，不由 chordal decomposition 保证。chordal decomposition 只是让 monolithic SDP 更快；如果 Shor relaxation 不 tight，得到的是 relaxation optimum 而不是原问题 global optimum。文中对哪些因子、噪声水平、约束组合能保证 tight 没有系统边界。
第四，所谓自动适用于 common factor/variable types 目前支持范围有限。非 polynomial error、robust kernels、range-bearing、projection/camera factors、IMU preintegration、高阶因子等真实系统常见组件如何 lift，文中未充分说明。未来扩展可能不是简单工程，因为某些因子会引入额外变量或破坏 sparsity。
第五，增益主要来自 exploiting sparsity 和软件整合，不是新的优化理论。对于已经有专门结构化 solver 的问题，本文未证明它在速度或鲁棒性上优于已有最佳路线。
Takeaway
- 1. 最值得记住的是 Bayes tree 可以被复用为 sparse SDP 的 clique tree：同一套 factor-graph elimination 结构同时服务于局部稀疏线性代数和全局 convex relaxation。
- 2. 这篇推动的不是新的 certifiability 理论，而是 certifiable estimation 的可用性边界：从手工推导专用 SDP，走向从标准 GTSAM factor graph 自动生成 chordally decomposed SDP。
- 3. 对其他问题的迁移 insight 是：如果一个全局 relaxation 看起来不可扩展，先检查其 lifted aggregate sparsity 是否能与原始计算图对齐；不要默认必须构造 monolithic moment/PSD matrix。
- 4. 未来真正值得做的是 tightness-aware sparse relaxation：自动选择 lifting、redundant constraints、ordering，并在不破坏 sparsity 的前提下增强 relaxation；否则 pipeline 只能在低 treewidth 且 naturally tight 的问题上漂亮工作。
一句话总结
这篇论文把已有 QCQP/SDP certifiable estimation 和 GTSAM Bayes tree/chordal sparsity 接起来，是一次重要的结构化工程化推进：它让全局最优估计在低 treewidth factor graphs 上更可用，但核心收益来自稀疏分解而非新的 relaxation 理论。