Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization

1 INTRODUCTION

• Robust estimation is combinatorial and NP-hard, leaving fast heuristics without optimality guarantees and global solvers with worst-case exponential runtimes.The framework aims to certify estimates on common instances while allowing failure on worst-case instances rather than returning an incorrect estimate.Source: §1 · p. 1

2.2 Polynomial Optimization and Lasserre’s Hierarchy

• Lasserre’s hierarchy relaxes polynomial optimization problems into increasingly large convex SDPs that provide suboptimality measures and become exact under mild technical conditions.The hierarchy respects worst-case NP-hardness because the SDP size may need to grow exponentially with the problem dimension.Source: §1 · p. 2

1 INTRODUCTION

• Common robust costs, including TLS, maximum consensus, Geman-McClure, Tukey’s Biweight, L1, Huber, and Barron’s adaptive kernel, can be reformulated as polynomial optimization problems.The reformulations introduce additional variables and manipulate the original costs into polynomials.Source: §1 · p. 2
• For TLS, exploiting polynomial term sparsity and perception-problem structure yields a sparse semidefinite relaxation 100 times smaller than the standard Lasserre hierarchy.The paper reports empirical exactness only on small problems when using existing SDP solvers, which remain too slow even with the sparse relaxation.Source: §1 · p. 2
• STRIDE combines projected-gradient descent on the convex SDP with safeguarded rank-one strides from local search on the nonconvex problem.It can use RANSAC or GNC as a warm start, certify their estimates when globally optimal, and detect and escape local minima otherwise.Source: §1 · p. 2
• The sparse SDP is empirically exact with up to 60%–90% outliers across applications.STRIDE is up to 100 times faster than existing SDP solvers on medium-scale problems and uniquely solves large SDPs with hundreds of thousands of constraints to high accuracy.Source: §1 · p. 3

2.1 Semidefinite Programming

• The paper’s SDPs have fewer than 5,000 variables but up to millions of constraints, and their rank-one optima are degenerate, challenging existing solvers.The authors state that these properties render interior-point methods and Burer–Monteiro factorization inapplicable, while first-order methods perform poorly on degenerate problems.Source: §2.1 · p. 4

2.2 Polynomial Optimization and Lasserre’s Hierarchy

• Rewriting the polynomial objective and constraints in a moment matrix, dropping its rank-one constraint, and adding moment, equality, and localizing constraints yields a convex dense SDP.The relaxation uses a fully dense monomial basis; different orders produce a hierarchy of convex relaxations.Source: §2.2 · p. 5
• Under the Archimedeanness condition, the relaxation’s lower bounds converge to the POP optimum as its order increases, with finite convergence under suitable technical conditions.If an order attains the POP optimum, rank-one optimal solutions correspond to global minimizers of the POP.Source: §2.2 · p. 5
• When the relaxation is exact, rank-one optimal solutions represent global minimizers, and checking the SDP solution’s rank can provide a global-optimality certificate.Rank computation can be numerically inaccurate, motivating a continuous metric for evaluating relaxation exactness.Source: §2.2 · p. 5

Robust costs as POPs

• For seven popular robust costs, estimation can be recast as a POP; TLS uses binary variables to mark inliers and outliers.Other costs are converted using slack variables or changes of variables.Source: §3 · pp. 5–6

Robust estimation formulation

• Under Assumption 3, robust estimation uses polynomial squared residuals and regularization with a feasible set described by polynomial equalities and inequalities.The formulation includes a measurement residual, robust cost, and optional regularizer.Source: §3 · p. 6

Perception examples

• Single rotation averaging, multiple rotation averaging, and point-cloud registration model rotation estimates or rigid alignment from noisy measurements and correspondences.The examples use chordal-distance rotation residuals and Euclidean point-alignment residuals.Source: §3 · pp. 6–7
• Mesh registration, absolute pose estimation, and category-level object perception estimate rigid pose, with category-level estimation also recovering shape coefficients.Their residuals respectively use point-to-plane and normal distances, point-to-line distance, and semantic-keypoint distance to a shape model.Source: §3 · p. 7

Polynomial expressibility

• All six examples satisfy Assumption 3, with quadratic squared residuals and regularizers and polynomial constraints of degree at most two.For absolute pose estimation, point-to-line distance is chosen instead of geometric reprojection error so the squared residual is polynomial.Source: §3 · p. 7

Scope and extensions

• The framework also covers additional perception problems, but bundle adjustment with point-to-line error typically has too many variables for existing semidefinite relaxations.With geometric reprojection error, bundle adjustment cannot be written as a POP.Source: §3 · p. 8

Focus on TLS

• The paper focuses on TLS because it discards outliers while minimizing inlier residuals, whereas maximum consensus can leave infinitely many equal-cost solutions.Adaptive costs can require high-degree polynomials and intractable SDPs; TLS is also a maximum-likelihood estimator under Gaussian inliers and uniformly distributed outliers.Source: §3 · p. 8

Scalability improvement

• Dense LAS at order κ = 2 can already be too large for existing solvers at desired problem sizes, including d = 10 and N = 100.That instance has n1 = 6,216 and 12,649,561 moment constraints.Source: §4 · p. 8

Sparse semidefinite relaxation

• SSR uses a sparse monomial basis containing the monomials in the TLS objective and constraints, producing a moment matrix of size (1 + d)(1 + N).The selected monomials are [x]^2, θ_i·[x]^2, and θ_i^2.Source: §4 · p. 8
• The relaxation drops the nonconvex rank-one constraint on the sparse moment matrix while retaining positive semidefiniteness and adding moment, equality, and localizing constraints.Moment constraints enforce repeated monomials to agree; localizing matrices impose positive semidefinite constraints associated with inequalities.Source: §4 · pp. 8–9

Certifiable global optimality

• SSR lower-bounds the TLS optimum, and a rank-one optimal moment matrix certifies that the relaxation is exact and recovers a global TLS optimizer.If the relaxation is exact, rank-one optimal solutions correspond to global minimizers of TLS.Source: §4 · p. 9

Scalability improvement

• At N = 200, SSR reduces the largest PSD block by about 10 times and moment constraints by 100 times versus LAS, and is empirically exact across Examples 1–6.For Example 1, LAS has n1 > 20,000 and mmom > 100,000,000, while SSR has n1 ≈ 2,000 and mmom ≈ 1,000,000.Source: §4 · p. 9, Table 1 · p. 10

Exploiting sparsity

• SSR can be exact only when dense LAS is exact, and whether a sparse basis preserves exactness must be checked empirically.The authors report a different sparse basis that is far from exact and note that TSSOS can produce a larger basis than their problem-specific SSR.Source: §4 · p. 10

STRIDE

• STRIDE blends a globally convergent projected-gradient-descent backbone for the SDP with long rank-one steps from local search on the nonconvex TLS problem.The rank-one steps aim to accelerate convergence; the SDP backbone allows escape from local minima where the nonlinear-programming search can be stuck.Source: §5 · p. 10

Long rank-one step

• Each long step rounds leading eigenvectors into feasible TLS hypotheses, locally optimizes them, and lifts the best solution back into the SDP.The method compares this candidate with the projected-gradient-descent step and accepts it only if its cost is strictly lower.Source: §5 · pp. 10–11

Global convergence

• Under the Slater condition, STRIDE’s SDP objective values converge to the SDP optimum, including when the optimal solution has rank higher than one.The method accepts a rank-one stride only when it strictly decreases the objective, while the projected-gradient-descent backbone supports convergence.Source: §5 · p. 11

Initialization

• STRIDE’s convergence speed can depend significantly on its initial guess.The authors describe fast heuristics as a source of primal initialization and a separate dual-initialization procedure.Source: §5 · p. 11

Fast heuristics and certification

• Existing GNC or RANSAC estimates can initialize STRIDE, which needs only one projected-gradient-descent step to certify an estimate that is already globally optimal when SSR is exact.The paper says these heuristics can typically return globally optimal TLS solutions when the measurement set has a low or medium outlier portion, e.g., below 70%.Source: §5 · p. 11

6.1 Single Rotation Averaging

• At N = 30 and N = 100, the single-rotation relaxation is exact up to 90% and 95% outliers, respectively; STRIDE is about 100 times faster than MOSEK at N = 30.At N = 100, STRIDE reaches ηmax = 1e−8 while SDPNAL+ reaches 1e−3; at 90% outliers with N = 30, a globally optimal estimate can still have about 100° rotation error.Source: §6.1 · p. 12

6.2 Multiple Rotation Averaging

• For a 10 × 10 grid with N = 10 loop closures, the relaxation is exact up to 80% outliers and STRIDE is about 20 times faster than MOSEK; at 20 × 20, it is almost always exact up to 80%.At 20 × 20, STRIDE misses ηs < 1e−3 in 1–2 runs per outlier rate, which the authors suspect are inexact relaxations.Source: §6.2 · p. 12

6.3 Point Cloud Registration

• For N = 20, the point-cloud relaxation is tight up to 80% outliers and STRIDE is about 5 times faster than MOSEK; for N = 100, STRIDE alone certifies exactness up to 90%.At 90% outliers with N = 100, STRIDE certifies global optimality in 17 runs and fails to do so in 3; it also certifies GNC successes and escapes local minima.Source: §6.3 · p. 12
• In the 3DMatch scan-matching examples, STRIDE returns certified globally optimal rigid transformations with ηs < 1e−6.The pipeline first uses FPFH matches and ROBIN to filter gross outliers.Source: §6.3 · p. 12

6.4 Absolute Pose Estimation

• For absolute pose estimation with N = 20, the relaxation is exact up to 60% outliers; at N = 100, it is mostly tight at 70%.At 70% outliers with N = 20, a high-accuracy SDP solution is not rank one, and rounding yields a pose far from ground truth; the authors note earlier relaxation breakdown with fewer measurements.Source: §6.4 · pp. 12–13
• On SPEED satellite-pose examples with 2–5 outliers, STRIDE obtains accurate estimates with certified global optimality in less than one minute.The examples use 11 model keypoints.Source: §6.4 · p. 13

6.5 Category-Level Object Perception

• For category-level pose and shape estimation, the relaxation is exact up to 60% outliers, STRIDE is about 10 times faster than MOSEK, and it certifies GNC optima or escapes local minima.On ApolloScape, STRIDE both certifies solutions returned by GNC and escapes its suboptimal solutions.Source: §6.5 · pp. 13–14

6.6 Summary and Discussion

• When heuristics already reach the global optimum, STRIDE can focus on certification and be 2–5 times faster than its escape mode; its speed also varies by application.The discussion says STRIDE solves problems beyond MOSEK’s reach, while SDP geometry may explain application-dependent speed.Source: §6.6 · p. 14

Outlier-free geometric perception

• Outlier-free methods include minimal solvers for noiseless measurements and non-minimal solvers that account for noise, often using nonlinear least squares and local or exponential-time optimization.Certifiable methods apply semidefinite relaxations to nonlinear least squares and use rank or duality-gap conditions to certify global solutions.Source: §7 · p. 14

Certifiable algorithms for outlier-free perception

• Recent semidefinite relaxations have been empirically tight across applications including pose graphs, rotation averaging, triangulation, registration, and pose estimation.The discussion also notes emerging theoretical analyses of when and why these relaxations are tight.Source: §7 · p. 14

Outlier-robust geometric perception

• Robust methods include RANSAC and GNC heuristics, local optimization, deterministic approximation, and globally optimal Branch-and-Bound solvers.RANSAC robustifies minimal solvers for consensus maximization; GNC robustifies non-minimal solvers for M-estimation.Source: §7 · p. 15

Certifiable outlier-robust methods

• Certifiably robust methods relax robust-cost problems into tight convex programs; L1 and Huber costs are convex but have low breakdown points, while TLS supports high-breakdown formulations.The cited discussion describes existing high-breakdown certifiable approaches as problem-specific.Source: §7 · p. 15

8 CONCLUSIONS

• The framework reformulates several common robust costs as polynomial optimization problems, exploits sparsity for smaller empirically exact semidefinite relaxations, and uses STRIDE to solve them at scale and accuracy.Experiments on six applications with synthetic and real data demonstrate robustness, scalability, and the ability to safeguard fast heuristics.Source: §8 · p. 15

Proof of Proposition 4

• Black-Rangarajan duality proves the reformulations for several costs, while manipulating the cost functions establishes the remaining cases.The proof concludes by covering all seven cost functions.Source: A1 PROOF OF PROPOSITION 4 · p. 17
• For Geman-McClure and Tukey’s biweight, the proof introduces confidence variables and changes variables using θ := √w to obtain polynomial optimization formulations.For TLS and maximum consensus, θi is binary; for Geman-McClure and Tukey’s biweight, θi is continuous and indicates inlier confidence.Source: A1 PROOF OF PROPOSITION 4 · p. 17
• The Huber-cost proof uses γ = |r| and a binary θ whose sign constraint selects the residual regime around βi.The resulting formulation is stated as a polynomial optimization problem.Source: A1 PROOF OF PROPOSITION 4 · p. 17
• The adaptive-cost reformulation restricts scale s to rational values, which the proof says preserves expressiveness because rationals are dense in the reals.The proof avoids s = 0 and s = 2, where the cost function is undefined.Source: A1 PROOF OF PROPOSITION 4 · p. 17

• Squared norms of affine degree-one polynomials in the examples are quadratic, supporting the polynomial form required for the optimization problem.Source: A2 PROOF OF PROPOSITION 7 · p. 18
• The ball and field-of-view cone constraints can be represented by quadratic inequalities, with the cone also requiring an affine inequality.Source: A2 PROOF OF PROPOSITION 7 · p. 18
• A 3D rotation is represented by 15 quadratic equalities; although redundant, the full set is used to enhance relaxation robustness and tightness.Source: A2 PROOF OF PROPOSITION 7 · p. 18

• A rank-one lifting of any feasible TLS point is feasible for the SDP, so the SDP optimum is no greater than the TLS optimum.Source: A3 PROOF OF THEOREM 9 · p. 18
• An optimal TLS point also induces a rank-one SDP lifting that attains the TLS optimum.Source: A3 PROOF OF THEOREM 9 · p. 18
• If the SDP optimizer has rank one, a global optimizer can be extracted from it.The moment constraints identify the lifted mixed terms as products, while redundant equalities and localizing constraints enforce TLS feasibility.Source: A3 PROOF OF THEOREM 9 · p. 18
• The extracted feasible point attains the SDP value, which equals the TLS optimum and therefore certifies global optimality.Source: A3 PROOF OF THEOREM 9 · p. 18

• A formally correct relative suboptimality gap compares the rounded TLS estimate’s cost with a valid lower bound on the unknown optimum.The lower bound can be computed from an approximate SDP solution using the dual variable, without requiring the SDP solution to be optimal.Source: A4 RELATIVE SUBOPTIMALITY · pp. 18–19
• A zero relative suboptimality gap implies the relaxation is exact and the rounded solution is globally optimal for TLS.Source: A4 RELATIVE SUBOPTIMALITY · p. 18
• Computing the SDP lower bound to machine precision can be challenging, and first-order solvers may fail to attain it at moderate accuracy within reasonable iterations.Source: A4 RELATIVE SUBOPTIMALITY · pp. 18–19
• The lower-bound construction uses bounded traces for the moment and localizing matrices, supported by bounded variables and inequality constraints in the examples.Source: A4 RELATIVE SUBOPTIMALITY · p. 19

A5 FURTHER REDUCTION ON MULTIPLE ROTATION AVERAGING (EXAMPLE 2)

• With a larger neighborhood depth, the reduced multiple-rotation relaxation achieves exactness with over 70% outliers; the ζ = 0 version recovers a hand-crafted relaxation reported inexact around 50%.The reduction focuses the basis on rotations associated with outlier edges and nearby nodes.Source: A5 FURTHER REDUCTION ON MULTIPLE… · pp. 19–20

A6 SOLVING THE PROJECTION SUBPROBLEM

• STRIDE solves its projection subproblem through an unconstrained dual formulation, enabling a scalable L-BFGS algorithm.Dykstra’s alternating projections can converge slowly and require too many iterations for a satisfactory projection.Source: A6 SOLVING THE PROJECTION SUBPROBLEM · p. 20

A7 PROOF OF THEOREM 11

• STRIDE’s accepted iterates decrease the objective by at least ϵ, so only finitely many are accepted before the method reduces to globally convergent projected gradient descent.The proof rules out infinitely many accepted iterates because that would make the objective unbounded below, contradicting Slater’s condition and strong duality.Source: A7 PROOF OF THEOREM 11 · p. 20

A8.1.1 Bootstrapping via Correlative Sparsity

• Correlative sparsity partitions variables into groups and represents the TLS objective and constraints using N smaller moment matrices.The resulting CSSR has smaller blocks than SSR, but is not tight and cannot certify an optimal TLS solution.Source: A8.1.1 Bootstrapping via Correlative… · pp. 21–22
• The sparse relaxation adds moment, equality, and localizing constraints, then enforces consistency between overlapping entries of its moment matrices.The shared top-left 2×2 blocks are constrained to agree across the matrices.Source: A8.1.1 Bootstrapping via Correlative… · pp. 21–22
• The inexact CSSR solution is used to warmstart STRIDE by assembling its local dual components into the larger SDP structure.The assembly reflects combining local SOS polynomials in (x, θ) into a polynomial over the full variables.Source: A8.1.1 Bootstrapping via Correlative… · p. 22

A8.1.2 Semi-proximal ADMM

• ADMM+ refines primal and dual initializations from heuristics and CSSR; the authors report that the higher-quality starts promote STRIDE convergence.They run ADMM+ for at most 20,000 iterations or until the maximum primal or dual residual falls below a threshold such as 1e−6.Source: A8.1.2 Semi-proximal ADMM · p. 22

A8.2 Local Search and Nonlinear Programming

• Local search solves TLS from an initial point using nonlinear programming, with Riemannian optimization exploiting smooth structure in binary variables and geometric rotations.Some translation and shape constraints are relaxed for manifold search; STRIDE rejects NLP solutions that violate the dropped constraints.Source: A8.2 Local Search and Nonlinear… · p. 23

A9.1 Mesh Registration

• For mesh registration with N = 20, the relaxation was not always tight at 70% and 80% outliers; TeddyBear examples show certificates at 50% and 70% outliers, including escape from a GNC local minimum.For N = 100, the results were mostly the same as point cloud registration; the reported TeddyBear certificates had ηs = 2.5e−8 and ηs = 1.1e−7.Source: A9.1 Mesh Registration · p. 23

A9.2 Robustness of the TLS Estimator

• With an 80% outlier rate, increasing single-rotation measurements from N = 30 to N = 100 generally reduced TLS estimation error, and all solutions were certified globally optimal.TLS errors were comparable with least squares computed from inliers only.Source: A9.2 Robustness of the TLS Estimator · p. 23

A9.3 Scaling the Noise Bound

• At 50% outliers with N = 50, varying the noise bound β showed a wide range of certifiably optimal and accurate estimates; 15 of 20 runs kept the same solution at 0.9, 1, and 1.1 scaling.These runs used the same measurements while changing only the noise bound.Source: A9.3 Scaling the Noise Bound · p. 24

A9.4 Point Cloud Registration on 3DMatch

• On 3DMatch, STRIDE returned globally optimal transformation estimates in all 10 extra scan-matching results.Source: A9.4 Point Cloud Registration on 3DMatch · p. 24

A9.5 Absolute Pose Estimation on SPEED

• On SPEED, STRIDE returned accurate pose estimates with global optimality certificates in all six image instances with 2–5 outliers.Source: A9.5 Absolute Pose Estimation on SPEED · p. 24

A9.6 Vehicle Pose and Shape Estimation on ApolloScape

• On ApolloScape, STRIDE returned accurate vehicle pose and shape estimates with global optimality certificates in all reported cases.Source: A9.6 Vehicle Pose and Shape Estimation… · p. 24

2 outliers 3 outliers 4 outliers 5 outliers

• Reported errors include R error: 0.48◦ with t error: 0.05, and R error: 0.37◦ with t error: 0.07.Source: §2 · p. 30
• Additional reported errors include R error: 0.37◦ with t error: 0.07, and R error: 0.34◦ with t error: 0.07.Source: §2 · p. 30
• Two further entries report R error: 1.75◦ with t error: 0.09, ηs = 1.5e−7, time: 4899 [s], and R error: 1.74◦ with t error: 0.03, ηs = 1.6e−9, time: 4446 [s].Source: §2 · p. 31