pith. sign in

arxiv: 2512.20931 · v2 · pith:KY3JXFASnew · submitted 2025-12-24 · 💻 cs.RO

Certifiable Alignment of GNSS and Local Frames via Lagrangian Duality

Baoshan Song , Matthew Giamou , Penggao Yan , Chunxi Xia , Li-Ta Hsu This is my paper

Pith reviewed 2026-05-21 17:38 UTC · model grok-4.3

classification 💻 cs.RO
keywords GNSS frame alignmentLagrangian dualitycertifiable optimizationQCQP relaxationDoppler measurementsglobal optimalitypose estimationrelaxation tightness
0
0 comments X

The pith

A Lagrangian dual relaxation yields certifiable global optimality for GNSS-local frame alignment even with two Doppler satellites in 2D motion.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to solve frame alignment between a local system and GNSS without local minima or heavy reliance on many visible satellites. It reformulates the task as a nonconvex QCQP and relaxes it to a concave Lagrangian dual problem that supplies a lower cost bound. Analysis of when this relaxation is tight and when the measurements make the problem observable then supplies criteria that let a user numerically confirm the solution is globally optimal. This matters for navigation in places with sparse satellite signals, where prior local solvers can return incorrect answers without any warning that something is wrong.

Core claim

By converting the GNSS-local frame alignment task into a nonconvex QCQP and solving its Lagrangian dual relaxation, the authors establish sufficient conditions under which the dual solution coincides with the original problem's optimum, enabling certification of global optimality for alignments based on Doppler or pseudo-range data from as few as two satellites during two-dimensional motion.

What carries the argument

The concave Lagrangian dual of the nonconvex QCQP formulation for frame alignment, which supplies a computable lower bound and allows tightness checks to certify optimality.

If this is right

  • The alignment solution can be certified as optimal simply by checking whether the dual lower bound matches the primal cost.
  • Certifiably correct alignments become available in GNSS-degraded settings that contain only two usable Doppler measurements.
  • Local optimization routines such as velocity-based VOBA or GVINS may return undetected suboptimal points in the same minimal-data regime.
  • The derived observability conditions give explicit rules for when the certification procedure is guaranteed to succeed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same duality construction could be adapted to fuse GNSS data with additional inertial or visual measurements to reduce the satellite requirement further.
  • Similar Lagrangian relaxations might certify optimality in other nonconvex pose-estimation problems that currently rely on local solvers.
  • The tightness criteria could be tightened or generalized by incorporating higher-order motion models or additional measurement types.

Load-bearing premise

The relaxation tightness and observability criteria derived in the paper remain valid under the minimal conditions of two Doppler satellites and two-dimensional vehicle motion.

What would settle it

A concrete counterexample consisting of two Doppler satellites and planar motion in which a feasible primal solution achieves a strictly lower cost than the computed dual bound would disprove the claimed tightness guarantee.

Figures

Figures reproduced from arXiv: 2512.20931 by Baoshan Song, Chunxi Xia, Li-Ta Hsu, Matthew Giamou, Penggao Yan.

Figure 1
Figure 1. Figure 1: Illustration of alignment between GNSS e-frame and local w-frame. The key insight is to employ alignment of the local motion and its projection on the GNSS Doppler measurements which implies the global motion. this work, we refer to the initial rotation alignment between GNSS and local frames as initial alignment. Since rotations in three dimensions are described by the nonconvex special orthogonal group (… view at source ↗
Figure 2
Figure 2. Figure 2: Pipeline of certifiable alignment to more robotics problems, such as pose graph optimization (PGO) [18], indoor positioning [19], geometric registration [20], hand-eye calibration [21], rotation synchronization [22], wireless localization [23], camera arrangement [24], orbit determination [25], and opportunistic positioning [26]. This work proposes a certifiable GNSS/local initial frame alignment method us… view at source ↗
Figure 3
Figure 3. Figure 3: Optimality success rate in 2D motion. The success is confirmed when [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Optimality success rate in 3D motion. The success is confirmed when [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Doppler noise disturbance test with 3D motion. Noise level denotes the standard deviation of the Gaussian white noise. Alignment error means the [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Doppler noise disturbance test with 2D motion. Noise level denotes the standard deviation of the Gaussian white noise. Alignment error means the [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Under poor observability conditions (defined as two visible satellites), [PITH_FULL_IMAGE:figures/full_fig_p006_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Dataset scenes and vehicle trajectory (green lines) in the real tests [PITH_FULL_IMAGE:figures/full_fig_p007_8.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper formulates GNSS-local frame alignment from pseudo-range or Doppler measurements as a nonconvex QCQP, relaxes it to a concave Lagrangian dual providing a lower bound, derives tightness and observability criteria to certify when the dual solution equals the primal optimum, and claims this yields certifiably global solutions even with only 2 satellites under 2D motion—unlike VOBA or GVINS which may converge to local optima. Simulation and real-world experiments are presented, with code and data open-sourced.

Significance. If the tightness criteria are sufficient, the work supplies a practical certifiable solver for GNSS-degraded robotics navigation, filling a gap left by local optimizers. The open-source release is a clear strength for reproducibility.

major comments (2)
  1. [relaxation tightness and observability analysis] The central claim of certifiable optimality with 2-satellite Doppler measurements in 2D motion rests on the relaxation-tightness and observability analysis. It is unclear whether the derived criteria are sufficient to guarantee dual-primal equality in all configurations (including degenerate geometries) or only generic ones; if the latter, a numerical certificate could be issued even when a lower-cost feasible point exists, undermining the guarantee. A concrete counter-example check or explicit proof covering degenerate cases is needed.
  2. [Experiments] Experiments claim support for the minimal-observation case, but without reported failure rates, error bars, or explicit verification that the dual bound is achieved and no better feasible point exists in the tested 2-satellite Doppler trials, it is difficult to rule out post-hoc selection or incomplete coverage of degenerate geometries.
minor comments (2)
  1. [Formulation] Clarify notation for the dual variables and the mapping from raw measurements to the QCQP matrices.
  2. [Observability analysis] Add a short table summarizing the minimal conditions (number of satellites, motion dimensionality, measurement type) under which tightness is proven.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address each major comment below and agree that targeted revisions will strengthen the presentation of the tightness guarantees and experimental validation.

read point-by-point responses

  1. Referee: [relaxation tightness and observability analysis] The central claim of certifiable optimality with 2-satellite Doppler measurements in 2D motion rests on the relaxation-tightness and observability analysis. It is unclear whether the derived criteria are sufficient to guarantee dual-primal equality in all configurations (including degenerate geometries) or only generic ones; if the latter, a numerical certificate could be issued even when a lower-cost feasible point exists, undermining the guarantee. A concrete counter-example check or explicit proof covering degenerate cases is needed.

    Authors: We appreciate the referee's emphasis on this point. The tightness criteria are obtained from an observability analysis that characterizes the conditions for dual-primal equality in the minimal 2-satellite Doppler case under 2D motion. While the derivation targets the configurations relevant to the claim, we acknowledge that an explicit treatment of degenerate geometries would remove any ambiguity. In the revision we will add a dedicated subsection with a proof outline covering degenerate cases together with numerical verification on synthetic instances that satisfy the observability conditions, confirming that the dual bound is attained and no lower-cost feasible point exists. revision: yes

  2. Referee: [Experiments] Experiments claim support for the minimal-observation case, but without reported failure rates, error bars, or explicit verification that the dual bound is achieved and no better feasible point exists in the tested 2-satellite Doppler trials, it is difficult to rule out post-hoc selection or incomplete coverage of degenerate geometries.

    Authors: We agree that additional statistical reporting and verification would improve transparency. The current experiments already compare against VOBA and GVINS on both simulated and real data, but we will revise the section to include failure rates over repeated trials, error bars on the reported metrics, and explicit checks that the dual solution equals the primal cost (or that a feasible point with lower cost does not exist) for the 2-satellite Doppler trials. We will also ensure the test geometries span both generic and near-degenerate configurations. revision: yes

Circularity Check

0 steps flagged

Derivation relies on standard QCQP relaxation and tightness analysis without reduction to inputs

full rationale

The paper formulates GNSS-local frame alignment as a nonconvex QCQP, relaxes it to a concave Lagrangian dual providing a lower bound, and derives tightness/observability criteria via analysis to certify optimality under minimal 2-satellite Doppler conditions. This chain uses established convex relaxation methods and direct mathematical derivation rather than self-definitional loops, fitted parameters renamed as predictions, or load-bearing self-citations. No equations reduce the claimed certifiable optimality to prior fitted quantities or ansatzes by construction; the criteria and experiments provide independent content, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The method relies on standard convex optimization duality theory and observability conditions from control theory; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract description.

axioms (2)
  • standard math Lagrangian duality provides a tight lower bound for the original QCQP when relaxation conditions are met
    Invoked when transforming the nonconvex QCQP into the concave dual problem
  • domain assumption Observability analysis yields verifiable criteria for solution optimality
    Used to derive certifiable optimality conditions from the dual solution

pith-pipeline@v0.9.0 · 5800 in / 1362 out tokens · 58968 ms · 2026-05-21T17:38:19.346531+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    P. D. Groves,Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems. Boston, MA: Artech House, 2008. JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 8 TABLE III ALIGNMENTERROR OF THREE COMPARED METHODS IN THE REAL TESTS. Yaw error [°] MAE/STD/MAX Ave. Sat. Num. VOBA GVINS SDP Berlin1 4 5.76 2.27 11.98 4.72 2.59 10.84 4.69 2....

    work page 2008

  2. [2]

    Aerialvl: A dataset, baseline and algorithm framework for aerial-based visual localization with reference map,

    M. He, C. Chen, J. Liu, C. Li, X. Lyu, G. Huang, and Z. Meng, “Aerialvl: A dataset, baseline and algorithm framework for aerial-based visual localization with reference map,”IEEE Robotics and Automation Letters, 2024

    work page 2024

  3. [3]

    Localization requirements for autonomous vehicles,

    T. G. R. Reid, S. E. Houts, R. Cammarata, G. Mills, S. Agarwal, A. V ora, and G. Pandey, “Localization requirements for autonomous vehicles,” arXiv preprint arXiv:1906.01061, 2019, available: https://arxiv.org/abs/ 1906.01061

    work page arXiv 1906

  4. [4]

    Gici-lib: A gnss/ins/camera integrated navigation library,

    C. Chi, X. Zhang, J. Liu, Y . Sun, Z. Zhang, and X. Zhan, “Gici-lib: A gnss/ins/camera integrated navigation library,”IEEE Robotics and Automation Letters, vol. 8, no. 12, pp. 7970–7977, 2023

    work page 2023

  5. [5]

    Towards robust gnss positioning and real-time kinematic using factor graph optimization,

    W. Wen and L.-T. Hsu, “Towards robust gnss positioning and real-time kinematic using factor graph optimization,” in2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021, pp. 5884–5890

    work page 2021

  6. [6]

    A least squares estimate of satellite attitude,

    G. Wahba, “A least squares estimate of satellite attitude,”SIAM Review, vol. 7, no. 3, pp. 409–409, 1965

    work page 1965

  7. [7]

    Rapid initial heading alignment for mems land vehicular gnss/ins navigation system,

    Q. Chen, H. Lin, J. Kuang, Y . Luo, and X. Niu, “Rapid initial heading alignment for mems land vehicular gnss/ins navigation system,”IEEE Sensors Journal, vol. 23, no. 7, pp. 7656–7666, 2023

    work page 2023

  8. [8]

    Velocity-based optimization- based alignment (vboba) of low-end mems imu/gnss for low dynamic applications,

    Q. Zhang, S. Li, Z. Xu, and X. Niu, “Velocity-based optimization- based alignment (vboba) of low-end mems imu/gnss for low dynamic applications,”IEEE Sensors Journal, vol. 20, no. 10, pp. 5527–5539, 2020

    work page 2020

  9. [9]

    Optimization-based alignment for inertial navigation systems: Theory and algorithm,

    M. Wu, Y . Wu, X. Hu, and D. Hu, “Optimization-based alignment for inertial navigation systems: Theory and algorithm,”Aerospace Science and Technology, vol. 15, no. 1, pp. 1–17, 2011

    work page 2011

  10. [10]

    Least-squares fitting of two 3-d point sets,

    K. S. Arun, T. S. Huang, and S. D. Blostein, “Least-squares fitting of two 3-d point sets,”IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 698–700, 1987

    work page 1987

  11. [11]

    Least-squares estimation of transformation parameters between two point patterns,

    S. Umeyama, “Least-squares estimation of transformation parameters between two point patterns,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 4, pp. 376–380, 2002

    work page 2002

  12. [12]

    Carrier-phase-based initial heading alignment for land vehicular mems gnss/ins naviga- tion system,

    T. Zhang, S. Liu, Q. Chen, X. Feng, and X. Niu, “Carrier-phase-based initial heading alignment for land vehicular mems gnss/ins naviga- tion system,”IEEE Transactions on Instrumentation and Measurement, vol. 71, pp. 1–13, 2022

    work page 2022

  13. [13]

    Carrier doppler-based initial alignment for mems imu/gnss integrated system under low satellite visibility,

    Y . Wei, H. Li, and M. Lu, “Carrier doppler-based initial alignment for mems imu/gnss integrated system under low satellite visibility,”GPS Solutions, vol. 25, no. 3, p. 90, 2021

    work page 2021

  14. [14]

    Gvins: Tightly coupled gnss–visual–inertial fusion for smooth and consistent state estimation,

    S. Cao, X. Lu, and S. Shen, “Gvins: Tightly coupled gnss–visual–inertial fusion for smooth and consistent state estimation,”IEEE Transactions on Robotics, vol. 38, no. 4, pp. 2004–2021, 2022

    work page 2004

  15. [15]

    P 3- lins: Tightly coupled ppp-gnss/ins/lidar navigation system with effective initialization,

    T. Li, L. Pei, Y . Xiang, X. Zuo, W. Yu, and T.-K. Truong, “P 3- lins: Tightly coupled ppp-gnss/ins/lidar navigation system with effective initialization,”IEEE Transactions on Instrumentation and Measurement, vol. 72, pp. 1–13, 2023

    work page 2023

  16. [16]

    On the tightness of semidefinite relaxations for rotation estimation,

    L. Brynte, V . Larsson, J. P. Iglesias, C. Olsson, and F. Kahl, “On the tightness of semidefinite relaxations for rotation estimation,”Journal of Mathematical Imaging and Vision, vol. 64, no. 1, pp. 57–67, 2022

    work page 2022

  17. [17]

    S. P. Boyd and L. Vandenberghe,Convex Optimization. Cambridge University Press, 2004

    work page 2004

  18. [18]

    Se- sync: A certifiably correct algorithm for synchronization over the special euclidean group,

    D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard, “Se- sync: A certifiably correct algorithm for synchronization over the special euclidean group,”The International Journal of Robotics Research, vol. 38, no. 2-3, pp. 95–125, 2019

    work page 2019

  19. [19]

    Doppler frequency shift based source localization in presence of sensor location errors,

    L. Deng, P. Wei, Z. Zhang, and H. Zhang, “Doppler frequency shift based source localization in presence of sensor location errors,”IEEE Access, vol. 6, pp. 59 752–59 760, 2018

    work page 2018

  20. [20]

    Teaser: Fast and certifiable point cloud registration,

    H. Yang, J. Shi, and L. Carlone, “Teaser: Fast and certifiable point cloud registration,”IEEE Transactions on Robotics, vol. 37, no. 2, pp. 314– 333, 2020

    work page 2020

  21. [21]

    Certifiably globally optimal extrinsic calibration from per-sensor egomotion,

    M. Giamou, Z. Ma, V . Peretroukhin, and J. Kelly, “Certifiably globally optimal extrinsic calibration from per-sensor egomotion,”IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 367–374, 2019

    work page 2019

  22. [22]

    Resync: Riemannian subgradient-based robust rotation synchronization,

    H. Liu, X. Li, and A. M.-C. So, “Resync: Riemannian subgradient-based robust rotation synchronization,” inAdvances in Neural Information Processing Systems, vol. 36, 2023, pp. 5236–5261

    work page 2023

  23. [23]

    Robust multiple sensor localization via semidefinite relaxation in wireless sensor networks with anchor position uncertainty,

    Y . Yan, G. Yang, H. Wang, and X. Shen, “Robust multiple sensor localization via semidefinite relaxation in wireless sensor networks with anchor position uncertainty,”Measurement, vol. 196, p. 111193, 2022

    work page 2022

  24. [24]

    Oasis: Optimal ar- rangements for sensing in slam,

    P. Kaveti, M. Giamou, H. Singh, and D. M. Rosen, “Oasis: Optimal ar- rangements for sensing in slam,” in2024 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2024, pp. 13 818–13 824

    work page 2024

  25. [25]

    Certifiably optimal satellite orbit determination based on doppler measurements for low-earth-orbit satel- lites,

    B. Song, W. Wen, and L.-T. Hsu, “Certifiably optimal satellite orbit determination based on doppler measurements for low-earth-orbit satel- lites,” in2025 IEEE/ION Position, Location and Navigation Symposium (PLANS), 2025, pp. 410–416

    work page 2025

  26. [26]

    Certifiably optimal doppler positioning using opportunistic leo satellites,

    B. Song, W. Wen, Q. Zhang, B. Xu, and L.-T. Hsu, “Certifiably optimal doppler positioning using opportunistic leo satellites,”arXiv preprint arXiv:2509.17198, 2025

    work page arXiv 2025

  27. [27]

    On-manifold preintegration for real-time visual–inertial odometry,

    C. Forster, L. Carlone, F. Dellaert, and D. Scaramuzza, “On-manifold preintegration for real-time visual–inertial odometry,”IEEE Transactions on Robotics, vol. 33, no. 1, pp. 1–21, 2016

    work page 2016

  28. [28]

    Advancing high-precision navigation: Lever- aging homogeneous sensors in tightly coupled ppp-rtk/imu integration,

    Z. Shen, X. Li, and X. Li, “Advancing high-precision navigation: Lever- aging homogeneous sensors in tightly coupled ppp-rtk/imu integration,” IEEE Transactions on Industrial Electronics, vol. 71, no. 11, pp. 15 100– 15 110, 2024

    work page 2024

  29. [29]

    A high-precision vehicle navigation system based on tightly coupled ppp-rtk/ins/odometer integration,

    X. Li, Z. Qin, Z. Shen, X. Li, Y . Zhou, and B. Song, “A high-precision vehicle navigation system based on tightly coupled ppp-rtk/ins/odometer integration,”IEEE Transactions on Intelligent Transportation Systems, vol. 24, no. 2, pp. 1855–1866, 2022

    work page 2022

  30. [30]

    Instantaneous velocity determination and positioning using doppler shift from a leo constellation,

    F. Guo, Y . Yang, F. Ma, Y . Zhu, H. Liu, and X. Zhang, “Instantaneous velocity determination and positioning using doppler shift from a leo constellation,”Satellite Navigation, vol. 4, no. 1, p. 9, 2023

    work page 2023

  31. [31]

    Convex global 3d registration with lagrangian duality,

    J. Briales and J. Gonzalez-Jimenez, “Convex global 3d registration with lagrangian duality,” inProceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 4960–4969

    work page 2017

  32. [32]

    On the local stability of semidefinite relaxations,

    D. Cifuentes, S. Agarwal, P. A. Parrilo, and R. R. Thomas, “On the local stability of semidefinite relaxations,”Mathematical Programming, vol. 193, no. 2, pp. 629–663, 2022

    work page 2022

  33. [33]

    Toward globally optimal state estimation using automatically tightened semidefinite re- laxations,

    F. D ¨umbgen, C. Holmes, B. Agro, and T. Barfoot, “Toward globally optimal state estimation using automatically tightened semidefinite re- laxations,”IEEE Transactions on Robotics, vol. 40, pp. 4338–4358, 2024

    work page 2024

  34. [34]

    Observability- aware intrinsic and extrinsic calibration of lidar-imu systems,

    J. Lv, X. Zuo, K. Hu, J. Xu, G. Huang, and Y . Liu, “Observability- aware intrinsic and extrinsic calibration of lidar-imu systems,”IEEE Transactions on Robotics, vol. 38, no. 6, pp. 3734–3753, 2022

    work page 2022

  35. [35]

    The problem of comparable gnss results–an approach for a uniform dataset with low-cost and reference data,

    P. Reisdorf, T. Pfeifer, J. Breßler, S. Bauer, P. Weissig, S. Lange, G. Wanielik, and P. Protzel, “The problem of comparable gnss results–an approach for a uniform dataset with low-cost and reference data,” in Proceedings of the International Conference on Advances in V ehicular Systems, Technologies and Applications (VEHICULAR), 2016

    work page 2016