FAST-Sync: A Fast Start for Group Synchronization on Any Matrix Lie Group

GTSAM Posts

Published in IEEE Robotics and Automation Letters, vol. 11, no. 9, pp. 10377–10384, September 2026. DOI: 10.1109/LRA.2026.3710327.

Authors: Shane Holmes, Yiran Luo, Firat Taxpulat, David M. Rosen, and Frank Dellaert

Blog post by: Firat Taxpulat and Frank Dellaert

Group synchronization sounds specialized, but the problem is familiar to many GTSAM users. Pose-graph SLAM estimates global robot poses from noisy relative poses. Rotation averaging recovers camera orientations from pairwise matches. Closely related problems appear in monocular SLAM with scale drift, $SL(d)$-based 3D reconstruction, invariant filtering on $SE_2(3)$, and moving reference frames modeled with the Galilean group.

In each case, we have unknown group elements $X_1,\ldots,X_N\in G$ and noisy measurements $\widetilde X_{ij}\approx X_i^{-1}X_j$. The aim is to recover a globally consistent set of states, up to a common gauge transformation.

FAST-Sync is a batch initializer for this problem over matrix Lie groups. It replaces the nonlinear problem with a structured linear approximation, solves that approximation efficiently, projects the answer back to the chosen group, and hands the result to a local optimizer such as Gauss-Newton or Levenberg-Marquardt.

That last step is essential. FAST-Sync is not a replacement for nonlinear optimization; it is a way to start nonlinear optimization in a much better place.

Why initialization is the hard part

The maximum-likelihood group synchronization problem is typically high-dimensional and non-convex. GTSAM’s local optimizers can solve large instances efficiently, but—as with local optimization generally—the result depends on the initial estimate. A poor start can require many iterations to repair, or it can place the optimizer in the wrong basin of attraction.

A common baseline is to select a spanning tree and concatenate relative measurements outward from a root. This is very cheap, but every edge contributes error. Along a long tree path, those errors accumulate.

Three MIT SE(2) pose-graph trajectories comparing a maximum-spanning-tree initialization, FAST-Sync initialization, and local optimization from FAST-Sync.
Figure 1. A maximum-spanning-tree (MST) initialization (top) can lie outside the global optimizer's basin of attraction. FAST-Sync uses all relative measurements to produce a linear initialization (middle), from which local optimization converges to the global optimum (bottom) on this MIT $SE(2)$ example. Reproduced from Figure 1 of our published paper.


Figure 1 above illustrates this for a medium-sized pose graph problem (a robot cruising around the MIT campus). The spanning-tree estimate is inexpensive but severely distorted. FAST-Sync’s estimate is already close enough that ordinary local refinement reaches the desired solution.

This matters even when a globally certifiable solver is available. A strong initial estimate can reduce the work needed to reach—and then certify—a high-quality solution.

From a manifold problem to a linear start

FAST-Sync generalizes the philosophy of chordal initialization (an earlier structure-from-motion method by Daniel Martinec and Tomáš Pajdla) beyond familiar rotation and rigid-pose groups. Its first move is to replace the original log-likelihood with a quadratic Frobenius-norm surrogate:

\[J_F(X)= \frac{1}{2}\sum_{(i,j)\in E} \kappa_{ij} \left\|X_j-X_i\widetilde X_{ij}\right\|_F^2,\]

where $\kappa_{ij}=\sigma_{ij}^{-2}$ is the inverse noise variance of measurement $(i,j)$ under the isotropic concentrated-Gaussian model we use in the paper. FAST-Sync then temporarily relaxes the constraints $X_i\in G$, solves for matrices in the surrounding ambient vector space, and projects them back to $G$.

The residual is linear in the unknown matrix entries. Following the notation in our paper and suppressing the scalar row weight, an edge $(i,j)$ defines the sparse block row

\[(H_{ij})_\ell= \begin{cases} -\widetilde X_{ij}^{T}, & \ell=i,\\ I_d, & \ell=j,\\ 0_{d\times d}, & \text{otherwise}, \end{cases} \qquad \overline H=H\otimes I_d.\]

The key to FAST-Sync initialization is that we can solve a linear system that is $d$ times smaller and reuse it $d$ times. Using a Kronecker product and its algebraic properties, we replace the $d^2M\times d^2N$ vectorized system with $H\in\mathbb{R}^{Md\times Nd}$. After appending a “gauge” row, FAST-Sync factors the reduced, gauge-augmented matrix $A\in\mathbb{R}^{(M+1)d\times Nd}$ and reuses its triangular factor in the column-wise recovery.

A shallow graph starting from a gauge

Both the sparse structure and the mysterious “gauge” mentioned above provide two more opportunities to improve over chordal initialization.

First, FAST-Sync uses a block-preserving Nested Dissection ordering to create a back-substitution graph for the linear system, as shown in Figure 2 below. Nested Dissection recursively separates the measurement graph using small vertex separators, yielding the shallow graph on the right of the figure (for a small SfM dataset). In addition, the $d\times d$ entries belonging to one state always move together, with the effect that the corresponding sparse back-substitution matrix is block-sparse, as shown on the left.

Sparse triangular block structure and elimination dependency graph produced by Nested Dissection for the Statue of Liberty dataset.
Figure 2. Nested Dissection produces the sparse triangular block structure at left and the corresponding back-substitution directed acyclic graph at right. The final root block is fixed to the group identity, and the remaining matrices are recovered in reverse order. Reproduced from Figure 3 of our published paper.


Second, we use the root of the directed graph as the gauge. For a connected synchronization graph, applying one common global transformation to every state leaves all relative measurements unchanged. A linear initializer therefore needs to fix one gauge state, usually to the identity. In the noiseless problem, the choice of root is algebraically arbitrary. In the noisy ambient-space relaxation, however, the ordering affects both sparse fill and how far intermediate matrices drift from the group before projection, affecting the quality of the final estimate.

The block-sparse matrix corresponding to the graph allows all relaxed group matrices to be recovered in reverse order, starting from the root/gauge:

\[\widehat X_N=I_d,\qquad \widehat X_j= -\left( \sum_{k\in\mathrm{nz}_j} \widehat X_kR_{jk}^{T} \right)R_{jj}^{-T}, \qquad X_j^0=\Pi_G(\widehat X_j).\]

Here, the $R_{jk}$ are blocks of the sparse triangular factor and $\mathrm{nz}_j$ contains the later nonzero blocks needed to recover state $j$. One property of Nested Dissection is that it creates directed graphs with many parallel branches, allowing this back-substitution to be done in parallel.

Nested Dissection thus helps twice: it creates shallow and parallel back-substitution graphs and—empirically—gives better-quality initial estimates after rounding the relaxed matrices back to the group. A full theory of that effect remains open.

FAST-Sync is now in GTSAM

FAST-Sync is now in GTSAM! The merged GTSAM PR #2634 adds FAST-Sync directly to the develop branch. In C++, fastSync<T>(graph) accepts a NonlinearFactorGraph and returns a Values object that can be passed directly to a nonlinear optimizer. The public FastSync<T> class also exposes the ambient solve and projection/alignment stages separately.

A follow-up PR #2639 replaces the initial implementation’s sequential QR elimination with Cholesky and allows selecting either an ordering type or providing a complete custom ordering.

The implementation supports Rot2, Rot3, Pose2, Pose3, Similarity2, Similarity3, and SL4, and the repository includes both a technical notebook, which explains the reduced solve and projection interface, and a runnable Python tutorial, which covers all seven supported groups and subsequent Levenberg-Marquardt refinement. A MATLAB example exercises the same seven type-specific functions.

Application: Shonan averaging

As an example, below we show the practical impact on Shonan Rotation Averaging, which estimates globally consistent absolute camera orientations from noisy pairwise relative rotations. This is a core problem in structure from motion. Shonan combines scalable local manifold optimization with a semidefinite relaxation that can certify global optimality. See the ECCV 2020 paper for details.

Dataset Init Optimize Total
Taj Mahal 673 → 223: 3.03× 281 → 275: 1.02× 954 → 498: 1.92×
Brandenburg Gate 595 → 260: 2.28× 293 → 299: 0.98× 888 → 560: 1.59×
Temple Nara Japan 805 → 222: 3.62× 481 → 374: 1.29× 1,287 → 597: 2.16×
St. Peter’s Square 1,458 → 188: 7.77× 1,181 → 341: 3.47× 2,639 → 529: 4.99×
Colosseum Exterior 655 → 193: 3.39× 365 → 540: 0.68× 1,020 → 733: 1.39×

The table above shows the effect of using FAST-Sync: each entry reports before/after: speedup, with mean timings in milliseconds over three runs after one warm-up. “Before” uses the previous chordal initialization with COLAMD; “after” uses FAST-Sync. The five benchmarks are drawn from YFCC100M and contain 564–1,773 camera rotations with 100,000 pairwise relative-rotation measurements each.

FAST-Sync initialization is 2.28–7.77× faster. By starting closer to the optimum, it can also reduce the subsequent nonlinear optimization time, most notably on St. Peter’s Square (3.47×). Although optimization is flat on two datasets, the initialization gains dominate: total runtime improves by 1.39–4.99× across all five datasets.

Works for any matrix Lie group!

In the paper we further evaluate FAST-Sync on six groups: $SO(3)$, $SE(3)$, $SU(2)$, $SL(4)$, $Gal(3)$, and $Sim(3)$. In our synthetic small-world experiments, maximum-spanning-tree initialization is cheaper at the first step, but accumulated error often leaves much more work for the nonlinear optimizer. FAST-Sync pays more up front and frequently wins on total time because refinement starts closer to the desired basin. For $SO(3)$, $SE(3)$, and $SU(2)$, we use SE-Sync to obtain the certifiably global reference solution. For $SL(4)$, $Gal(3)$, and $Sim(3)$, we estimate the global optimum using local optimization initialized from ground truth.

On the $SE(3)$ pose graph problems we tested, FAST-Sync is about 35–40% faster than the off-the-shelf chordal baseline while reaching nearly the same solution quality.

Runtime-versus-Frobenius-error curves comparing maximum-spanning-tree initialization and FAST-Sync on Intel, Rim, Pantheon, and drone datasets, plus a connectivity and noise plot.
Figure 3. On representative $SE(2)$, $SE(3)$, $SO(3)$, and $Gal(3)$ datasets, FAST-Sync starts with lower Frobenius error and generally reaches the reference solution sooner than the maximum-spanning-tree (MST) baseline, including on our noise-corrupted variants. Reproduced from Figure 10 of our published paper.


We also study four representative datasets: the Intel $SE(2)$ pose graph, the Rim $SE(3)$ dataset, Pantheon rotation averaging, and a $Gal(3)$ Drone graph derived from a real drone sequence. As shown in Figure 3 above, we see the same overall pattern when comparing with a (very cheap) maximum-spanning-tree initializer: FAST-Sync’s linear solve is not always the cheapest initialization, but initialization plus refinement is typically faster and more reliable than beginning with a poorer estimate.

Takeaway

FAST-Sync turns group synchronization into a strong starting estimate by combining five ideas: an ambient Frobenius surrogate, Kronecker reduction, block-preserving Nested Dissection, sparse back-substitution, and projection to the group. The result gives a local optimizer a stronger starting point that, in many of our experiments, reduces total initialization-plus-refinement runtime.

The new GTSAM implementation makes that initializer available directly from a factor graph, and Shonan averaging now integrates FAST-Sync’s estimate by default within a certifiable rotation-averaging pipeline.

One caveat: “Any matrix Lie group” describes the reusable linear-algebraic template. It does not mean that every group is automatically handled without additional work. A new group still needs a usable projection $\Pi_G$, and appropriate manifold operations and factors for refinement.

Further browsing:

Disclosure: AI was used to help draft this post and prepare the figures.