Certifying Rotation Averaging on Sparse Graphs Without Laplacian Localization

Many robotics and vision systems estimate the orientations of hundreds of cameras or robot poses from noisy relative measurements. That problem is non-convex, but a convex relaxation called a semidefinite program (SDP) often recovers the exact global answer. An SDP is a convex problem over positive-semidefinite matrices, solvable in polynomial time. The best theory says when this works: the relaxation stays exact as long as the noise stays below a level set by the measurement graph's Fiedler value. The Fiedler value is the second-smallest eigenvalue of the graph Laplacian, and it measures how well-connected the graph is. Real measurement graphs, however, are sparse. They have dangling tree-like branches, long single-track corridors, and heavy hubs. On such graphs the Laplacian's low eigenvectors localize: their mass collapses onto a few peripheral nodes. The Fiedler value then falls toward zero, and the guarantee becomes vacuous even in cases where the relaxation may still be exact in practice.

This note proposes that the right connectivity quantity for these certificates is the one the community-detection literature already uses to escape the same pathology. That quantity is the spectrum seen by non-backtracking walks, which are random walks forbidden to immediately reverse an edge. Such walks ignore dangling trees and treat long chains as single weighted links. We aim to show three things. First, the noise level at which the relaxation stops being exact tracks the spectrum of the graph's kernel (trees removed, chains contracted), together with any genuine community bottlenecks, rather than the raw Fiedler value. Second, a duality bound stated on that kernel can be proven. Third, the bound is useful for deciding which extra measurements (loop closures) to collect.

Core Claim

Rotation Averaging and Strong Duality gives the relevant result. It solves multiple-rotation averaging through its Lagrangian dual SDP, proves a zero duality gap under noise bounds tied to $\lambda_2(L)$ (the Laplacian Fiedler value), reports a safe zone of about 42.9° for complete graphs, and introduces a block-coordinate-descent solver. Its argument depends on graph connectivity in a way that sparse graphs break. Community detection thresholds and the weak Ramanujan property shows that adjacency eigenvectors of sparse graphs localize on hubs. Understanding Regularized Spectral Clustering via Graph Conductance shows that low Laplacian eigenvectors localize on low-conductance dangling sets. Together, these papers motivate the gap rather than solving it.

Our claim is that the low eigenvalues produced by localization are mostly irrelevant to exactness. A leaf node's rotation can always satisfy its single measurement exactly. A path of degree-2 nodes is itself a tree and carries no internal non-convexity. What can genuinely break exactness is redundancy under noise: cycles in the kernel, and real bottlenecks between well-connected regions.

The non-backtracking operator already encodes this distinction. The Ihara–Bass identity states

$$\det(I - uB) = (1-u^2)^{m-n}\det\big(I - uA + u^2(D - I)\big),$$

where $B$ is the $2m\times 2m$ non-backtracking matrix on directed edges, $A$ and $D$ are the adjacency and degree matrices, $n$ and $m$ are the node and edge counts, and $u$ is a scalar. Setting $u = 1/r$ and multiplying by $r^2$ turns the right-hand matrix into the Bethe-Hessian $H_r = (r^2-1)I + D - rA$. The non-backtracking spectrum is unchanged by attaching trees, and it treats a chain of $k$ edges as one effective link.

We therefore replace $\lambda_2(L)$ in the certificate with $\lambda_2(L_{\mathcal K})$. Here $L_{\mathcal K}$ is the Laplacian of the kernel graph $\mathcal K$: the 2-core with every maximal degree-2 chain of length $k$ contracted to a single edge of weight $1/k$. This is the series-resistance rule, matching the way measurement noise accumulates along a chain. We will also report bottlenecks in $\mathcal K$ that the Bethe-Hessian identifies as genuine communities, meaning detectable above the Kesten–Stigum threshold, the information-theoretic limit for detecting communities in sparse random graphs.

The prediction is falsifiable. Consider graphs whose raw Fiedler value differs by orders of magnitude but whose kernels match. Their empirical exactness thresholds should match. Graphs with matched raw Fiedler value but a real kernel bottleneck should lose exactness earlier.

Research Program

Empirical stage. For each measurement graph and noise level, we solve rotation averaging over $SO(3)$ with the dual block-coordinate-descent solver of Rotation Averaging and Strong Duality. We then check the a posteriori dual certificate: a positive-semidefinite slack matrix whose null space contains the rank-one-per-block solution. This defines an empirical threshold $\sigma^*$, the largest noise level at which at least 95% of trials are certified exact. Alongside $\sigma^*$ we record the raw Fiedler value, the 2-core Fiedler value, the normalized-Laplacian gap, $\lambda_2(L_{\mathcal K})$, and the inverse participation ratio (a standard localization score) of the corresponding eigenvectors.

Graph families. We use three. The first is cycle graphs, where the source reports that local solvers fail 30–70% of the time while the dual succeeds 100% of the time. The second is degree-corrected stochastic block models, which generate random graphs with planted communities and heavy-tailed degrees, standing in for multi-session mapping with sparse inter-session loop closures. The model and its spectral theory follow Gulikers et al. and Community detection with the Bethe-Hessian. The third is edge-subsampled versions of the 322-camera Buddha graph.

Theoretical stage. We aim to prove that a dual certificate for the full graph can be assembled from three pieces: a certificate on the kernel, explicit certificates on trees, and explicit certificates on chain interiors. Tree certificates are trivial. Chain-interior certificates should exist because paths contain no cycles. The kernel certificate would use effective edge noise inflated by chain length.

The resulting bound would have the same form as the source paper's, with $\lambda_2(L)$ replaced by $\lambda_2(L_{\mathcal K})$ and with an explicit penalty for chain length. Two points about the chordal-distance cost on chains are not settled. Contracting a chain is only approximately equivalent to a single edge at small noise, and the composition may introduce a constant-factor loss. Both are open, and we will report the bound with whatever constant the proof yields.

Semidefinite programs on sparse random graphs and their application to community detection proves that a community-detection SDP on bounded-degree graphs reaches the Kesten–Stigum condition, in the form $(a-b)^2/(4d) > 1 + o_d(1)$, without suffering hub localization. This motivates the hypothesis that SDPs themselves are robust to localization and that only the existing bounds are not. That proof uses Grothendieck-type machinery for a different objective, so we borrow the intuition, not the technique.

Design stage. This is where the nonlinear-systems direction enters, as the application regime. Pose-graph estimation for nonlinear robot motion is the setting where a certificate matters before data is collected. Given a sparse graph and a budget of $K$ candidate loop closures, we choose edges to maximize the certified noise tolerance. We then measure the realized $\sigma^*$ after adding them.

Maximizing the raw Fiedler value by adding edges is a convex weight-design problem, but it will spend budget patching dangling leaves. Maximizing $\lambda_2(L_{\mathcal K})$ should spend it on kernel cycles and community bridges. Joint Community Detection and Rotational Synchronization via Semidefinite Programming shows that clustering and synchronization interact, but it assumes dense or moderately sparse graphs and standard Laplacians. We take the sparse case and use community structure as a diagnostic of which low modes are real, not as a variable to estimate jointly.

Baselines

Naive reference. The do-nothing reference is the existing Fiedler-value bound of Rotation Averaging and Strong Duality, applied unchanged to the raw measurement graph. It is the strongest existing a priori certificate in the file. The only reported figure is its complete-graph safe zone of roughly 42.9°. For sparse heterogeneous graphs we found no reported result on Lacuna for either its bound or the empirical exactness threshold, so we will compute both ourselves. Every candidate quantity is evaluated on identical graphs, noise draws and solver runs, so the comparison costs nothing beyond eigenvalue computations.

Ablations. The 2-core Fiedler value tests whether pruning trees alone explains the gain. The full kernel quantity, which adds chain contraction, must beat it on graphs rich in corridors for the contraction to be justified.

Normalized and regularized competitors. The normalized-Laplacian gap and the regularized Laplacian with a diagonal shift $\tau$ are included because they are the standard localization fixes, as analyzed by Zhang et al.. Their $\tau$ gets the same small grid-tuning budget, selected on held-out graph families.

Upper reference. The a posteriori certificate is ground truth, not a competitor.

What counts as success. We beat the baselines if the kernel quantity's rank correlation with $\sigma^*$ across graphs is clearly higher than that of the 2-core Fiedler value, and if its implied bound is non-vacuous on graphs where the raw bound is near zero.

Loop-closure baselines. For the design task, the baselines are random selection, greedy maximization of the raw Fiedler value, and greedy maximization of the 2-core Fiedler value, all under the same edge budget. Success means a higher realized $\sigma^*$ at equal $K$.

Why not just…?

Why not just prune trees and apply the existing bound to the 2-core? This is the most serious threat, and it is why the proposal starts from the 2-core rather than claiming credit for removing trees. Pruning removes dangling-set localization exactly. It does not remove the Fiedler collapse caused by long degree-2 corridors, where a path of length $\ell$ has Fiedler value on the order of $1/\ell^2$. Those corridors are common in trajectory graphs, and on them the existing bound will stay vacuous. The corridor-rich synthetic family will settle this. If the 2-core Fiedler value predicts $\sigma^*$ as well as the kernel quantity, we will report that the contraction adds nothing and that pruning is sufficient.

Why not just check the a posteriori certificate and skip a priori bounds? For a single solved instance, that is what one should do, and our experiments rely on it. An a posteriori check cannot tell a designer which measurements to collect before solving, or whether a sensor layout will stay certifiable as noise grows. The loop-closure experiment tests directly whether the a priori quantity changes decisions. If kernel-guided selection is no better than raw-Fiedler or random selection, the a priori bound has little practical value and we will say so.

Why not just use the normalized or regularized Laplacian? These operators blunt hub localization, but Zhang et al. show that the regularized version is sensitive to $\tau$: too small and it stays localized, too large and it washes out real structure. On Polblogs, Revisiting the Bethe-Hessian reports overlap 0.26 for adjacency spectral clustering against 0.91 for the tuned Bethe-Hessian, which is evidence that naive operators misjudge which modes are real. That evidence comes from community detection, not certification, so we include these operators as baselines and let the correlation with $\sigma^*$ decide.

Proposed Experiments

Matched-Fiedler test. This is the primary decisive check. We build pairs of graphs with equal kernels but raw Fiedler values differing by more than an order of magnitude, by attaching trees and inserting corridor subdivisions. We also build pairs with equal raw Fiedler value but different kernel bottlenecks, by planting two degree-corrected communities joined above versus near the Kesten–Stigum threshold. The hypothesis predicts that $\sigma^*$ is invariant within the first kind of pair and differs within the second. The opposite pattern refutes it.

Robustness on real data. We subsample the Buddha graph's edges to average degrees of 3–6 and compare all candidate predictors. We report computation time against the source's 16.7-second block-coordinate-descent runtime, to confirm that the sweep is feasible; the source reports more than 1700 seconds for a generic SDP solver on the full graph.

Cycle sanity check. On cycle graphs we check that our pipeline reproduces the source's 100% dual success at its noise levels.

Loop-closure design. We evaluate the design task on degree-corrected stochastic block model graphs and subsampled Buddha graphs at budgets $K$ from 1% to 10% of $m$, measuring realized $\sigma^*$ against the baselines above.

Outcomes. A positive outcome on the matched-Fiedler test together with a proven kernel bound would give the first non-vacuous exactness guarantees for rotation averaging on sparse, heterogeneous graphs. A negative outcome would show that localized Laplacian modes do affect exactness, which would itself correct the intuition taken from Semidefinite programs on sparse random graphs.