Aligning two 3D scans is a chicken-and-egg problem. To find which points match, you need to know how one scan is rotated and shifted relative to the other. To find that rotation and shift, you need the matches. Certifiable solvers break this loop by decoupling rotation from translation. They then check, through a convex relaxation called a semidefinite program (SDP: an optimization over positive semidefinite matrices that gives provable lower bounds on non-convex problems), that the returned rotation is the global optimum of a robust cost. That check answers the wrong question for a deployed system. A certified global optimum can still be the wrong pose when the scene is planar, symmetric, or barely overlapping, because some other, distant pose fits the data almost as well. An uncertified answer can also be perfectly accurate. What a robot or a mapping pipeline needs is a way to decide when to act and when to say "I don't know", with a guaranteed bound on how often an accepted alignment is wrong.
We propose to compute, for each scan pair, a certified ambiguity radius. This is the smallest angle $\theta$ such that a convex lower bound proves no rotation farther than $\theta$ from the estimate can match the data nearly as well as the estimate does. This radius becomes the confidence score of a selective predictor, a system that answers only on inputs it scores as trustworthy and abstains on the rest. Its acceptance threshold is calibrated with the binomial risk bounds of selective classification. The resulting abstention rule rests on an optimization-theoretic statement about the cost landscape, plus a small calibration layer that covers the distance between "unique optimum" and "correct pose". It does not rest on a heuristic count of agreeing matches. To keep it practical, the lower bound comes from cheap eigenvalue computations instead of interior-point SDP solves.
Core Claim
Existing certifiable registration produces a binary flag that conflates two different things: whether the solver found the optimum, and whether the optimum is unique. TEASER estimates rotation by graduated non-convexity, a method that solves a sequence of progressively harder smoothed problems. It then verifies global optimality after the fact with Douglas-Rachford splitting, a first-order method for finding dual certificates. Global Optimality for Point Set Registration Using Semidefinite Programming builds the dual matrix in closed form from a local solution and tests whether it is positive semidefinite. Both report yes or no, and both papers note that tightness collapses on planar or low-overlap scenes. Neither offers a policy for what to do then.
Our claim is that the right selection signal is a margin certificate, and that it can be computed at the same scale as these certifiers. Let $f(R)$ be the truncated least squares rotation cost over the pruned correspondences, a cost that caps each residual so outliers cannot dominate. Let $\hat R$ be the solver's estimate. For an angle $\theta$, define the exclusion set $E_\theta = \{R \in SO(3) : \mathrm{tr}(\hat R^\top R) \le 1 + 2\cos\theta\}$, which contains all rotations at least $\theta$ away from $\hat R$. The certified margin is
$$\Delta_\theta(x) = L_\theta(x) - f(\hat R),$$
where $x$ is the scan pair and $L_\theta(x)$ is any valid lower bound on $\min_{R \in E_\theta} f(R)$. If $\Delta_\theta > 0$, every global minimizer lies within $\theta$ of $\hat R$. This holds whether or not the unrestricted relaxation is tight. The exclusion constraint is linear in the lifted variable, so $L_\theta$ comes from the same relaxation with one extra inequality. $L_\theta$ is nondecreasing in $\theta$ because the feasible set shrinks, so the radius $\theta^*(x) = \min\{\theta : \Delta_\theta(x) > 0\}$ can be found by bisection.
The selector accepts $x$ when $\theta^*(x) \le \tau$. The threshold $\tau$ is set by Selection with Guaranteed Risk from Selective Classification for Deep Neural Networks, applied to the binary event "pose error exceeds the user's tolerance". The method attaches a high-probability bound to the selected risk. Because $\theta^*$ is a geometric quantity rather than a learned one, we expect the bound to survive dataset shift better than scores tied to match statistics.
Research Program
The first component is the bound itself, built to scale. We use weak duality: for any choice of Lagrange multipliers $y$, and any multiplier $\mu \ge 0$ on the exclusion constraint, the dual objective $d(y,\mu)$ is a valid lower bound whenever the dual matrix $S(y,\mu)$ is positive semidefinite. Every feasible lifted matrix in the truncated least squares relaxation has a fixed, known trace $T$. We exploit this to make the bound valid even when $S$ fails that test:
$$L_\theta \ge d(y,\mu) - T \cdot \max\big(0, -\lambda_{\min}(S(y,\mu))\big),$$
where $\lambda_{\min}$ is the smallest eigenvalue.
Every multiplier therefore yields a certificate, and improving the multiplier only tightens it. The work per evaluation is one extreme-eigenvalue computation on a sparse matrix by Lanczos iteration, an iterative method that finds extreme eigenvalues of large sparse matrices without forming dense factorizations. The matrix dimension is roughly $9(N+1)$ for $N$ correspondences surviving max-clique pruning.
We warm-start the multipliers in two ways. One is the closed-form dual construction of Iglesias et al., evaluated at the best rotation inside $E_\theta$ found by a low-rank factorized solve. That solve uses the Riemannian staircase of Boumal et al., which raises the rank of the factorization until optimality is reached. The other warm start is a few projected first-order dual steps. The factorized solve is only a heuristic for good multipliers. The landscape guarantees in that paper do not cover our inequality constraint, so the certificate never depends on it. This is how the proposal addresses the scalability direction: the valid bound needs no interior-point method and no exact dual solve. Interior-point solvers are used only on small instances, as an oracle that measures how loose the cheap bound is.
The second component is the selection layer. Rotation and translation are decoupled, as in TEASER and in the null-space method of the ℓ0-minimization paper. Given the rotation, translation is a one-dimensional robust estimate per axis, and its ambiguity margin can be computed exactly by enumeration. The joint score is the pair of radii, and we accept only when both are small. We calibrate the threshold with SGR on a held-out split. We also report a bounded-loss variant whose risk is the expected capped rotation error, extending the 0/1 setting that the file notes is largely unresolved for geometric outputs.
The third component is analysis. Under a bounded-noise inlier model, a positive margin at $\theta$, together with a correct inlier noise bound, implies that the true rotation lies within $\theta$ plus a noise term of $\hat R$. We will state and prove this relation. Calibration then only has to absorb violations of the noise model, which is where we expect robustness under shift to come from.
Baselines
The naive reference point is accept-everything, which gives the full-coverage risk of TEASER++ and of the ℓ0 method. On 3DMatch, TEASER reports up to a 98.6% success rate. On KITTI, the ℓ0-minimization paper reports 99.56% registration recall. These numbers bound how much risk reduction is possible on the easy benchmarks, which is why the low-overlap and planar settings matter most. We found no reported risk-coverage result for point cloud registration on Lacuna, so every selective baseline below is run by us.
The strongest competitor is a calibrated inlier-support selector. Its score is the size of the maximum clique of mutually consistent correspondences, or the final inlier count, from the same TEASER++ run, thresholded with the same SGR procedure. It is the most natural thing a practitioner would do, it costs nothing extra, and it plausibly ranks failures well. The second competitor uses TEASER++'s own certificate in two forms. One is the binary certify/no-certify flag, which gives a single operating point. The other is the continuous suboptimality gap between primal cost and dual bound, used as a score. That second form isolates our key ingredient: it measures optimality without the exclusion ball, so the difference between it and $\theta^*$ is exactly the value of certifying uniqueness rather than optimality. The third competitor is a multi-start agreement score: the angular spread of solutions from graduated non-convexity restarted from several perturbed initializations. The fourth is the ℓ0 method's Bayesian inlier posterior, used as a score.
All selectors share the same correspondences: FPFH descriptors plus one learned descriptor, the same max-clique pruning, the same calibration splits, the same $(r^*, \delta)$, and wall-clock time capped at the margin method's per-pair time. The multi-start baseline receives as many restarts as fit in that budget. Beating a baseline means a strictly lower area under the risk-coverage curve, plus higher coverage at matched guaranteed risk. Above all, under train-on-3DMatch, test-on-3DLoMatch/Redwood/KITTI calibration, the realized selected risk must stay below $r^*$ while the baseline's exceeds it.
Why not just…?
Why not just threshold the inlier count or clique size with SGR? This is the real threat, and on 3DMatch it may tie. Its known failure mode is the one TEASER describes for consensus methods: a large, self-consistent but wrong consensus set. Planar floors and repeated structure in Redwood, the scenes SDRSAC targets because descriptors fail there, produce exactly that, since many poses explain a plane equally well. Our stratified evaluation on planar and symmetric pairs settles the question. If the inlier selector matches us there too, the margin certificate adds no value and we will say so.
Why not just use the existing optimality certificate as the score? Optimality does not imply uniqueness. A symmetric object has several global optima, and the relaxation can be tight at a wrong one. Iglesias et al. further show certificates failing on near-planar data where local solutions may still be accurate, which would produce over-refusal. The suboptimality-gap ablation measures both effects directly.
Why not just restart the local solver from many initializations and check agreement? Agreement among restarts is cheap and catches many ambiguities. However, it can only find competing poses it happens to visit, and it is exactly the initialization-sensitive alternation that Ma et al. identify as fragile. The time-matched comparison will show whether exhaustive restarts close the gap. Synthetic Bunny variants with a hidden second near-optimal pose test whether restarts miss it while the bound does not.
Why not just threshold a deep matcher's confidence? Learned registration models generalize poorly to new environments, as the ℓ0 paper documents. Softmax-style confidence, competitive in Geifman and El-Yaniv, has no tie to the geometry. We include it in the shift experiment, where we expect its calibrated guarantee to break.
Why not just solve the exclusion SDP exactly with an interior-point solver? On instances of a few hundred correspondences we will do exactly that, as the looseness oracle. Beyond that, per-step cost $O(mn^3 + m^2n^2 + m^3)$ (Huang et al.) and the runtime growth reported by Iglesias et al. rule it out inside a bisection loop.
Proposed Experiments
We evaluate on 3DMatch and 3DLoMatch, KITTI, Redwood Office and Living Room, and Stanford Bunny with controlled outlier ratios up to 99%. The Bunny set also includes added planar and mirror-symmetric variants. Metrics are the risk-coverage curve and its area, coverage at guaranteed risk for several $(r^*, \delta)$, realized selected risk under shift, over-refusal (the fraction of rejected pairs that were actually correct), and per-pair runtime.
Three checks are decisive. First, on the planar and symmetric strata, $\theta^*$ must beat the calibrated inlier-support selector in area under the risk-coverage curve. Second, calibrated on 3DMatch, the margin selector must keep realized risk below $r^*$ on 3DLoMatch and Redwood where the baselines violate it. Third, on small instances, the eigenvalue-corrected bound must be close to the exact interior-point $L_\theta$, measured as the median ratio of the radii the two bounds certify. Runtime must remain within a small multiple of TEASER++'s certification step. Failing the first check means the idea reduces to inlier counting. Failing the third means the scalability argument does not hold and only the small-scale version survives.
References
- TEASER: Fast and Certifiable Point Cloud Registration
- Global Optimality for Point Set Registration Using Semidefinite Programming
- Selective Classification for Deep Neural Networks
- The non-convex Burer-Monteiro approach works on smooth semidefinite programs
- A robust inlier identification algorithm for point cloud registration via $\mathbf{\ell_0}$-minimization
- SDRSAC: Semidefinite-Based Randomized Approach for Robust Point Cloud Registration Without Correspondences
- Robust Estimation of Nonrigid Transformation for Point Set Registration
- Solving SDP Faster: A Robust IPM Framework and Efficient Implementation