Real-Time Latency of Convex Relaxations in Geometric Perception

23 concepts22 papers1 proposal

In robotics and computer vision, geometric perception tasks—such as estimating the position of a drone, aligning 3D point clouds, or reconstructing a scene from images—fundamentally rely on optimization. However, the underlying mathematics of these problems is notoriously non-convex. Because operations involve rotations and translations in three-dimensional space ($SE(3)$), the error landscapes are riddled with local minima.

Historically, practitioners have relied on local search heuristics (like gradient descent or Levenberg-Marquardt) paired with randomized outlier rejection frameworks like RANSAC. While these methods are fast, operating on the order of milliseconds, they offer no guarantees: if the initialization is poor or the data is highly corrupted, the algorithm can get permanently trapped in a local minimum.

To solve this, researchers developed certifiable global optimization techniques. By using mathematical tools like Semidefinite Programming (SDP), Second-Order Cone Programming (SOCP), and Lagrangian duality, non-convex geometric problems can be "relaxed" into convex ones. These formulations guarantee convergence to the global minimum and can mathematically prove whether the solution found is optimal.

However, this theoretical triumph faces a major practical hurdle: computational latency. While local heuristics take milliseconds, solving high-dimensional convex relaxations often takes seconds or even minutes. This latency gap creates a critical bottleneck, preventing these mathematically rigorous algorithms from being deployed in high-frequency, real-time robotic control loops.


Why Convex Relaxations Introduce Latency

To understand why global solvers are slow, we must look at how they achieve their guarantees. A standard geometric problem requires finding a valid rotation matrix $R$. The constraint that makes this non-convex is quadratic: $R^T R = I$ and $\det(R) = 1$.

Convex relaxation methods, such as those analyzed by Horowitz et al. in Convex Relaxations of SE(2) and SE(3) for Visual Pose Estimation, sidestep this non-convexity by "lifting" the problem into a higher-dimensional space. Instead of optimizing over the original low-dimensional variables directly, the problem is rewritten in terms of a much larger, higher-dimensional matrix that captures the relationships between all variables and their products.

[Original Non-Convex Space]  ───(Lifting via Relaxation)───>  [Higher-Dimensional Convex Space]
   - Bumpy error landscape                                      - Smooth, bowl-shaped landscape
   - Trapped in local minima                                    - Single global minimum
   - Fast to compute (ms)                                       - Computationally expensive (seconds)

While this lifting flattens the bumpy error landscape into a smooth, convex bowl where the global minimum can be easily found, it explodes the size of the problem matrix. Generic convex solvers (such as interior-point methods) scale poorly with matrix size. As a result, the computational overhead becomes an order of magnitude higher than local search algorithms, creating a significant latency gap.


The Latency Bottleneck Across Vision and Robotics

This trade-off between guaranteed accuracy and computational speed manifests across nearly every domain of geometric perception, rendering general-purpose global solvers impractical for live systems.

1. Object and Pose Estimation

In relative pose estimation and inverse kinematics, algorithms must compute transformations instantly to guide actions. Briales et al. developed a certifiably optimal solver for the non-minimal relative pose problem in A Certifiably Globally Optimal Solution to the Non-Minimal Relative Pose Problem, but noted that the resulting SDP processing times prevent its use in high-frame-rate applications like visual SLAM. Similarly, when formulating inverse kinematics as an initialization-free global optimization problem, Yenamandra et al. demonstrated in Convex Optimisation for Inverse Kinematics that current solvers require several seconds per pose—far exceeding the millisecond-level response times required for live robotics or virtual reality tracking.

2. Localization and Mapping (SLAM)

For autonomous vehicles and drones, real-time state estimation is a safety-critical requirement. In Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models, Lajoie et al. observed that the high computational complexity of SDP relaxations precludes their use in live navigation systems. This sentiment is echoed by Carlone in Estimation Contracts for Outlier-Robust Geometric Perception, where the author notes that high-order SDP relaxations face severe latency challenges that block deployment in high-frequency drone navigation.

Even when the motion is restricted to a 2D plane, global inlier maximization techniques using Branch-and-Bound (BnB) methods face severe computational overhead compared to minimal heuristic solvers, as shown by Chen et al. in Globally-Optimal Inlier Maximization for Relative Pose Estimation Under Planar Motion. Consequently, as surveyed by Basri et al. in A survey of structure from motion, robust convex solvers remain largely restricted to offline processing rather than live, closed-loop systems.

3. 3D Registration and Triangulation

Aligning point clouds or triangulating 3D points from multiple camera views suffers from the same latency constraints. In Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration, Yang et al. combined a systematic BnB search with local ICP to guarantee optimal 3D registration, but the convergence time limits its utility in dynamic environments.

For triangulation tasks, Donné et al. demonstrated in Point Triangulation through Polyhedron Collapse Using the l∞ Norm that heavy-duty solvers like SOCP struggle to meet low-latency vision requirements. Similarly, Härenstam-Nielsen et al. showed in Semidefinite Relaxations for Robust Multiview Triangulation that while semidefinite relaxations provide robust triangulation guarantees under heavy noise, their high latency restricts them to offline applications.

Task Global Optimization Mechanism Latency Scale Real-Time Suitability
Consensus Maximization (Speciale et al.) Linear Matrix Inequalities (LMI) Seconds to Minutes Offline / Prioritized Accuracy
Shape Reconstruction (Yang et al.) Sums-of-Squares (SOS) Relaxation Seconds Offline / Initialization-free
Multi-Robot Calibration (Wen et al.) Semidefinite Relaxation (SDR) Minutes Periodic Background Tasks
Orientation Tracking (Lee et al.) Exhaustive / Global Search Seconds Unsuitable for Mobile AR

Pathways to Real-Time Performance

To bridge this latency gap, the research community is moving away from generic, off-the-shelf optimization packages. Instead, the focus has shifted toward designing specialized solvers that exploit the unique mathematical structures inherent to geometric vision.

Exploiting Low-Dimensional Structure

Generic SDP solvers treat the lifted problem matrix as an arbitrary block of numbers. However, geometric matrices are highly structured and sparse. In Convex Global 3D Registration with Lagrangian Duality, Briales et al. demonstrated that by adding clever redundant constraints and exploiting the specific low-dimensional structure of the problem matrix, specialized solvers can achieve up to a 100x speedup over general-purpose alternatives.

Basis Reduction

When using high-order relaxations like Sums-of-Squares (SOS) polynomials, the number of variables grows combinatorially. To combat this, Yang et al. introduced a "basis reduction" technique in In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction From 2D Landmarks. By pruning unnecessary polynomial terms before solving the relaxation, they significantly reduced the size of the semidefinite matrices, accelerating the path toward real-time certifiable convergence.

Decoupled Architectures

Another practical workaround is to decouple the high-latency global optimization from the real-time control loop. As suggested by Wen et al. in Simultaneous Time Synchronization and Mutual Localization for Multi-robot System, high-latency semidefinite relaxations can be executed as periodic background calibration processes, while low-latency local trackers handle high-frequency control tasks.

Ultimately, the transition of certifiably optimal perception from offline theory to real-time robotic deployment relies entirely on this co-design of geometric theory and specialized numerical optimization.

Key Foundational Work

Geometrically consistent elastic matching of 3D shapes: A linear programming solution (2011) — contributed 1 concept elements to this direction.
Convex Relaxations of SE(2) and SE(3) for Visual Pose Estimation (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_real_time_processing_constraints_computa_026409b1,
  title = {real-time processing constraints (computational latency of global optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/real-time-processing-constraints-computational-latency-of-global-optimization/rdr_026409b1e0244c56a3b142bc5f9b34b2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_real_time_processing_constraints_computa_026409b1_v1,
  title = {real-time processing constraints (computational latency of global optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/real-time-processing-constraints-computational-latency-of-global-optimization/rdr_026409b1e0244c56a3b142bc5f9b34b2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake