acceptodds
Under review as a conference paper at ICLR 2027

Globally Optimal Robust Rotation Averaging

Abstract

Rotation averaging (recovering absolute orientations from pairwise relative rotations) underlies global Structure from Motion, multi-scan registration, and cryo-electron microscopy, and in all three the measurements are heavily contaminated by outliers. Robust solvers tolerate the contamination but certify nothing; certifiable relaxations certify a least-squares surrogate that outliers render meaningless. We certify the robust objective itself: maximum consensus, the NP-hard number of measurements explainable within a tolerance. Covering the rotation group with cells of certified radius turns the continuous problem into two integer Markov random fields that bracket its optimum (cell-centre decoding from below, radius-inflated satisfiability from above), and a single branch and bound with an admissible node bound solves both at once. Because both ends are integers, subdivision does more than shrink the bracket: we prove it closes at a finite resolution set by the instance's own margin, for all but finitely many tolerances. The certificate is stated in the units that matter: the returned rotations explain measurements, and no rotations explain more. On synthetic graphs, the bracket closes on every instance in about a minute, and the solver is the most accurate method at every outlier rate we test and the only one still standing at . As an outlier-classification front end with a single parameter set, it improves the state of the art in Structure from Motion, multi-scan registration, and cryo-EM orientation recovery. The source code will be made public.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
rotation synchronization, optimal methods, structure-from-motion

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_RNXQOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a new method to maximize consensus rotation averaging. Their method uses a discretization of SO(3). The search over this discretization becomes a pairwise Markov Random Field. They then use shrinking upper and lower bounds to converge to a solution. In theory, they get exact recovery under some conditions on the inlier and outlier sets of pairwise measurements. Experiments demonstrate that their method outperforms some existing methods in some regimes.

Critical strengths

The method outperforms many existing algorithms for robust rotation synchronization. These include other message-passing algorithms and energy minimization methods on a variety of datasets.

The direct optimization of a consensus measure seems to have been pursued only in the context of random-sampling methods (such as RANSAC). The use of the MRF appears novel and is an interesting approach to getting robust rotation synchronization to work.

Critical weaknesses

In its current state, the paper is quite difficult, if not impossible, for a human to read. Jargon is frequently used and undefined, the text does not clarify as it goes in a way that is natural for a human reader, and there is not enough signposting/roadmaps to really get a sense of what is going on. Furthermore, I am left wondering what has really been proven and why it matters.

The method considered is a rotation averaging method. For large-scale 3D reconstruction, methods have moved towards foundation model-based approaches. The authors do not sufficiently motivate why we should still care about these incremental solvers in this larger context. In fact, on all datasets tested, state-of-the-art methods are typically found by these learned methods, and they are also quite robust. This is especially relevant to a conference like ICLR, and I therefore do not find it to be a good and modern fit.

Questions for authors

Could the authors expand on their review of related work? It appears to be mostly AI-generated, and many references have been missed historically in the development of robust rotation synchronization.

Also, it would be nice to have a better idea of the relevance of these ideas to the modern structure-from-motion and 3d vision landscape, and why these developments are important and useful.

Reviewer_mGAJOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a certified method for maximum consensus in rotation averaging (RA), aiming to certify the maximum number of measurements that can be classified as inliers and determine when this maximum has been reached. To transform the continuous rotation estimation problem into a discrete inlier-count optimization problem, the authors consider the angle-axis-to-rotation map and subdivide the 3D cube of angle-axis vectors into axis-aligned subcubes with certified radii, which bound the distance between any rotation from the cell and the cell's representative rotation. By assigning each node of the RA graph to a cell, the authors define pairwise Markov random field (MRF) potentials that (i) test whether an edge is an inlier when evaluated at the representative rotations of its endpoint cells and (ii) test whether any pair of rotations within those cells could make the edge an inlier. The optimal values of these two potentials, which can be computed efficiently using branch-and-bound, provide lower and upper bounds on the maximum-consensus count. This bracket is progressively tightened by refining the cells and repeating the process, after which RA is a benine least squares problem over the certified inliers. Experiments on controlled synthetic and real-world datasets demonstrate consistent robustness compared with the considered baselines (L1+IRLS, Spectral, CycleFlt, GNC-TLS, and GNC-GM).

Critical strengths
  • The proposed method effectively certifies the maximum inlier count in rotation averaging, supported by theoretically derived guarantees.
  • The experimental results support the claims of improved robustness over the considered baselines, particularly at high noise levels and on sparse graphs.
Critical weaknesses
  • Lack of comparison with certifiable baselines. The considered baselines (L1+IRLS, Spectral, CycleFlt, and GNC) are primarily local solvers that do not provide certificates of global optimality. However, as the authors discuss in the “Certifiable Estimation” subsection of Related Work, some methods, such as Shonan and SE-Sync, can provide optimality certificates under certain noise conditions. Although certificates of optimality differ from the certificates of the maximum number of explainable measurements explored in this paper, comparisons with such methods would help contextualize the research question of what should be certified: the objective value or the optimality of the solution. The selected local solvers are not sufficiently strong competitors to establish the superiority of the proposed method in terms of solution quality and robustness.

  • Limited evaluation of the noise model. The use of uniformly distributed outlier noise may make inliers and outliers relatively easy to distinguish, since outlier measurements can differ substantially from consistent measurements. It would be useful to evaluate the method under, for example, multiplicative rotational noise, which corrupts existing measurements through random perturbations rather than replacing them with entirely random measurements, as is commonly considered in rotation averaging. Such an evaluation would help establish whether the method remains effective when measurements are corrupted in ways that make inliers and outliers harder to distinguish.

Minor typo: Appendix A.2: A closing bracket appears to be missing in “(consequence (a)” and “(consequence (a).”

Questions for authors

Why has the comparison to stronger baselines been left out? Is it still feasible to include?

Reviewer_UoVFOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a method for robust rotation averaging with maximum-consensus certificates. It discretizes SO(3) into cells and uses two integer MRFs to bound how many relative rotation measurements can be explained. Branch and bound with cell subdivision tightens the bounds. TRW-S and IRLS provide the initial estimate, and the search region is restricted for larger problems. Experiments show good performance on synthetic graphs, SfM, multi-scan registration and simulated cryo-EM.

Critical strengths
  1. The finite-resolution analysis is interesting. Under the stated tolerance condition, the bounds can exactly close after enough subdivision of the search region.

  2. The framework can work with different initial estimates and valid MRF bounds. It can still return a bound when the search is stopped early.

  3. Strong robustness in synthetic experiments across three graph structures and 20 seeds. On full graphs with 90% uniformly random outliers, the median error is only 0.81 degrees.

  4. The proposed method is validated on different applications with the same grid and tolerance. With identical features and matching, GLOMAP AUC@5 improves by 4.4 points on ETH3D and 8.3 on Haiper.

Critical weaknesses
  1. The global optimality claim is too strong. In Appendix B.2, the regional count is below the truth's count on 9/20 instances at 50% outliers and 12/20 at 70%. These solutions are not globally optimal. Section 3.4 only expands the region when the bounds do not close, how can it handle these already closed cases? The authors should report how many instances actually get global certificate.

  2. Runtime comparison is not clear. Table 1 only measures Stage A on GPU, while the full CPU pipeline takes 65-72 seconds on sparse graphs with N=100 in Table 5. The claimed 3-9x speedup does not include certification. I would expect separate runtime for estimation and certification, with hardware details for all methods.

Questions for authors
  1. How do the authors keep the IRLS-polished estimate inside the search region in Algorithm 1? Theorem 3 requires this, but the polishing step does not clearly include this constraint.
2 comments

Thank you for your thorough review.

1. Global vs. Regional Certificates and Fixing Section 3.4

You are right: when Stage B prunes the 30° grid around the Stage A estimate instead of keeping all of SO(3)N\mathrm{SO}(3)^N, closing the bound gap certifies a regional optimum over the retained region U\mathcal{U}, not a global one. We will retitle the paper "Certified Consensus for Robust Rotation Averaging", revise the abstract and Sec. 3.4 to separate global (U=SO(3)N\mathcal{U} = \mathrm{SO}(3)^N) from regional (U⊊SO(3)N\mathcal{U} \subsetneq \mathrm{SO}(3)^N) certificates, and report the exact counts:

  • Every certificate in the paper is regional. Across N=10,20,50N = 10, 20, 50 in all 3 topologies and N=100N = 100 full at 50% outliers (5 seeds each, incl. Table 5), 50/50 close regionally. On the sparse N=100N = 100 graphs of Table 5 and App. B.2 (20 seeds), 20/20 close regionally at both 50% and 70%, reaching the ground-truth count on 11/20 and 8/20.
  • Global mode is exact but exhaustive. We ran it (every root cell kept, no cap) on the 20 sparse graphs at 50%: it returns the root bracket and stops because the first subdivision needs about 1 TB of pairwise tables (measured 1,017–1,034 GB). Sec. 3.4's Stage B will state this directly.

Fixing Section 3.4's fallback rule. Relaxing pruning only when branch-and-bound leaves an open gap cannot detect when pruning dropped a camera's true cell outside U\mathcal{U} and search converged inside U\mathcal{U} (9/20 runs at 50% outliers and 12/20 at 70% in App. B.2). We remove that claim and add a greedy coordinate sweep (Iterated Conditional Modes, ICM, 30 restarts) between Stages A and B that re-seats every camera over all 30° root cells without pairwise tables (+1.4–2.6 s). Stage B then builds the region around the swept incumbent. On the 20 sparse graphs at 50% outliers the full pipeline still closes 20/20 (median 60 s, max 101 s), and the certified count now matches or exceeds the ground-truth count on 20/20 instead of 11/20 (0.56° error). At 70% outliers it also closes 20/20 (median 76 s, max 111 s), with the certified count below ground truth on 2/20 instead of 12/20 (0.74° error). App. B.2 will report the 2 remaining cases (1 and 4 edges short).

2. Estimation vs. Certification Runtime and Hardware Parity

Table 1 timed Stage A (GPU + CPU), while Table 5 ran the full loop on CPU (64.4 s mean / 65.2 s med. at 50%: 9.4 s Stage A + 55.0 s Stages B-C, and 74.1 s / 72.2 s at 70%). Running GPU + CPU closes 20/20 regional certificates at N=100N = 100 in 1.28 s (0.38 s Stage A + 0.90 s Stages B–C, 1.98 s with ICM). Mean runtimes on sparse 50%-outlier graphs (20 seeds, i9-10900K CPU, RTX 4090 GPU, †error above 5°):

MethodHardwareStageN=100N = 100 timeN=1000N = 1000 time
GNC-GMCPUEstimation1.46 s365 s
GNC-TLSCPUEstimation1.99 s985 s
L1+IRLSCPUEstimation0.07 s30 s†
CycleFltCPUEstimation0.24 s0.57 s†
Ours (Stage A, Table 1)GPU + CPUEstimation0.38 s109 s
Ours (full, Stages A–C)GPU + CPUEst. + Cert.1.28 s (+ICM: 1.98 s)183 s
Ours (Table 5, deep BnB)CPU onlyEst. + Cert.64.4 s (med. 65.2 s)-

At N=1000N = 1000 (183 s = 102 s Stage A + 81 s Stages B-C), 17/20 close to 0 gap and 3/20 stop at level 16 with a 1-edge (0.01%) gap - still 2–5x faster than GNC. Sec. 4.1 will state this.

3. When IRLS Polishing Leaves the Search Region (Algorithm 1)

Correct: IRLS polishing (Line 9) is unconstrained. In global mode (U=SO(3)N\mathcal{U} = \mathrm{SO}(3)^N), Rpol∈UR _ {\mathrm{pol}} \in \mathcal{U} holds automatically. In regional mode (U⊊SO(3)N\mathcal{U} \subsetneq \mathrm{SO}(3)^N), RpolR _ {\mathrm{pol}} can leave U\mathcal{U} and achieve an inlier count Cinc\mathrm{C} _ {\mathrm{inc}} above the upper bound U\mathrm{U} of U\mathcal{U}, missing Line 11's equality test U=Cinc\mathrm{U} = \mathrm{C} _ {\mathrm{inc}}. Because U\mathrm{U} (Line 8) bounds every rotation in U\mathcal{U} before polishing, changing Line 11 to Cinc≥U\mathrm{C} _ {\mathrm{inc}} \ge \mathrm{U} proves R^\hat{R} beats or ties all of U\mathcal{U} - certifying optimality over U∪{R^}\mathcal{U} \cup \lbrace \hat{R} \rbrace without constraining IRLS, with max⁡(U,Cinc)\max(\mathrm{U}, \mathrm{C} _ {\mathrm{inc}}) as the anytime upper bound. Our C++ solver already checks this bound and, if search continues, inserts the next-level cell containing R^i\hat{R} _ i before rebuilding tables (we will update Alg. 1 to match).

Reviewer_UoVFOpenReview ↗

Thanks for the response

Thank authors for the detailed responses. I'd keep my positive score.

Comments on the paper

3 comments

Dear Reviewers,

Please let us know if you have further questions!

Thanks,
The Authors

Thank you for the constructive follow-up!

1. Existing Recovery Bounds vs. Our Guarantees

  • Baselines have stronger a priori guarantees, but they are not guaranteed to hold on real problems. Prior works such as LUD (Wang & Singer, 2013), CEMP (Lerman & Shi, 2022), and ReSync (Liu et al., 2023) prove recovery up to constant outlier rates. Our own a priori bound (Theorem 8) is weaker, as it uses a simple union bound. However, a priori guarantees rely on idealized assumptions (random graphs, uniform outliers, or dense 3-cycles) that rarely hold on actual scenes.
  • Our main guarantees (Theorems 3-4) are a posteriori: they certify the actual problem at hand. They bound the consensus count directly on the observed graph, with zero assumptions on graph structure or outliers. Directly targeting consensus on the actual instance, rather than surrogates built for idealized models, is also why our solver outperforms the baselines across our experiments on multiple different problems (Structure-from-Motion, Cryo-Electron Microscopy, 3D scan registration). We will add this comparison to the paper.

2. Clarity and Motivation

We uploaded a revised PDF with a thoroughly rewritten Section 3 (highlighted in blue) as a first-round readability improvement, adding an upfront roadmap, a notation summary table (Table 1), step-by-step stage definitions, and the comparison to prior recovery guarantees in Section 3.5.

We hope this directly addresses your clarity concerns, and we will integrate the remaining rebuttal additions and further polishing across the rest of the paper for the final version.

Best regards,
The Authors

Dear Area Chair and Reviewers,

We have uploaded a revised PDF focusing specifically on rewriting Section 3 (Method, highlighted in blue) - adding a clear roadmap, a notation table (Table 1), step-by-step stage definitions, and a comparison to prior theoretical recovery bounds (Sec. 3.5) - so reviewers can directly verify the improved readability. To avoid rushed layout compression before the deadline, all other additions already reported in full in our rebuttal comments below will be incorporated into the final manuscript.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.