Certifiable Alignment of GNSS and Local Frames via Lagrangian Duality

• URL: http://arxiv.org/abs/2512.20931v1
• Date: Wed, 24 Dec 2025 04:24:33 GMT
• Title: Certifiable Alignment of GNSS and Local Frames via Lagrangian Duality
• Abstract summary: Esting the absolute orientation of a local system relative to a global navigation satellite system (GNSS) reference often suffers from local minima and high dependency on satellite availability.<n> methods for this alignment task rely on abundant satellites unavailable in-degraded environments, or use local optimization methods which cannot guarantee the optimality of the alignment.<n>The proposed method is certifiable, meaning it can numerically fill a gap where existing local convexs fail.
• Score: 11.186187106454957
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Estimating the absolute orientation of a local system relative to a global navigation satellite system (GNSS) reference often suffers from local minima and high dependency on satellite availability. Existing methods for this alignment task rely on abundant satellites unavailable in GNSS-degraded environments, or use local optimization methods which cannot guarantee the optimality of a solution. This work introduces a globally optimal solver that transforms raw pseudo-range or Doppler measurements into a convexly relaxed problem. The proposed method is certifiable, meaning it can numerically verify the correctness of the result, filling a gap where existing local optimizers fail. We first formulate the original frame alignment problem as a nonconvex quadratically constrained quadratic program (QCQP) problem and relax the QCQP problem to a concave Lagrangian dual problem that provides a lower cost bound for the original problem. Then we perform relaxation tightness and observability analysis to derive criteria for certifiable optimality of the solution. Finally, simulation and real world experiments are conducted to evaluate the proposed method. The experiments show that our method provides certifiably optimal solutions even with only 2 satellites with Doppler measurements and 2D vehicle motion, while the traditional velocity-based VOBA method and the advanced GVINS alignment technique may fail or converge to local optima without notice. To support the development of GNSS-based navigation techniques in robotics, all code and data are open-sourced at https://github.com/Baoshan-Song/Certifiable-Doppler-alignment.

Related papers

• Gradient based Bilevel for Inverse Optimal Control, a Riemannian approach [5.398550081886241]
  Inverse Optimal Control (IOC) aims to recover the cost function that explains observed trajectories as solutions of an optimal control problem.<n>Recent projection-based approaches offer a promising alternative but suffer from numerical instability when solved with gradient-based methods.<n>We show that these difficulties stem from the geometric structure of the IOC feasible set.
  arXiv  Detail & Related papers  (2026-06-09T13:27:01Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• 3-D Relative Localization for Multi-Robot Systems with Angle and Self-Displacement Measurements [7.572458613193042]
  We propose a novel 3-D relative localization framework based on inter-robot interior angle and self-displacement measurements.<n>We address three primary challenges existing in the Posterior (MAP) problem.
  arXiv  Detail & Related papers  (2026-04-02T07:02:46Z)
• Implementing Robust M-Estimators with Certifiable Factor Graph Optimization [5.293483842121928]
  We develop an adaptive reweighting scheme for factor graph-based estimation in robotics.<n>We show how one can easily implement M-estimators with certifiably correct solvers for inner subproblems.
  arXiv  Detail & Related papers  (2026-03-21T20:17:44Z)
• DRAFTO: Decoupled Reduced-space and Adaptive Feasibility-repair Trajectory Optimization for Robotic Manipulators [4.0407133618465005]
  This paper introduces a new algorithm for trajectory optimization, Decoupled Reduced-space and Adaptive Feasibility-repair Trajectory Optimization (DRAFTO)<n>To reduce the number of repeated constrained optimizations while handling joint-limit feasibility, the optimization is decoupled into a reduced-space Gauss-Newton (GN) descent.<n>The results of our benchmark tests against optimization-based planners, such as CHOMP, TrajOpt, GPMP2, and FACTO, validate the high efficiency and reliability across diverse scenarios and tasks.
  arXiv  Detail & Related papers  (2026-03-10T20:24:42Z)
• Optimal Transportation and Alignment Between Gaussian Measures [80.4634530260329]
  Optimal transport (OT) and Gromov-Wasserstein (GW) alignment provide interpretable geometric frameworks for datasets.<n>Because these frameworks are computationally expensive, large-scale applications often rely on closed-form solutions for Gaussian distributions under quadratic cost.<n>This work provides a comprehensive treatment of Gaussian, quadratic cost OT and inner product GW (IGW) alignment, closing several gaps in the literature to broaden applicability.
  arXiv  Detail & Related papers  (2025-12-03T09:01:48Z)
• Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
  We show how to reduce the two-dimensional $(gamma, beta)$ search to a one-dimensional search over $gamma$, with $beta*$ computed analytically.<n>This approach is validated using Recursive QAOA (RQAOA), where it consistently outperforms both coarsely optimised RQAOA and semidefinite programs.
  arXiv  Detail & Related papers  (2025-01-27T19:00:00Z)
• Global Search of Optimal Spacecraft Trajectories using Amortization and Deep Generative Models [0.5898893619901381]
  We formulate the parameterized global search problem as the task of sampling a conditional probability distribution with support on the neighborhoods of local basins of attraction to the high quality solutions.<n>The approach is benchmarked on a low thrust spacecraft trajectory optimization problem in the circular restricted three-body problem.<n>The paper also provides an in-depth analysis of the multi-modal funnel structure of a low-thrust spacecraft trajectory optimization problem.
  arXiv  Detail & Related papers  (2024-12-28T04:57:12Z)
• Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
  Quantum Approximate Optimization Algorithm (QAOA) is considered as a promising candidate to demonstrate quantum supremacy. limited qubit availability and restricted coherence time challenge QAOA to solve large-scale pseudo-Boolean problems. We propose a distributed QAOA which can solve a general pseudo-Boolean problem by converting it to a simplified Ising model.
  arXiv  Detail & Related papers  (2023-10-08T08:07:11Z)
• Vanishing Point Estimation in Uncalibrated Images with Prior Gravity Direction [82.72686460985297]
  We tackle the problem of estimating a Manhattan frame. We derive two new 2-line solvers, one of which does not suffer from singularities affecting existing solvers. We also design a new non-minimal method, running on an arbitrary number of lines, to boost the performance in local optimization.
  arXiv  Detail & Related papers  (2023-08-21T13:03:25Z)
• 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)
• On the Effective Usage of Priors in RSS-based Localization [56.68864078417909]
  We propose a Received Signal Strength (RSS) fingerprint and convolutional neural network-based algorithm, LocUNet. In this paper, we study the localization problem in dense urban settings. We first recognize LocUNet's ability to learn the underlying prior distribution of the Rx position or Rx and transmitter (Tx) association preferences from the training data, and attribute its high performance to these.
  arXiv  Detail & Related papers  (2022-11-28T00:31:02Z)
• Pushing the Envelope of Rotation Averaging for Visual SLAM [69.7375052440794]
  We propose a novel optimization backbone for visual SLAM systems. We leverage averaging to improve the accuracy, efficiency and robustness of conventional monocular SLAM systems. Our approach can exhibit up to 10x faster with comparable accuracy against the state-art on public benchmarks.
  arXiv  Detail & Related papers  (2020-11-02T18:02:26Z)

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.