Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration

• URL: http://arxiv.org/abs/2609.03222v1
• Date: Wed, 02 Sep 2026 23:39:56 GMT
• Title: Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration
• Abstract summary: Central-Path Certifier (CP-Cert) is a certifiable method explicitly to certify candidate optima to problems that exhibit degeneracy.<n>We show that CP-Cert is fast and scalable, achieving outliers that are up to three orders of magnitude faster than state-of-the-art direct solvers.
• Score: 13.351125897016368
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Certifiable methods have arisen as a means to guarantee global optimality of solutions to non-convex problems using convex semidefinite programming (SDP) relaxations. The most performant of these methods use a local solver to obtain the candidate solution, and then certify its optimality using efficient linear algebra techniques. However, for many problems of interest in robotics, this local-solve-then-certify approach is impeded by a form of degeneracy in the relaxation, leaving a costly optimization of the relaxation as the only recourse. In this paper, we introduce our Central-Path Certifier (CP-Cert), a certifiable method explicitly tailored to certify candidate optima to problems that exhibit this form of degeneracy. Using a candidate as a starting point, our approach seeks a nearby region of the feasible space -- known as the central path -- where a valid certificate can be readily obtained. The approach is kept efficient by exploiting indirect linear algebra techniques, problem sparsity, and parallelism. We apply CP-Cert to both matrix-weighted pose registration and pointcloud data association, whose novel SDP relaxation is of independent interest. On simulated examples, we explore the properties of this novel relaxation and show that CP-Cert is fast and scalable, achieving runtimes that are up to three orders of magnitude faster than state-of-the-art direct solvers. Finally, we combine these contributions into a certifiable, outlier-robust pose-estimation pipeline, which we apply to real-world data.

Related papers

• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs [50.41998220099097]
  Data errors, corruptions, and poisoning attacks during training pose a major threat to the reliability of modern AI systems.<n>We introduce MIBP-Cert, a novel certification method based on mixed-integer bilinear programming (MIBP)<n>By computing the set of parameters reachable through perturbed or manipulated data, we can predict all possible outcomes and guarantee robustness.
  arXiv  Detail & Related papers  (2024-12-13T14:56:39Z)
• Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling [46.01254613933967]
  Online learning methods are still highly effective for high-dimensional streaming data, out-of-core processing, and other throughput-sensitive applications. Many such algorithms rely on fast adaptation to individual errors as a key to their convergence. While such algorithms enjoy low theoretical regret, in real-world deployment they can be sensitive to individual outliers that cause the algorithm to over-correct.
  arXiv  Detail & Related papers  (2024-10-31T03:35:48Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  We introduce a general approach for seeking high dimensional non-linear optimization problems in which maintaining safety during learning is crucial. Our approach called LBSGD is based on applying a logarithmic barrier approximation with a carefully chosen step size. We demonstrate the effectiveness of our approach on minimizing violation in policy tasks in safe reinforcement learning.
  arXiv  Detail & Related papers  (2022-07-21T11:14:47Z)
• Accelerating Certifiable Estimation with Preconditioned Eigensolvers [2.1701691499017812]
  A dominant cost in many state-of-the-art (Burer-Monteiro factorization-based) estimation methods is solution verification. We show how to significantly accelerate this verification step, and thereby the overall speed of certifiable estimation methods. We show how to address this challenge using preconditioned eigensolvers.
  arXiv  Detail & Related papers  (2022-07-12T02:00:08Z)
• Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite Relaxations and Scalable Global Optimization [29.738513596063946]
  We propose the first general framework to design cert algorithms for robust geometric perception in the presence of outliers. Our experiments demonstrate that our SDP relaxation is exact with up to outliers across applications.
  arXiv  Detail & Related papers  (2021-09-07T21:42:16Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers [32.1176248075545]
  We propose the first general and practical to design certifiable algorithms for perception in the presence of a large amount of outliers. Our dual certifiers leverage solution-of-any suboptimal optimality of any problem.
  arXiv  Detail & Related papers  (2020-06-11T19:46:42Z)
• Certifiable Relative Pose Estimation [2.0840789905678485]
  We present the fast optimality certifier for the non-minimal version of the Relative Lagrangian problem for cameras from epipolar cameras. The proposed certifier is based on a novel closed-form expression for dual points.
  arXiv  Detail & Related papers  (2020-03-30T18:26:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.