PaperlayerView exact revision on arXiv

Source-linked AI summary

Advances in Global Solvers for 3D Vision

Zhenjun Zhao, Heng Yang, Bangyan Liao, Yingping Zeng, Shaocheng Yan, Yingdong Gu, Peidong Liu, Yi Zhou, Haoang Li, Javier Civera

arXiv:2602.14662v1cs.CVcs.RO

TL;DR

Geometric vision problems are often nonconvex, making local methods sensitive to initialization, while the field lacks a consolidated survey of global solvers. This survey organizes three solver paradigms across ten tasks and finds that solver selection involves trade-offs among guarantees, robustness, and scalability.

  • Problem

    The field lacks a consolidated survey of global solvers for 3D vision, limiting researchers’ ability to navigate and advance it.

    Source: §1 · p. 2

  • Method

    The survey synthesizes foundations, algorithmic designs, and practical enhancements for BnB, CR, and GNC, comparing them across ten geometric vision tasks.

    Source: §7 · p. 12, §10 · p. 27

  • Results

    The survey reports a trade-off: BnB and convex relaxation provide global guarantees at significant computational cost, whereas GNC is computationally efficient but lacks optimality guarantees.

    Source: §5 · p. 10, §10 · p. 27

  • Takeaways & Limitations

    Global solver selection in 3D vision is governed by trade-offs among optimality guarantees, robustness, and scalability.

    Source: §10 · p. 27

    Scaling BnB and convex relaxation while preserving guarantees remains a challenge because their computational complexity can become prohibitive on large-scale problems.

    Source: §8.1 · p. 25

Abstract

from arXiv · show

Global solvers have emerged as a powerful paradigm for 3D vision, offering certifiable solutions to nonconvex geometric optimization problems traditionally addressed by local or heuristic methods. This survey presents the first systematic review of global solvers in geometric vision, unifying the field through a comprehensive taxonomy of three core paradigms: Branch-and-Bound (BnB), Convex Relaxation (CR), and Graduated Non-Convexity (GNC). We present their theoretical foundations, algorithmic designs, and practical enhancements for robustness and scalability, examining how each addresses the fundamental nonconvexity of geometric estimation problems. Our analysis spans ten core vision tasks, from Wahba problem to bundle adjustment, revealing the optimality-robustness-scalability trade-offs that govern solver selection. We identify critical future directions: scaling algorithms while maintaining guarantees, integrating data-driven priors with certifiable optimization, establishing standardized benchmarks, and addressing societal implications for safety-critical deployment. By consolidating theoretical foundations, practical advances, and broader impacts, this survey provides a unified perspective and roadmap toward certifiable, trustworthy perception for real-world applications. A continuously-updated literature summary and companion code tutorials are available at https://github.com/ericzzj1989/Awesome-Global-Solvers-for-3D-Vision.

1 INTRODUCTION

Geometric vision problems are often nonlinear and nonconvex, making local methods sensitive to initialization and robust estimation harder. This survey offers a unified account of global solvers, their trade-offs, applications, and open challenges.

Introduction

  • BnB partitions and prunes the solution space for global guarantees; CR uses convex surrogates for tractable solutions and bounds; GNC follows a homotopy path toward near-global solutions in practice.The three paradigms address the nonconvexity of geometric estimation through distinct strategies.Source: §1 · p. 1
  • The survey presents the first systematic review dedicated to global solvers for 3D vision, unifying the field through BnB, CR, and GNC and reviewing their theory and practical variants.It addresses the lack of a consolidated perspective covering method families, trade-offs, diverse tasks, and future directions.Source: §1 · pp. 1–2
  • The survey compares optimality guarantees, computational complexity and scalability, outlier robustness, and deployment considerations, and examines applications across ten core 3D vision tasks.Tasks include pose estimation, 3D registration, averaging, triangulation, pose graph optimization, and bundle adjustment.Source: §1 · pp. 1–3
  • The survey highlights open challenges and future research directions that bridge theory and practice, and provides a continuously updated repository of literature, implementation pointers, and tutorial code.The tutorials demonstrate convex-relaxation formulations using SPOT in Python,.Source: §1 · p. 3
  • Its scope covers optimization-based global and continuation solvers, robustness and scalability enhancements, and applications; sampling-based methods such as RANSAC – are excluded.The survey focuses on methods that certify global optimality or often achieve near-global solutions in practice; sampling methods are outside scope because they are not optimization-based and have been surveyed elsewhere,.Source: §1 · p. 3

2 BACKGROUND AND PROBLEM FORMULATION

The section establishes notation and canonical geometric estimation formulations, then explains their sources of nonconvexity and the robust-estimation strategies used for noisy or outlier-contaminated measurements.

2.1 Notation and Conventions

  • Standard notation covers scalars, vectors, matrices, indexed entries and submatrices, inner products, vectorization, Kronecker products, and concatenation.It also defines [v]× for the skew-symmetric matrix associated with v ∈ R^3.Source: §2.1 · p. 3
  • The section defines PSD and PD matrices, unit spheres, SO(d), camera calibration matrices, and polynomial notation, including SOS representations that guarantee nonnegativity.A polynomial q(x) is SOS when q(x) = [x]_F^T Q [x]_F for some Q ⪰ 0; the polynomial notation follows.Source: §2.1 · p. 4

2.2 Geometric Problem Formulation and Structure

  • Many geometric estimation tasks fit a nonlinear least-squares template in which residuals quantify disagreement between model parameters and measurements.Examples include reprojection errors in absolute pose, triangulation, and bundle adjustment; epipolar error in relative pose; alignment error in Wahba and point-set registration; and distance-based costs in vanishing point estimation and rotation/translation averaging.Source: §2.2 · p. 4
  • Nonconvexity arises from both feasible-set structure—including rotations, unit-norm, low-rank or bilinear, and discrete constraints—and nonlinear residual models.Examples of nonlinear residuals include perspective projection in absolute pose and bundle adjustment, and angular distances in rotation averaging.Source: §2.2 · p. 4

2.3 Robust Estimation

  • Consensus maximization, seeks parameters that maximize the number of measurements within a predefined error threshold, but its formulation is combinatorial and NP-hard.The inlier-set criterion uses an indicator for whether each measurement satisfies the threshold.Source: §2.3 · p. 4
  • M-estimation, limits large-residual influence by replacing least squares with a subquadratic-growth robust function; its continuous optimization remains globally challenging.Typical choices include Huber, Cauchy, Geman–McClure, and truncated least squares; nonconvexity arises in both the robust cost and feasible set.Source: §2.3 · p. 4

3 GLOBAL SOLVER 1: BRANCH-AND-BOUND (BNB)

BnB achieves deterministic, certifiable global optimization through exhaustive partitioning and pruning, while bound quality and parameter-space dimension govern its practical efficiency.

Theoretical properties

  • BnB,, deterministically partitions, bounds, and prunes nonconvex search regions, yielding ε-certified global optima under valid bounds and sufficient refinement, unlike probabilistic RANSAC.Pruning is safe because regions whose lower bound exceeds the best feasible objective cannot contain the true minimizer; termination provides an a posteriori certificate when the bound gap falls below a threshold.Source: §3 · pp. 4–5

Modeling and solution ingredients

  • Search design combines parameterization choices such as angle-axis and translation boxes,, bounding methods –, and branching and node-selection policies –.Tighter bounds improve pruning; branching may use uniform bisection, adaptive splitting, or problem-specific heuristics, while node selection may be best-first, depth-first, or hybrid.Source: §3 · pp. 4–5

Computational complexity

  • Worst-case search grows exponentially with parameter dimension and tighter tolerance, while tight bounds and low intrinsic dimensionality or smoothness can enable aggressive pruning in practice.For a d-dimensional domain of diameter D, the number of explored subregions can grow as O((D/δ)^d), with δ ∼ ε.Source: §3 · p. 5

Robust estimation via consensus maximization

  • For outlier-robust consensus maximization, interval residual bounds provide per-region upper inlier-count bounds, while feasible-point counts provide lower bounds for pruning,.Efficient bounding and adaptive subdivision support globally optimal inlier-set identification for moderate-scale problems.Source: §3 · p. 5

Hybrid frameworks

  • Hybrid solvers use coarse low-dimensional BnB initialization or alternate local optimization with BnB, tightening bounds while improving scalability but potentially sacrificing strict optimality,,, [63].Coarse rotation-only search can initialize nonlinear least-squares refinement; alternation updates the upper bound locally and refines the lower bound through BnB.Source: §3 · p. 5

Strengths and limitations

  • Problem-specific bound construction limits plug-and-play use, and consensus problems with outlier ratios above 50% can produce large search trees requiring adaptive or hybrid strategies.Local refinement or coarse initialization in hybrid designs may partially sacrifice strict optimality guarantees.Source: §3 · p. 6

4 GLOBAL SOLVER 2: CONVEX RELAXATION (CR)

Convex relaxation replaces nonconvex constraints with tractable convex surrogates, enabling globally optimal solutions or provable suboptimality bounds. Its main frameworks are Shor’s relaxation for QCQPs, Moment-SOS for polynomial optimization, and specialized relaxations that exploit problem structure.

4.1 Shor’s Relaxation

  • Shor’s relaxation lifts QCQPs to SDPs by dropping a rank-one constraint; tight solutions are certifiable, while higher-rank solutions need rounding and refinement.Standard SDP interior-point methods scale as O(n^3.5) for typical 3D vision problems, limiting applicability to moderate sizes; structure-exploiting methods can improve scalability but may weaken guarantees.Source: §4.1 · pp. 6–7

4.2 Moment-SOS Relaxation

  • Moment-SOS,, converts polynomial nonnegativity into SOS-based SDPs whose hierarchy converges monotonically to the global optimum, often with tightness at orders d = 2–4.The moment matrix grows combinatorially with problem dimension and order; for n = 10, d = 4, r = 1001 and p = 43,758, with O(r^3.5) IPM complexity and O(r^2) memory.Source: §4.2 · pp. 7–8

4.3 Other Relaxation Techniques

  • Specialized relaxations use quasi-convex, SOCP/QP/LP, or convex-hull formulations for targeted problems, scaling substantially better while retaining guarantees under suitable conditions.Quasi-convex L∞ formulations can be solved by bisection; problem specificity and violated structural assumptions can reduce approximation quality.Source: §4.3 · p. 9

5 GLOBAL SOLVER 3: GRADUATED NONCONVEXITY (GNC)

GNC, – is a deterministic continuation framework that transforms nonconvex geometric estimation into progressively harder surrogate problems, offering practical robust estimation without a priori global optimality guarantees.

Modeling and solution ingredients

  • GNC lowers µ to deform a convex or nearly convex surrogate toward the target nonconvex objective, warm-starting successive IRLS problems that progressively down-weight large residuals.Figure 5 illustrates the loss transition and the solution path tracked through increasingly challenging landscapes.Source: §5 · pp. 9–10, Figure 5 · p. 10

Theoretical properties

  • Under smoothness and local-convexity assumptions, each IRLS subproblem reaches a local minimum and continuation reaches a stationary point; near-global convergence is empirical, not certified.Near-global minima are especially common in low-noise regimes or when outliers are well-separated.Source: §5 · p. 10

Strengths and limitations

  • GNC reliably suppresses 30–50% outliers deterministically, but can fail above 50%, with adversarial outliers, or under overly rapid cooling, and offers no optimality certificate.Performance also depends on initialization and schedule tuning; adaptive variants can reduce that sensitivity.Source: §5 · pp. 10–11

Computational complexity

  • Each IRLS iteration costs O(Nn^2) with Gauss-Newton or O(Nn+n^3) with direct factorization; geometric cooling typically takes O(log(1/µmin)) steps.The cost scales linearly with the number of measurements.Source: §5 · p. 10

Variants and extensions

  • Variants include GNC-GM for smooth homotopy, GNC-TLS, for sharper rejection, adaptive annealing,, GNC-MinT, and hybrids with convex relaxations,.GNC-MinT uses residual-distribution analysis for termination without a prior inlier threshold.Source: §5 · pp. 10–11

6 COMPARATIVE ANALYSIS

The solver families trade off optimality guarantees, computational efficiency, scalability, and outlier robustness. Their relative strengths guide method selection across application scenarios.

6.1 Global Optimality Guarantees

  • BnB guarantees global optimality with certificates upon convergence but has exponential worst-case complexity; convex relaxations certify solutions when tight, while GNC offers no a priori guarantees.Moment-SOS can strengthen guarantees through hierarchical refinement at increased computational cost; GNC often achieves near-global solutions empirically under favorable conditions.Source: §6.1 · p. 11

6.2 Computational Complexity and Scalability

  • GNC scales best at O(Kn^2) per iteration; BnB is typically limited to fewer than 20 measurements, while Shor’s relaxation handles hundreds at O(n^3.5) per SDP solve.Specialized SOCP, QP, LP, and convex-hull relaxations can handle thousands of measurements; Moment-SOS is typically effective below 100 measurements at low orders.Source: §6.2 · p. 11

6.3 Robustness to Outliers

  • GNC handles 30–50% outlier ratios through progressive down-weighting without explicit classification, while BnB and convex relaxations require discrete search or explicit robust modeling.Specialized relaxations typically have limited outlier handling, though some variants use robust formulations.Source: §6.3 · pp. 11–12

6.4 Method Selection and Deployment

  • Choose BnB or tight convex relaxations for small problems needing certification, Shor’s relaxation for medium-scale problems, and GNC or specialized relaxations for large or time-critical applications.Hybrid approaches can use GNC for initialization followed by convex relaxation for certification when needed.Source: §6.4 · p. 12

7 TASKS AND APPLICATIONS · 7.1 Wahba Problem · 7.2 Vanishing Point Estimation

Global solvers address task-specific nonconvexity in 3D vision, with performance shaped by geometric structure and outliers. The survey compares tasks by optimality, robustness, and scalability, then examines Wahba rotation estimation and vanishing-point estimation.

7 TASKS AND APPLICATIONS

  • The survey compares global solvers across geometric tasks by certifiability, tolerance to noise and outliers, and scalability, emphasizing that task structure changes solver performance.Its task-by-task template covers problem formulations, local and closed-form methods, BnB, relaxations, and GNC.Source: §7 · p. 12

7.1 Wahba Problem

  • Without outliers, Wahba estimation has an exact, globally optimal SVD solution, while local iterative methods may stall and least squares is sensitive to outliers.The optimal rotation is R* = U diag(1, 1, det(UV^T)) V^T for M = USV^T; variants adapt SVD-based solutions to other costs and constraints.Source: §7.1 · p. 13
  • Wahba BnB partitions rotation space with admissible bounds; GORE prunes provable non-inliers while preserving maximum-consensus inliers for faster global search.BnB variants use L∞-based SOCP feasibility, consensus maximization, and stereographic bounds; some registration formulations assume known translation. GORE accelerates subsequent methods such as BnB, while Peng et al. improve noisy rotation search through approximate consensus maximization.Source: §7.1 · pp. 13, 15
  • Wahba SDP and convex relaxations offer certifiable recovery, including QUASAR under substantial outlier contamination and LMI exact recovery under mild assumptions [140].Other results establish tightness or recovery conditions dependent on noise and outlier distribution, [138], analyze anisotropic sensor noise, and provide exact convex-hull SDP descriptions or conditional global guarantees for FracGM.Source: §7.1 · pp. 13, 15

7.2 Vanishing Point Estimation

  • Vanishing-point estimation is nonconvex on the projective plane and combinatorial with multiple points; heuristic voting, RANSAC, least squares, and EM lack global guarantees or risk local minima.The task estimates vanishing points from image-line families and supports applications including SLAM, calibration, single-view geometry, and scene understanding.Source: §7.2 · p. 15
  • For Manhattan-world vanishing points, BnB methods maximize consensus with interval analysis or tighter EGI bounds,, while hybrid RANSAC–BnB methods seek quasi-global or certifiable accuracy,.The Manhattan assumption specifies three orthogonal dominant directions; the EGI approach reports robust near-real-time performance.Source: §7.2 · p. 15
  • Atlanta-world methods extend BnB to multiple vertical directions,,,, while GlobustVP provides certifiable SDP-based Manhattan-world estimation robust to outliers.Atlanta methods use improved EGI bounds, mine-and-stab, or hemisphere search with tight bounds; GlobustVP relaxes a nonconvex QCQP using truncated multi-selection error and soft line–vanishing-point association.Source: §7.2 · pp. 15–16

7.3 Absolute Pose Estimation · 7.4 Relative Pose Estimation

The sections survey global approaches to nonconvex absolute and relative pose estimation, including Branch-and-Bound and convex relaxations; the absolute-pose section also describes robust Graduated Non-Convexity methods. They relate solver designs to pose constraints, outliers, and reduced search spaces.

7.3 Absolute Pose Estimation

  • For absolute pose, EPnP, and DLS provide analytical PnP solutions, while SDP, SOS, and QCQP methods offer convex relaxations and optimality certification.DLS finds stationary points from polynomial KKT equations; PnP relaxations include CvxPnPL, moment-SOS methods, SQPnP, ACEPnP, and a Lagrangian-duality certifier.Source: §7.3 · pp. 16–17
  • Absolute-pose BnB ranges from robust PnP with outlier rejection to correspondence-free 2D-3D registration, and reduced-dimensional searches –.Methods use geometric bounds, rotation-invariant features, known gravity, or rotation-translation decomposition; line-based variants also decouple orientation and translation,.Source: §7.3 · p. 16
  • For robust PnP, GNC-SPnPL uses Geman–McClure reweighting, while GNCPnP applies the TLS cost to improve resilience to severe outliers.Both methods use Black–Rangarajan duality.Source: §7.3 · p. 17

7.4 Relative Pose Estimation

  • Relative pose estimation uses the fundamental matrix when cameras are uncalibrated and the essential matrix when calibrated; pose recovery has projective or cheirality ambiguity, respectively.Relative pose estimation supports SfM, visual localization, and SLAM.Source: §7.4 · p. 17
  • For relative pose, the 8-point algorithm [22],, estimates a rank-2 fundamental matrix, while the 5-point algorithm [352] yields up to 10 essential-matrix candidates.Subsequent work improves polynomial formulations and numerical stability, or adds scene-structure and motion-prior constraints –.Source: §7.4 · pp. 17–18
  • Relative-pose BnB spans rotation search and robust essential-matrix estimation,, as well as unknown-intrinsics, correspondence-free, and motion-constrained problems, –.Approaches branch over rotation or a minimal essential-matrix manifold, and exploit known orientation, gravity, planar motion, or reduced-DoF camera configurations.Source: §7.4 · p. 18
  • Relative-pose convex methods include SDP certifiers,, moment-SOS relaxations, –, and globally optimal SOCP for multi-camera visual odometry.Other work uses duality-based certification,,,, factorization and Riemannian staircases, and SOS refinements with line correspondences,.Source: §7.4 · pp. 18–19

7.5 3D Registration

3D registration estimates a rigid transformation from point correspondences, but its nonconvexity and outliers motivate global solvers. The section surveys BnB, convex relaxations, and GNC, including decompositions and acceleration strategies for robust, certifiable estimation.

Properties and local methods

  • ICP is efficient but sensitive to initialization, partial overlap, and outliers, while SVD alignment is globally optimal only when correspondences are correct.The SO(3) constraint makes registration nonlinear and nonconvex; ICP variants [366], can converge to local minima, whereas closed-form methods,, rely on correspondence quality.Source: §7.5 · p. 19

Branch-and-Bound (BnB)

  • Go-ICP, globally optimizes ICP’s L2 error with nested BnB over SE(3), while related methods extend global search to varied correspondences and Gaussian-mixture alignment.Olsson et al., use convex underestimators; Li and Hartley address rotation-only registration; Campbell and Petersson extend the framework as GOGMA.Source: §7.5 · p. 19

Alternative problem formulations

  • Alternative formulations use assignment, distribution, polynomial, and graph structures to globally estimate correspondences and transformations,,,,, [206].These include rectangular BnB for concave quadratic assignment, SOS optimization for inlier maximization, graph vertex cover, and maximum-clique search.Source: §7.5 · p. 19

Decomposition strategies

  • Decomposition methods reduce 6-DoF registration to lower-dimensional BnB searches, including sequential rotation and translation, 4-DoF LiDAR variants, and two-stage axis-angle search, [204],,,, [216].Li et al. [204] also introduce 3D Integral Volume for faster bound evaluation; GMOR [216] uses Chasles’ theorem [370], interval stabbing, and range maximum query to deterministically maximize inlier overlap under high outlier ratios.Source: §7.5 · p. 19

Row-vector and constrained formulations

  • Row-vector, Atlanta-world, and symmetry-plane formulations further reduce BnB search complexity or improve robustness under low overlap,,,.TEAR combines spherical-space BnB and interval stabbing with inter-row orthogonality constraints.Source: §7.5 · p. 19

Acceleration and efficiency improvements

  • Acceleration methods tighten bounds or reduce computation through compatibility graphs, Chebyshev surrogates, convex relaxations, and interval analysis,, [53].Robust preprocessing extends rotation-only outlier removal to 6DoF registration using interval stabbing, while QGORE computes tight upper bounds in quadratic time and preserves robustness and optimality.Source: §7.5 · pp. 19–20

Shor’s relaxation

  • SDP and Lagrangian-duality relaxations enforce rotation constraints and provide global-optimality certificates across point-to-point, point-to-line, point-to-plane, and multi-cloud registration,,,.TEASER, separates rotation, translation, and scale, using TLS with maximum-clique pruning, SDP rotation, and adaptive voting; TEASER++ [85] replaces SDP rotation with GNC for greater efficiency while maintaining robustness, and both can verify candidates via DRS, –.Source: §7.5 · p. 20

Graduated non-convexity (GNC)

  • GNC within IRLS improves convergence and robustness under heavy contamination, with theoretical convergence analysis.GlobalPointer alternates between two SDP subproblems, while Ahmed and Chaudhury use tailored nonconvex ADMM for an SDP with explicit rank constraints.Source: §7.5 · p. 20

7.6 Rotation Averaging

Rotation averaging estimates absolute camera orientations from noisy relative rotations, up to a global gauge, by minimizing edge discrepancies on SO(3). The section surveys nonconvex local methods and convex relaxations that pursue global guarantees with different scalability limits.

Problem definition

  • Rotation averaging estimates absolute camera orientations up to a global gauge by minimizing edge-wise discrepancies between measured and estimated relative rotations.Discrepancies can use geodesic, chordal, axis-angle, or quaternion distances with a p-norm.Source: §7.6 · p. 20

Properties and local methods

  • Manifold constraints and graph coupling make rotation averaging highly nonconvex; local iterative methods are efficient but noise-sensitive and lack global correctness guarantees.Classical approaches include IRLS, Weiszfeld-type procedures, and related methods on SO(3); they typically project estimates back onto SO(3).Source: §7.6 · p. 20

Shor’s relaxation

  • Shor SDP relaxations lift rotations to a block-orthonormal matrix variable and have yielded exact-recovery and tightness guarantees under stated conditions.Singer gives guarantees under bounded noise; Bandeira et al. show tightness under relatively high noise, while Zhong and Boumal analyze 2D tightness.Source: §7.6 · p. 20
  • Removing the determinant constraint extends the angle range to approximately 42.9°; dual-specialized block-coordinate descent is 1–2 orders of magnitude faster than standard SDP solvers such as SeDuMi.Rotation-coordinate descent retains dual certificates when strong duality holds. Shonan Rotation Averaging combines semidefinite relaxations with local optimization and adaptive dimension lifting to provide global-optimality certificates; anisotropic chordal relaxations [236] can certify global optima under directionally varying measurement uncertainties.Source: §7.6 · p. 21

Moment-SOS relaxation

  • Moment-SOS relaxations exploit the polynomial constraints to certify optimal solutions on small- to medium-scale instances, but growing moment matrices limit large-scale use.Ke et al. solve single rotation averaging optimally with low-order Lasserre relaxations on modest problem sizes.Source: §7.6 · p. 21

Other relaxations

  • Alternative convex formulations include geodesic weak convexity, LUD’s SDP, convex-hull relaxations, and DESC, which can exactly recover ground-truth structure under favorable conditions.LUD is solvable using ADM; DESC formulates robust rotation averaging as a cycle-consistency quadratic program.Source: §7.6 · p. 21

7.7 Translation Averaging · 7.8 Triangulation

Translation averaging and triangulation are nonconvex geometric estimation problems; the sections survey convex relaxations and global methods alongside local or analytical approaches.

7.7 Translation Averaging

  • Translation averaging estimates camera positions from noisy pairwise directions, up to global translation and scale, but normalization, gauge ambiguities, outliers, and degeneracies make it nonconvex and challenging,,,.Linear least-squares methods are efficient but can accumulate drift and lack global consistency guarantees.Source: §7.7 · p. 21
  • Ozyesil et al. give translation averaging its first certifiably correct formulation using an SDP relaxation, parallel rigidity guarantees for exact recovery, and an augmented Lagrangian dual algorithm for scale.The algorithm is designed to scale the SDP solver to large camera networks.Source: §7.7 · p. 21
  • Alternative translation-averaging relaxations include quasi-convex L∞ SOCP, faster LP, outlier-resilient LUD, scalable ShapeFit, and baseline-insensitive angular-error optimization.The LUD formulation uses iterative QP approximations; ShapeFit uses ADMM, while the angular-error formulation uses an explicit normalization variable and BCD.Source: §7.7 · p. 21
  • For known rotations, camera translations and 3D structure can be estimated separately; methods include pseudoconvex reprojection optimization, SOCP acceleration and decomposition, and robust L1 or residual-trimming formulations,,,,,,,,,, [245],.Li decomposes large L∞ problems into finite primitive subproblems solvable analytically or in closed form.Source: §7.7 · p. 22

7.8 Triangulation

  • Triangulation is nonconvex and ill-conditioned in near-degenerate views; local methods can depend on initialization, while DLT, two-view polynomial solutions, and three-view Gröbner solvers offer analytical alternatives,,,,,, –.The two-view L2 polynomial method minimizes geometric reprojection error; the cited angular-error methods provide closed-form optimal two-view solutions.Source: §7.8 · p. 22
  • SDP relaxations formulate triangulation as QCQPs and provide global-optimality certificates; extensions include low-noise exact recovery and TLS costs for high noise and outliers,,,.The formulations use graph rigidity, epipolar or fractional reprojection constraints, and larger SDP relaxations for rank-deficient matrix problems.Source: §7.8 · p. 22
  • Other globally optimal triangulation approaches include quasi-convex L∞ LP or SOCP, outlier-handling LP, panoramic-camera frameworks, optimal inlier selection, and certifiable QCQP approximation,,,,,,,,.The QCQP approximation uses linear constraints and can be solved by COD or SVD, with optimality certified via the dual-problem Lagrangian Hessian.Source: §7.8 · pp. 22–23

7.9 Pose Graph Optimization · 7.10 Bundle Adjustment

Pose graph optimization has a broad range of certifiable convex and synchronization-based methods, while bundle adjustment remains difficult to globalize because of its extreme scale and nonconvexity. Recent BA work combines scalable SDP relaxations with initialization-free alternatives.

7.9 Pose Graph Optimization

  • Shor-based dual SDPs provide PGO optimality certificates, with exactness conditions and smaller verification formulations; dual initialization can also help when relaxations are not tight,,,,.Complex-domain PGO relaxations characterize tightness through the Single Zero Eigenvalue Property, while CPL-Sync combines SDP and Riemannian optimization with low-noise tightness guarantees [264],,.Source: §7.9 · p. 23
  • SE-Sync, uses a Riemannian Staircase to certify global PGO optima at speeds comparable to local methods, and later synchronization methods extend the framework to Cartan motion and similarity groups,.SE-Sync’s rotation relaxation permits exact recovery when measurement noise is not too large; SIM-Sync also incorporates learned depth priors.Source: §7.9 · p. 23
  • Robust PGO relaxations preserve global optimality with unsquared deviation, absolute deviation, and Huber costs, while TLS addresses perceptual aliasing and correlated outliers in SLAM.Source: §7.9 · p. 23
  • Certifiable SLAM extends PGO through SDP/QCQP and range-aided methods; DC2-PGO and DCORA [276] distribute certified solving across multi-robot systems.Landmark-based and range-aided formulations provide certificates, while distributed methods combine sparse relaxations with Riemannian optimization.Source: §7.9 · p. 23
  • Other PGO relaxations include sparse SOS methods reaching global minima, convex-hull SDP relaxations, and SCORE’s certifiable SOCP initializer for range-aided SLAM [113].Source: §7.9 · pp. 23–24

7.10 Bundle Adjustment

  • BA jointly refines cameras and scene points but is highly nonconvex and enormous; sparsity-based Gauss-Newton or Levenberg–Marquardt systems scale well yet remain vulnerable to poor initialization and outliers.Global BA methods remain relatively rare because certifiable large-scale nonconvex optimization is computationally challenging.Source: §7.10 · p. 24
  • Scaled BA can use convex SDP relaxations with Burer–Monteiro factorization and CUDA-based Riemannian optimization to achieve certifiable global optimality at large scales while incorporating learned depth priors.Source: §7.10 · p. 24
  • Initialization-free BA methods use variable projection and surrogate objectives, including pOSE and expOSE, to enable global minima from arbitrary or random initializations,,,, [282].These approaches analytically eliminate structure variables, preserve bilinear residual factorization or approximate exponential regularization, and can incorporate rotation averaging.Source: §7.10 · p. 24

8 OPEN CHALLENGES AND FUTURE DIRECTIONS

The section identifies scalability with guarantees, integration of deep learning with certifiable optimization, and standardized evaluation as priorities for advancing global solvers toward practical vision systems.

8.1 Scalability and Algorithmic Advances

  • Scaling global solvers while preserving guarantees and robustness remains a central challenge, with distinct acceleration strategies proposed for BnB, convex relaxation, and GNC.Suggestions include tighter bounds, adaptive branching, and decomposition for BnB; block-coordinate, distributed, and hardware-accelerated methods for convex relaxation; and lightweight certifiers for GNC-style solvers. Outlier-robust relaxations remain difficult to scale, while quantum-inspired and neuromorphic approaches are still open challenges.Source: §8.1 · p. 25
  • Convex relaxations face a tightness–tractability trade-off, motivating problem-specific constraints and adaptive hierarchies that refine critical solution-space regions.Proposed tightening strategies include algebraic invariants, low-rank structure, sparsity, and redundant constraints [71],,,, [427], [432],, [448], [79],,,.Source: §8.1 · p. 25

8.2 Integration with Deep Learning

  • Deep learning can guide global solvers, while certifiable constraints and differentiable relaxations may help address learned predictions’ geometric inconsistency and lack of optimality certificates.Learned priors can guide BnB pruning, CR formulations, and GNC schedules; relaxations can verify warm starts, [439]. Embedding constraints in models or using convex relaxations as differentiable layers are proposed integration paths,,.Source: §8.2 · p. 25

8.3 Standardized Benchmarks and Evaluation

  • Evaluation should use realistic, diverse benchmarks and measure certification, efficiency, robustness, and resource demands beyond solution quality.The proposed benchmarks span pose estimation, registration, SLAM, and SfM, with controlled synthetic and real-world data across noise levels, outlier ratios, and problem scales,. Common data formats, reference implementations, and evaluation infrastructure support reproducibility.Source: §8.3 · pp. 25–26
  • Coordinated progress on scalability, learning integration, and rigorous evaluation is presented as a route to robust, certifiable systems for safety-critical applications including autonomous driving, surgical robotics, and aerial navigation.Source: §8.3 · p. 26

9 SOCIAL IMPACTS

As global solvers move from research toward safety-critical deployment, their societal responsibilities extend beyond technical performance to safety, transparency, learning integration, and ethical use.

9.1 Safety-Critical Applications

  • Global pose estimation and triangulation can reduce catastrophic downstream risk, while certifiable solvers can signal when guarantees fail and support fail-safe design.This is especially relevant where oversight is limited, including deep-space exploration and remote surgery.Source: §9.1 · p. 26

9.2 Trust, Transparency, and Accountability

  • Global solvers provide optimality certificates or suboptimality bounds, while explicit objectives and constraints support validation, auditing, accountability, and regulatory compliance.These properties are important in industrial inspection [466], infrastructure monitoring, medical diagnosis support, and structural safety assessment.Source: §9.2 · p. 26

9.3 Integration with Learning-Based Systems

  • Learned warm-starts and priors can improve scalability, but training-data bias, privacy, fairness, and distribution shift can undermine reliable certification.Hybrid systems need validation, uncertainty-aware learning and robust verification, plus documentation of training data and deployment assumptions.Source: §9.3 · p. 26

9.4 Computational Resources and Accessibility

  • Global solvers’ computational demands can restrict access to well-resourced organizations and carry an energy footprint that grows with large-scale deployment.Scalable algorithms and specialized hardware are proposed to reduce access barriers and environmental impact.Source: §9.4 · p. 27

9.5 Ethical and Societal Considerations

  • Certifiable 3D vision has beneficial uses but is dual-use, with potential applications in invasive surveillance, unauthorized tracking, and military targeting.The research community should address misuse through transparent capability and limitation reporting, engagement with ethicists and policymakers, and deployment guidelines; open-source tools, benchmarks, and education can broaden access, while institutional and regulatory frameworks should protect societal welfare and individual rights.Source: §9.5 · p. 27

10 CONCLUSION

The survey organizes global solvers for 3D vision into three paradigms and examines their foundations, practical enhancements, and use across ten geometric vision tasks. It identifies trade-offs in guarantees and efficiency, and calls for advances to support reliable real-world deployment.

10 CONCLUSION

  • The survey unifies Branch-and-Bound, Convex Relaxation, and Graduated Non-Convexity across ten geometric vision tasks, from pose estimation to bundle adjustment.It examines their theoretical foundations and practical enhancements for robustness and scalability.Source: §10 · p. 27
  • Certifiable methods offer global guarantees at significant computational cost, while continuation approaches sacrifice guarantees for efficiency.The choice depends on application requirements, problem structure, and deployment constraints.Source: §10 · p. 27
  • Realizing global solvers’ potential requires advances in algorithmic scalability, integration with data-driven methods, standardized evaluation, and attention to societal impacts in safety-critical applications.Source: §10 · p. 27
  • Global solvers provide a foundation for trustworthy, certifiable 3D perception as systems move from controlled environments toward real-world deployment.The survey characterizes them as bridging theoretical guarantees and practical reliability.Source: §10 · p. 27

Related papers

Loading 2602.14662v1…