Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration
Connor Holmes, Abhishek Goudar, Timothy D. Barfoot
cs.RO
2026-09-03
CP-Cert walks from a candidate onto the SDP central path to recover dual certificates when redundant constraints make the dual non-unique, far faster than Mosek.
Many robotics problems are QCQPs with a Shor SDP relaxation. When the relaxation is tight, a local candidate that matches the SDP cost can be certified globally. The fast path is: run a local solver, recover dual multipliers, test that the certificate matrix is PSD.
Tightness often comes from redundant constraints, and at a rank-one candidate the dual is no longer unique. The linear system is underdetermined, so the community falls back to a full interior-point solve. Mosek-class solvers struggle past a few hundred variables in real time. Data association and matrix-weighted pose registration live in that degenerate regime.
Along the central path the dual is unique, and as μ→0 those duals meet the SDP KKT system. A rank-one candidate is already in hand, so a cold start from the analytic center is unnecessary.
CP-Cert perturbs X̂=xxᵀ by δI into the interior of the PSD cone, follows a cost-constrained central path (ε replaces the barrier parameter μ and can be initialized from the primal alone), and walks back toward the candidate. The primal round trip exists to carry dual multipliers. Exact convergence is not required: if complementarity is below τc and Ĥ+τp I admits a Cholesky factor, stop early. If the candidate is not global or the relaxation is not rank-tight, the primal iterate drifts from x̂ and a Frobenius-angle threshold declares failure.
The bottleneck is the Schur-complement system, solved with preconditioned conjugate gradients. The preconditioner is built from the candidate and uses sparsity and parallelism, avoiding repeated large factorizations. Loraine also uses PCG for low-rank SDP, but does not use a candidate for initialization or preconditioning.
A new SDP relaxation of pointcloud data association, in the spirit of the Lovász theta function, is empirically rank-tight on robotics instances and therefore certifiable. The pieces feed a stereo pipeline: SuperPoint and LightGlue matches, RAFT-Stereo disparity, an inverse stereo model with anisotropic covariances, CLIPPER cliques, then CP-Cert on both association and matrix-weighted registration.
On 900 Stanford Bunny trials, 842 relaxations are rank-tight. Confusion rates among those:
| Local method | TP (certified and global) | FN (global, not certified) |
| CLIPPER | 83.02% | 0.24% |
| Mosek global | 99.29% | 0.71% |
| PMC | 50.83% | 0.00% |
| RANSAC | 22.45% | 0.00% |
No local minimum was certified (FP is 0). Rank tightness is 100% for α≥0.6; CLIPPER inliers are most useful for registration when α sits between 0.5 and 2.
Runtime versus number of associations is roughly cubic for both CP-Cert and Mosek, with a two-to-three-order gap in the constant. With many outliers and nearly 20k constraints, successful certification stays near 100 ms. On a tiny pose SDP (n=13, m=21) success takes 0.9–1.1 ms versus Mosek 4.2–7.3 ms.
On a real stereo pipeline with 0.05–1.0 s frame gaps, association certifies 93.6–94.1% of the time and pose registration 100%. Mean translation error is 0.0025–0.0210 m, rotation 0.040–0.293°. Successful association certificates take 351–981 ms (2–4.6 s on failure); pose certificates stay at 1.2–1.5 ms.
Redundant constraints tighten the relaxation and block the usual certify-after-local-solve shortcut. CP-Cert is built for that degeneracy, so a graph method like CLIPPER can claim a globally optimal clique in near real time without resolving the SDP. Stereo relative pose can then sit on certified inliers. It is a certifier, not a more accurate frontend.
Rank tightness is assumed; 58 of 900 Bunny trials miss it. Several parameters (δ, ε schedule, angle threshold) need retuning per problem. Failure paths are slower than success paths because early stopping is asymmetric. The association SDP still scales cubically with matches, and that second is the expensive step in the pipeline. The stereo experiment is not tuned for error, so the pose numbers are not a SOTA registration claim. Unlike a general low-rank SDP solver, CP-Cert needs a candidate.