SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group

David M. Rosen; Luca Carlone; Afonso S. Bandeira; John J. Leonard

Source-linked AI summary

SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group

David M. Rosen, Luca Carlone, Afonso S. Bandeira, John J. Leonard

arXiv:1612.07386v2Dec 21, 2016cs.RO

TL;DR

The paper addresses the computational difficulty of nonconvex maximum-likelihood estimation for special Euclidean synchronization. It develops SE-Sync from an exact semidefinite relaxation and a structure-exploiting Riemannian solver, recovering certifiably globally optimal solutions in relevant noise regimes and outperforming Gauss-Newton on SLAM benchmarks.

Problem
Special Euclidean synchronization requires estimating poses from noisy relative measurements, but its maximum-likelihood formulation is generally nonconvex and computationally hard.
Method
SE-Sync solves a semidefinite relaxation using low-rank, geometric, and graph-theoretic structure, then applies rounding and a posteriori certification.
Results
SE-Sync recovers certifiably globally optimal solutions under non-adversarial noise and is 3.3–15.7 times faster than Gauss-Newton across SLAM benchmark datasets.
Takeaways & Limitations
The semidefinite relaxation can provide exact globally optimal synchronization solutions below a critical noise threshold while remaining practical for large-scale instances.
Takeaways & Limitations
Available concentration inequalities yield probability-of-exactness estimates that are significantly suboptimal and grossly conservative relative to empirical observations.

Abstract

from arXiv · show

Many important geometric estimation problems take the form of synchronization over the special Euclidean group: estimate the values of a set of poses given a set of relative measurements between them. This problem is typically formulated as a nonconvex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation whose minimizer provides an exact MLE so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem on a low-dimensional Riemannian manifold, and design a truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is able to recover certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so more than an order of magnitude faster than the Gauss-Newton-based approach that forms the basis of current state-of-the-art techniques.

1 Introduction

Special Euclidean synchronization estimates unknown poses from noisy relative measurements, but its maximum-likelihood formulation is generally nonconvex and computationally difficult. The paper turns a previously theoretical semidefinite-relaxation approach into SE-Sync, a practical algorithm for certifiably globally optimal large-scale solutions in a non-adversarial noise regime.

Motivation: Special Euclidean synchronization underlies pose-graph SLAM, camera motion estimation, sensor network localization, artifact reconstruction, and molecular structure determination.These applications estimate unknown group elements from noisy pairwise relative transforms.
Motivation: Maximum-likelihood formulations provide analytical rigor and performance guarantees, but their underlying optimization problems are often nonconvex and computationally hard.Prior methods therefore largely sought efficient approximate estimates rather than guaranteed global optima.
Related work: Prior convex relaxations can capture the original problem’s global structure, but their minimizers are generally infeasible for the original estimation problem.Rounding is commonly used to reproject such solutions into the feasible set.
Related work: Earlier work established that tight convex relaxations can certify candidate optimality and, in principle, recover certifiably globally optimal solutions through convex programming.The present paper addresses whether this approach can become practically effective at large scale.
Related work: General-purpose semidefinite programming methods do not scale effectively beyond decision variables of a few thousand dimensions, while real-world synchronization relaxations are typically one to two orders of magnitude larger.This scaling barrier motivated a specialized solver.
Contributions: The paper develops improved synchronization and semidefinite-relaxation formulations and proves a non-adversarial noise regime where relaxation minimizers are exact globally optimal solutions.This is stated as Proposition 2.
Contributions: A structure-exploiting optimization scheme combined with rounding produces SE-Sync, which recovers certifiably globally optimal solutions and is more than an order of magnitude faster than Gauss-Newton on evaluated datasets.The evaluation uses simulated and real-world pose-graph SLAM datasets and noise up to an order of magnitude above typical robotics and computer-vision levels.

2 Problem formulation

The paper formulates synchronization on SE(d) as estimation of unknown group elements from noisy relative-transform measurements represented on a connected measurement graph. It introduces the notation, graph structures, matrix operators, probability models, and maximum-likelihood formulation used thereafter.

2.1 Notation and mathematical preliminaries: The paper uses N and R for nonnegative integers and real numbers, [n] for {1, . . . , n}, and |S| for set cardinality.These conventions support indexing and set-size notation throughout the formulation.
2.1 Notation and mathematical preliminaries: O(d), SO(d), and SE(d) denote the orthogonal, special orthogonal, and special Euclidean groups, with SO(d) represented by rotation matrices and SE(d) by R^d ⋊ SO(d).The paper also uses the Stiefel manifold of orthonormal k-frames as a smooth compact matrix manifold.
2.1 Notation and mathematical preliminaries: The notation includes symmetric, positive semidefinite, Kronecker-product, pseudoinverse, vectorization, block-diagonal, and block-structured matrix operators.These operators provide the linear-algebraic language for the optimization formulations.
2.1 Notation and mathematical preliminaries: Graphs encode vertices, edges, directed orientations, incidence matrices, weights, and Laplacians; the Laplacian is related to an oriented incidence matrix through the edge-weight matrix.The presentation excludes loops and parallel edges, although the results can be generalized to parallel edges.
2.1 Notation and mathematical preliminaries: The probability notation distinguishes latent values from noisy observations and estimates, and uses Gaussian and isotropic Langevin distributions for translational and rotational quantities.These conventions identify the roles of true, observed, and estimated parameters.
2.2 The special Euclidean synchronization problem: SE(d) synchronization estimates n unknown group elements from m noisy pairwise relative transforms, with measurements represented by edges of a connected undirected graph.If the graph is disconnected, the estimation problem decomposes into independent problems on its connected components.
2.2 The special Euclidean synchronization problem: A directed orientation assigns measurement directions, and noisy observations are sampled from the stated generative model with reverse measurements defined by inversion.The maximum-likelihood estimate is obtained by minimizing the corresponding objective, equivalently expressible as a nonlinear least-squares problem.

3 Forming the semidefinite relaxation

The section reformulates special Euclidean synchronization into graph-structured rotation and translation problems, then constructs a semidefinite relaxation whose exactness can recover globally optimal maximum-likelihood estimates under bounded noise.

3 Forming the semidefinite relaxation: The maximum-likelihood problem estimates SE(d) states from noisy relative transforms, with gauge symmetry because relative measurements do not determine absolute state values.The solution set is organized into orbits under the diagonal SE(d) action.
3.1 Simplifying the maximum-likelihood estimation: The reduced objective is expressed using weighted translational and rotational graphs, their Laplacians, a connection Laplacian, and graph-structured projection and incidence matrices.These constituent matrices have interpretations tied to the directed measurement graph and translational data.
3.1 Simplifying the maximum-likelihood estimation: Translation can be eliminated in closed form for fixed rotations, reducing maximum-likelihood estimation to a rotation-only problem with a recoverable optimal translation.The reduced formulation uses a translational data matrix and graph-derived operators.
3.2 Relaxing the maximum-likelihood estimation: The orthogonal relaxation replaces the constraints R ∈ SO(d)^n with R ∈ O(d)^n, enabling a convex relaxation while temporarily allowing both components of O(d).The formulation is developed through an extrinsic Lagrangian-duality construction with block-diagonal symmetric multipliers.
3.2 Relaxing the maximum-likelihood estimation: The primal and dual formulations are semidefinite programs obtained by aggregating the matrix multipliers into a block-diagonal matrix Λ.The section names these formulations as Problems 6 and 7.
3.2 Relaxing the maximum-likelihood estimation: If a minimizer Z* of the dual semidefinite relaxation factors as Z* = R*T R* and R* lies in SO(d)^n, then it yields optimal solutions of the orthogonal relaxation and the original maximum-likelihood problem.The optimal translation is recovered using equation (21).
3.2 Relaxing the maximum-likelihood estimation: Proposition 2 guarantees exact recovery when the measurement noise is sufficiently small in spectral-norm deviation of the data matrix from its exact latent value.Solving the semidefinite relaxation can then recover a global minimizer of the original problem through the translation-recovery formula.
3.2 Relaxing the maximum-likelihood estimation: The paper states the exactness threshold only as an existence result because available concentration inequalities produce probability estimates that are grossly conservative empirically.Sharper concentration inequalities and explicit probability bounds are left for future research, despite observed exactness at noise levels up to an order of magnitude above typical applications.

4 The SE-Sync algorithm

SE-Sync makes the semidefinite relaxation practical by exploiting low-rank, geometric, and graph-theoretic structure, then combines Riemannian optimization with rounding and a posteriori certification. A rank-deficient second-order critical point yields a globally optimal relaxation solution, enabling recovery and verification of an optimal synchronization estimate.

Algorithmic strategy: The algorithm solves the convex semidefinite relaxation and uses rounding to recover an optimal estimate when exactness holds, or a feasible approximation otherwise.This strategy targets the hard maximum-likelihood problem through the relaxation while retaining a fallback feasible solution.
Low-rank structure: Factoring the decision variable as Z = Y^T Y reduces the search space and removes the need to enforce positive semidefiniteness directly.The rank-restricted formulation is valid when the relaxation admits a solution with rank at most r.
Geometric structure: The block-diagonal constraints transform the rank-restricted problem into optimization over a product of Stiefel manifolds.Each block Y_i lies on St(d, r), giving the formulation its Riemannian geometry.
Graph-theoretic structure: Sparse graph-derived matrix decompositions avoid manipulating the dense data matrix directly and support a fast Riemannian optimization method.The decomposition uses sparse matrices and their inverses associated with the measurement graph.
Riemannian Staircase: A rank-deficient second-order critical point of the Riemannian problem is a global minimizer and produces a solution of the semidefinite relaxation.The Riemannian Staircase searches successive relaxation levels until such a point is found.
Certification: SE-Sync combines the efficient optimization and rounding procedures, and verifies optimality a posteriori when the recovered estimate attains the relaxation’s lower bound.This equality provides a computational certificate for the estimate’s correctness as a maximum-likelihood solution.

5 Experimental results

Experiments on simulated cube problems and heterogeneous SLAM benchmarks evaluate SE-Sync under varying noise, measurement density, and problem size. SE-Sync recovers globally optimal solutions and consistently outperforms Gauss-Newton in computational speed, including on real-world-style benchmark datasets.

Cube experiments: The experiments vary measurement noise, measurement density, and problem size using simulated cube pose-graph SLAM datasets.The cube scenario models a robot traveling through a regular cubical lattice with sequential odometry and loop closures.
Cube experiments: Exactness depends primarily on rotational measurement noise, with exactness observed up to about 15 degrees RMS angular error.This threshold is reported for the cube experiments and concerns the rotational observations.
Cube experiments: The observed exactness threshold is roughly an order of magnitude greater than typical sensor noise in robotics and computer vision applications.The authors interpret this as empirical evidence for certifiably globally optimal recovery under reasonable operating conditions.
Cube experiments: SE-Sync computes and certifies globally optimal solutions faster than Gauss-Newton often requires to obtain an estimate, with the speed gap increasing superlinearly with problem size.Both SE-Sync-Chol and SE-Sync-QR are reported as many-fold faster when using chordal initialization.
Algorithmic explanation: SE-Sync’s speed advantage is attributed partly to its exact Hessian and truncated-Newton trust-region method, which produce higher-quality updates without explicitly forming or factoring the Hessian.Gauss-Newton uses an approximation whose quality degrades with large residuals or strong nonlinearities, while truncated Newton solves approximate Newton equations as accurately as needed.
SLAM benchmark datasets: On larger SLAM benchmarks, both methods reached the same globally optimal solution, while SE-Sync was 3.3 to 15.7 times faster than Gauss-Newton.The factors correspond to garage, the smallest dataset, and rim, the largest dataset, respectively.

6 Conclusion

SE-Sync combines an exact semidefinite relaxation with structure-exploiting Riemannian optimization to certify globally optimal synchronization solutions. Experiments show recovery under substantially higher noise than typical applications and more than an order-of-magnitude speedup over Gauss–Newton.

SE-Sync’s semidefinite relaxation is exact below a critical measurement-noise threshold, enabling globally optimal solutions and a posteriori certification.The method uses a specialized Riemannian optimization procedure to solve large-scale instances efficiently.
SE-Sync recovers globally optimal solutions with noise up to an order of magnitude greater than typically encountered in robotics and computer vision.
SE-Sync runs more than an order of magnitude faster than the Gauss–Newton-based approach underlying current state-of-the-art techniques.
The authors suggest extending SE-Sync toward provably robust and statistically efficient estimation when some measurements are contaminated by outliers.This possibility is presented as a future extension rather than an established result.
Structured semidefinite programming may support practically effective certifiably correct algorithms for robust machine perception on embedded systems.The conclusion motivates broader investigation of this possibility.

A The isotropic Langevin distribution

The appendix characterizes isotropic Langevin noise on SO(d) and its two- and three-dimensional interpretation through von Mises-distributed rotation angles. In these dimensions, samples are generated by perturbing a mode rotation about a uniformly distributed axis.

The isotropic Langevin distribution on SO(d) is defined by a density with mode M and concentration parameter κ.The relative rotation M^TX determines the rotation from M to a realization X.
The Langevin density depends on the magnitudes of elementary rotation angles but not the orientations of their mutually orthogonal subspaces, yielding isotropy.
As λ →∞, the von Mises density asymptotically approaches the Gaussian N(0, λ−1).
The von Mises distribution becomes increasingly concentrated at its mode as λ increases and is uniform when λ = 0.
For d = 2, 3, Langevin samples use an angle θ drawn from vM(0, 2κ), with a uniformly distributed rotation axis in three dimensions.In two dimensions the perturbation is R(θ); in three dimensions it is exp(θ[v̂]×).
The angular-standard-deviation approximation is accurate within 1% for κ > 12.87 and within .1% for κ > 125.3.These thresholds correspond to angular standard deviations of 11.41 degrees and 3.62 degrees, respectively.

B Reformulating the estimation problem

This appendix reformulates the estimation problem in vectorized, block-matrix form and establishes an equivalent formulation involving graph-structured coefficient matrices. It then eliminates translations analytically, reducing the optimization to one over rotations with a corresponding optimal translation.

Vectorization rewrites the estimation objective using concatenated translations t, rotations R, and a block-structured coefficient matrix B.The blocks B1, B2, and B3 are indexed by directed edges and vertices.
The block products satisfy B^TB = M ⊗ I_d, establishing equivalence between the original and vectorized estimation problems.
For fixed rotations R, the translations can be optimized analytically, yielding an equivalent rotation-only problem and an associated minimizing translation t*.
Because the weighted graph Laplacian is positive semidefinite, its nullspace for a connected graph consists of constant translations across vertices.

B.3 Simplifying the translational data matrix ˜Qτ

The translational data matrix is simplified using weighted incidence matrices, orthogonal projections, and a reduced incidence matrix. The derivation also connects the resulting semidefinite formulation to its dual through strong duality.

The matrix Π is the orthogonal projection onto the kernel of the weighted incidence matrix AΩ^1/2.This projection yields the simplified form of the translational data matrix.
Although Π is generally dense, it admits a computationally convenient decomposition using sparse matrices and their inverses.
The reduced incidence matrix is full-rank, allowing the relevant minimum-norm problem to be solved through normal equations and a thin LQ decomposition.
The semidefinite relaxation’s dual constraints require the block diagonal of Z to consist of identity matrices.Strict feasibility of both primal and dual formulations implies nonempty optimal sets and strong duality.

C Proof of Proposition 2

The proof connects noisy minimizers of Problem 5 to exact recovery in the semidefinite relaxation by constructing a certificate matrix and controlling its spectrum under bounded noise.

Proof roadmap: The proof derives first-order conditions for a minimizer R∗ of Problem 5 using a symmetric block-diagonal multiplier matrix Λ∗.These conditions are expressed as (˜Q −Λ∗)R∗T = 0, with Λ∗ computed from ˜Q and R∗.
Proof roadmap: The matrix C ≜ ˜Q −Λ∗ certifies the relaxation solution: C ⪰0 implies optimality, while rank(C) = dn −d implies uniqueness.The certificate follows from Lagrangian duality between Problems 5 and 7.
Proof roadmap: In the noiseless case, the latent rotations yield a certificate whose d zero eigenvalues and remaining positive eigenvalues establish exactness of Problem 7.The positive eigenvalues are lower-bounded by the algebraic connectivity λ2(L(W ρ)).
Proof roadmap: Noise perturbs the data matrix and minimizer continuously, while the first-order condition keeps at least d certificate eigenvalues fixed at zero.Bounding estimation error as a function of ∆Q therefore controls the remaining eigenvalues of C.

C.1 Gauge symmetry and invariant metrics for Problems 4 and 5

Because Problems 4 and 5 possess global gauge symmetries, the appendix measures estimation error between gauge orbits rather than arbitrary representatives.

Gauge symmetry: Gauge symmetry maps any minimizer to an equivalent minimizer through diagonal left-actions of SO(d) or O(d).This creates multiple, generally infinitely many, equivalent solutions for dimensions d ≥2.
Invariant metrics: The orbit distances dS and dO minimize Frobenius distance over global SO(d) and O(d) gauge transformations, respectively.They compare the closest representatives of the corresponding solution orbits.
Invariant metrics: These distances are invariant under independent gauge transformations applied to either feasible point.Thus they provide symmetry-aware measures of dissimilarity for Problems 4 and 5.
Computing the metrics: The orbit distances can be computed using singular-value decompositions and orthogonal Procrustes solutions.For SO(d), the corresponding special orthogonal Procrustes problem supplies the minimizing transformation.
Invariant metrics: Riemannian quotient-space geometry justifies these metrics because the gauge actions are isometries that are free and proper.The quotient spaces identify gauge-equivalent representatives into single geometric points.

C.2 A sufficient condition for exact recovery in Problem 5

The appendix gives a sufficient certificate-based condition for recovering a minimizer of Problem 5 through the semidefinite relaxation Problem 7.

Certificate construction: The proof constructs C from a Problem 5 minimizer and its Lagrange multipliers, using positive semidefiniteness as the optimality certificate.The construction exploits Lagrangian duality between Problems 5, 6, and 7.
Certificate construction: First-order optimality on O(d)n yields (˜Q −Λ∗)R∗T = 0, with Λ∗ a symmetric block-diagonal multiplier matrix.The condition follows by projecting the ambient Euclidean gradient onto the tangent space of O(d)n.
Exact recovery condition: The certificate matrix provides a posteriori verification by reducing exactness to checking positive semidefiniteness of C.This criterion is simpler to verify than solving the original nonconvex problem globally.
Exact recovery condition: If C ⪰0, then Z∗ = R∗TR∗ minimizes Problem 7; if rank(C) = dn −d, it is the unique minimizer.The rank condition is established using semidefinite-program nondegeneracy.
Uniqueness: The proof establishes dual nondegeneracy by showing that the null-space basis can be chosen as U = 1/√n R∗T.This supports uniqueness of the relaxation solution under the rank condition.

C.3 The noiseless case

The semidefinite relaxation is exact for noiseless measurements, and the proof explains why this exactness persists under sufficiently small perturbations.

Noiseless exactness: In the noiseless case, the latent rotations provide an optimal solution of Problem 5 and induce the candidate certificate for Problem 7.The proof uses the true rotational and translational data matrices together with connection-Laplacian structure.
Noiseless exactness: The rotational connection Laplacian is similar to L(W ρ) ⊗ Id, so its spectrum contains d copies of the weight-graph spectrum.Its nonzero eigenvalues are lower-bounded by λ2(L(W ρ)) > 0.
Noiseless exactness: The translational data matrix is compatible with endpoint potential differences, placing its columns in the image of the directed incidence transpose.This supports the projection and certificate calculations used in the noiseless proof.
Noiseless exactness: The noiseless certificate has d zero eigenvalues and dn −d strictly positive eigenvalues, establishing exactness and uniqueness of Problem 7.Theorem 10 states that the latent rotation Gram matrix is the unique relaxation solution.
Perturbed measurements: Under noise, continuity of C and bounds on gauge-invariant estimation error allow certificate eigenvalues to remain nonnegative for sufficiently small perturbations.This extends the noiseless exactness argument to a non-adversarial noise regime.

C.4 An upper bound for the estimation error in Problem 5

This section derives an upper bound on the orbit-based rotational estimation error for a minimizer of Problem 5 by relating perturbations in the data matrix to the estimate.

Error decomposition: The proof decomposes the estimation error into components aligned with and orthogonal to image(¯R^T).Lemma 11 characterizes the relevant matrix subspace and its orthogonal projection structure.
Projection operators: The projection ProjV maps vectors onto image(R^T), while ProjM applies this projection row-wise to matrices.The construction uses RRT = nI_d for R ∈ O(d)^n and the Frobenius inner product for matrices.
Auxiliary optimization: Optimality conditions reduce the auxiliary optimization to equal singular values σ1 = ··· = σd = σ.The constraint is solved for the common singular value, yielding the auxiliary objective value used in the error bound.
Conclusion: Combining the perturbation inequalities and the auxiliary optimization produces the final upper bound on the estimation error.The final step combines inequalities (134), (140), (151), and (152).
Theorem 12: The section bounds dO(¯R, R∗) for an estimate obtained by minimizing Problem 5.The bound is stated in Theorem 12 for the true rotations ¯R and an estimated minimizer R∗.

C.5 Finishing the proof

The proof concludes that sufficiently small data perturbations yield a positive semidefinite certificate with the required rank, making the rounded estimate uniquely optimal and preserving membership in SO(d)^n.

Proof setup: The proof assumes R∗ is orbit-aligned and defines data and rotation perturbations ∆Q and ∆R.These perturbations are used to decompose the certificate matrix C.
Perturbation control: Continuity implies that sufficiently small ∥∆Q∥2 keeps the certificate perturbation below λd+1(¯Q).The argument uses Theorem 12 to obtain ∆R → 0 as ∆Q → 0.
Certificate spectrum: Under this condition, C has at least dn − d strictly positive eigenvalues and at least d zero eigenvalues.The zero eigenspace contains image(R∗T), while the remaining eigenvalues are positive.
Optimality certification: C ⪰ 0 and rank(C) = dn − d, so Theorem 7 guarantees that Z∗ = R∗TR∗ is the unique minimizer of Problem 7.The certificate therefore establishes uniqueness of the lifted solution.
Special orthogonal group: The +1 and −1 components of O(d) are separated enough that R∗ ∈ SO(d)^n, making it optimal for Problem 4 as well.Proposition 2 follows by selecting β = min{β1, β2} > 0.