SE-Sync

Rosen 2019 · Paper

One-line summary — First certifiably correct algorithm for pose graph optimization: an SDP relaxation solved via Riemannian optimization that recovers the globally optimal solution with a proof of optimality (arXiv 2016, IJRR 2019).

Problem

$SE(d)$ synchronization — estimate $n$ unknown poses $x_1,\dots,x_n \in SE(d)$ from noisy measurements of $m$ of their pairwise relative transforms $x_{ij} = x_i^{-1}x_j$ — is the standard SLAM backend problem (pose-graph SLAM, camera pose estimation). Under the paper’s generative model (Gaussian translation noise with precision $\tau_{ij}$, isotropic Langevin rotation noise with concentration $\kappa_{ij}$), the maximum-likelihood estimate minimizes

$$p^{*}_{\mathrm{MLE}} = \min_{t_i \in \mathbb{R}^d,\; R_i \in SO(d)} \sum_{(i,j)\in\vec{\mathcal{E}}} \kappa_{ij}\big\lVert R_j - R_i\tilde{R}_{ij}\big\rVert_F^2 + \tau_{ij}\big\lVert t_j - t_i - R_i\tilde{t}_{ij}\big\rVert_2^2 .$$

This is a high-dimensional non-convex nonlinear program, computationally hard in general: local solvers (g2o, GTSAM, Ceres) can silently converge to local minima far from the true solution, with no way to know whether a returned answer is globally optimal — unacceptable for safety-critical autonomy.

Method & architecture

• Eliminate translations. For fixed rotations the problem is an unconstrained quadratic in $t$, solved in closed form via a generalized Schur complement. This reduces the MLE to pure rotation synchronization, $p^{*}_{\mathrm{MLE}} = \min_{R \in SO(d)^n} \operatorname{tr}(\tilde{Q} R^{\mathsf{T}} R)$, where the data matrix $\tilde{Q} = L(\tilde{G}^{\rho}) + \tilde{T}^{\mathsf{T}} \Omega^{1/2} \Pi\, \Omega^{1/2} \tilde{T}$ combines the rotation connection Laplacian $L(\tilde{G}^{\rho})$ with a translational data term; $\Pi$ (an orthogonal projection) admits a sparse decomposition via a thin LQ factorization of the weighted incidence matrix, so products with $\tilde{Q}$ never form a dense matrix. Optimal translations are recovered afterwards as $t^{*} = -\operatorname{vec}\big(R^{*}\tilde{V}^{\mathsf{T}} L(W^{\tau})^{\dagger}\big)$.
• SDP relaxation, provably tight. Relaxing $SO(d)$ to $O(d)$ makes the problem a QCQP whose Lagrangian dual is the semidefinite program

$$p^{*}_{\mathrm{SDP}} = \min_{Z \succeq 0}\; \operatorname{tr}(\tilde{Q} Z) \quad \text{s.t.} \quad \mathrm{BlockDiag}_{d\times d}(Z) = \mathrm{Diag}(I_d,\dots,I_d),$$

so $p^{*}_{\mathrm{SDP}} \le p^{*}_{\mathrm{MLE}}$. Proposition 1: there exists $\beta > 0$ such that if $\lVert \tilde{Q} - \bar{Q} \rVert_2 < \beta$ (with $\bar{Q}$ the data matrix of the true latent transforms — i.e. noise below a critical threshold), the SDP has a unique solution $Z^{*} = R^{*\mathsf{T}}R^{*}$ with $R^{*} \in SO(d)^n$ the exact MLE. Whenever the rounded estimate attains the SDP lower bound, that equality is a computational certificate of global optimality.

• Riemannian staircase. Instead of interior-point SDP solvers (intractable beyond a few thousand variables), SE-Sync uses the Burer–Monteiro factorization $Z = Y^{\mathsf{T}}Y$ with $Y \in \mathbb{R}^{r\times dn}$, $r \ll dn$; the block constraints then say each $Y_i$ is an orthonormal frame, giving an unconstrained problem on a product of Stiefel manifolds:

$$p^{*}_{\mathrm{SDPLR}} = \min_{Y \in \mathrm{St}(d,r)^n} \operatorname{tr}(\tilde{Q}\, Y^{\mathsf{T}} Y).$$

Proposition 2 (after Boumal et al.): any rank-deficient second-order critical point of this problem is a global minimizer and yields the SDP solution — so one climbs the rank hierarchy (“Riemannian staircase”) until a rank-deficient critical point appears.

• Fast second-order local search. On the manifold, $\nabla F(Y) = 2Y\tilde{Q}$ and Hessian-vector products are projections of ambient derivatives ($\operatorname{grad} F(Y) = \operatorname{Proj}_Y \nabla F(Y)$), all computed with sparse matrix products and triangular solves; a truncated-Newton Riemannian trust-region (RTR) method finds high-precision critical points.
• Rounding. A rank-$d$ thin SVD of $Y^{*}$ gives $\hat{R} = \Xi_d V_d^{\mathsf{T}}$; flip orientation if most blocks have negative determinant, then project each block to the nearest rotation matrix — exact when the relaxation is tight, a feasible approximation otherwise.

Results

(MATLAB implementation on Manopt, staircase fixed at $r=5$, initialized from a random point on $\mathrm{St}(3,5)^n$; baselines: Gauss–Newton with odometric init, GN with chordal init, and GN-chordal plus a posteriori verification.)

• Simulated cube worlds ($s^3$ lattice, loop-closure probability $p_{LC}$, noise $\sigma_T$, $\sigma_R$; 30 runs per setting): SE-Sync converges to a certifiably globally optimal solution from random initialization in time comparable to — in these tests often faster than — GN with state-of-the-art chordal initialization, and much faster than GN + separate verification. The exception is the high-rotational-noise regime, where the relaxation’s exactness breaks down.
• Large-scale real/standard 3D SLAM datasets — sphere (2500 nodes/4949 edges), sphere-a (2200/8647), torus (5000/9048), cube (8000/22236), garage (1661/6275), cubicle (5750/16869): SE-Sync attains the certified global optimum on all of them (e.g. objective $1.249\times 10^{6}$ on sphere-a vs $3.041\times 10^{6}$ for odometry-initialized GN), in 3.6–203 s, confirming the relaxation stays exact on challenging real-world instances.
• Per the abstract, global optimality is recovered under noise “up to an order of magnitude greater than that typically encountered in robotics applications,” at a cost scaling comparably with direct Newton-type local search.

Why it matters for SLAM

SE-Sync answered a foundational question: despite PGO’s non-convexity, the instances arising in practical SLAM are globally solvable, and you can know when you have the global optimum. This launched the certifiable-perception research program (TEASER++ for registration, QUASAR for rotation search) and gave SLAM backends a verification tool — e.g., checking whether a local solver’s answer is actually optimal after potentially corrupted loop closures.

Related

• Pose graph optimization — the problem being certified
• MAP inference as sparse nonlinear least squares — the MLE formulation being relaxed
• TEASER++ — certifiable point cloud registration
• QUASAR — certifiable rotation search
• GNC — robust estimation companion for outlier-contaminated graphs