When reconstructing the 3D world from 2D images or point clouds, computer vision algorithms must solve a fundamental puzzle: how to aggregate thousands of local, noisy measurements into a single, globally coherent geometric structure. Historically, this aggregation relies on optimization objectives chosen for mathematical convenience, such as the $L_2$ least-squares norm or the $L_\infty$ minimax norm.
However, real-world data is rarely just "noisy"—it is frequently corrupted by outliers. False feature correspondences, occlusions, and repetitive environmental structures produce measurements that are completely wrong, rather than slightly off. To build reliable spatial computing systems, geometric optimization must be made natively resilient to these catastrophic errors.
Why Standard Norms Fail
To understand why standard geometric optimization fails in the presence of outliers, we must look at the mathematical leverage these objectives grant to large errors.
In a least-squares ($L_2$) formulation, the error of every measurement is squared. If an automated feature matcher incorrectly links a pixel on a foreground object to a background structure, the resulting geometric distance error is massive. Squaring this massive error gives the outlier outsized leverage over the total cost function. The optimization landscape warps, pulling the global solution away from the true geometry or trapping the solver in a poor local minimum. As noted by Gk Tejus et al. and Yunpeng Shi et al. in the context of rotation synchronization, standard squared-error losses degrade rapidly in unstructured or noisy environments because they lack an inherent mechanism to downweight extreme noise.
The vulnerability is even more acute for the minimax ($L_\infty$) norm. Because the $L_\infty$ norm seeks to minimize the maximum error across all observations, its value is entirely dictated by the single worst data point. As Qianggong Zhang and Richard Hartley et al. demonstrate, a single gross outlier can completely derail an $L_\infty$ global optimization, making traditional minimax formulations highly unreliable without aggressive, brittle pre-filtering stages.
Designing Natively Robust Cost Functions
To counter this sensitivity, a major thrust of research focuses on replacing squared-error metrics with cost functions that inherently cap or reduce the influence of large errors. The most prominent alternative is the $L_1$ norm, which penalizes errors linearly rather than quadratically, stripping outliers of their outsized leverage.
Chunyu Wang et al. and Yuchao Dai et al. leverage $L_1$ optimization to make 3D human pose estimation and non-rigid structure-from-motion resilient to tracking failures and occlusions. However, $L_1$ optimization introduces a significant mathematical hurdle: the absolute value function is non-differentiable at zero, meaning standard gradient descent techniques cannot be directly applied.
To resolve this computational bottleneck, Dennis Strelow generalized Wiberg minimization to handle robust, non-differentiable norms in bundle adjustment. Alternatively, Daichi Iwata et al. introduced Sketched Iteratively Reweighted Least Squares (IRLS), which accelerates robust regressions by projecting large-scale linear systems into lower dimensions while preserving the outlier resilience of $\ell_1$ minimization. Other approaches bypass pixel-level coordinate differences entirely; Georgios Tzimiropoulos demonstrates that maximizing the correlation of image gradient orientations creates an alignment framework that naturally ignores severe occlusions without requiring heavy matrix recomputations at every step.
Certifiable Optimality and Convex Relaxations
Even with a robust cost function, geometric optimization remains fundamentally non-convex due to the underlying geometry of 3D space—such as the non-linear constraints of the rotation manifold $SO(3)$. Traditional local search methods like bundle adjustment require highly accurate initializations to avoid getting stuck in local minima, as highlighted by Christopher Zach et al..
To guarantee finding the true global solution despite massive noise, researchers employ convex relaxations. By translating non-convex geometric constraints into higher-dimensional convex spaces using Semidefinite Relaxations (SDR) or Sums-of-Squares (SOS) relaxations, algorithms can find the mathematically optimal 3D structure or provably determine if a global optimum is unattainable.
For instance, Linus Härenstam-Nielsen et al. combine SDR with a robust cost function to achieve certifiably optimal multi-view triangulation that resists massive data noise without relying on stochastic heuristics like RANSAC. Similarly, Heng Yang et al. developed a robust solver, Shape#, that guarantees global optimality for 3D shape reconstruction from 2D landmarks, maintaining high accuracy even when up to 70% of the input data consists of outliers.
Exploiting Geometric Consistency
Rather than relying solely on the cost function to suppress outliers during the final optimization stage, a parallel strategy filters or denoises measurements early by exploiting structural invariants. In camera networks and pose graphs, the most powerful invariant is cycle consistency: the geometric rule that the product of relative transformations around any closed loop must equal the identity matrix. If a loop fails to close, an outlier is mathematically guaranteed to be present within that cycle.
True Geometry: Corrupted Measurement (Outlier):
Camera A Camera A
/ \ / \
/ \ / \
Relative Relative Relative Relative
/ \ / \
Camera B ——— Camera C Camera B ——— Camera C
Relative (Distorted)
[Loop Closes: AB*BC*CA = I] [Loop Fails to Close: AB*BC*CA != I]
Arman Karimian et al. utilize an Alternating Direction Method of Multipliers (ADMM) framework to identify and remove bad rotation measurements via cycle consistency before full 3D reconstruction begins, preventing solvers from getting trapped in local minima. Taking this further, Shaohan Li et al. introduce Cycle-Sync, a message-passing framework that leverages cycle consistency to achieve robust global camera pose estimation without expensive post-processing, maintaining accuracy even when 80% of the input data is corrupted.
By combining these structural consistency checks with optimization directly on the rotation manifold—as seen in the Riemannian subgradient approach of Huikang Liu et al.—modern geometric optimization transforms from a fragile mathematical ideal into a highly resilient framework capable of mapping the real, messy world.
Key Foundational Work
Quasiconvex Optimization for Robust Geometric Reconstruction (2005) — contributed 1 concept elements to this direction.
A visual servoing control law that is robust to image outliers (2003) — contributed 1 concept elements to this direction.