We propose the first general and scalable framework to design certifiable
algorithms for robust geometric perception in the presence of outliers. Our
first contribution is to show that estimation using common robust costs, such
as truncated least squares (TLS), maximum consensus, Geman-McClure, Tukey's
biweight, among others, can be reformulated as polynomial optimization problems
(POPs). By focusing on the TLS cost, our second contribution is to exploit
sparsity in the POP and propose a sparse semidefinite programming (SDP)
relaxation that is much smaller than the standard Lasserre's hierarchy while
preserving empirical exactness, i.e., the SDP recovers the optimizer of the
nonconvex POP with an optimality certificate. Our third contribution is to
solve the SDP relaxations at an unprecedented scale and accuracy by presenting
STRIDE, a solver that blends global descent on the convex SDP with fast local
search on the nonconvex POP. Our fourth contribution is an evaluation of the
proposed framework on six geometric perception problems including single and
multiple rotation averaging, point cloud and mesh registration, absolute pose
estimation, and category-level object pose and shape estimation. Our
experiments demonstrate that (i) our sparse SDP relaxation is empirically exact
with up to 60%-90% outliers across applications; (ii) while still being far
from real-time, STRIDE is up to 100 times faster than existing SDP solvers on
medium-scale problems, and is the only solver that can solve large-scale SDPs
with hundreds of thousands of constraints to high accuracy; (iii) STRIDE
safeguards existing fast heuristics for robust estimation (e.g., RANSAC or
Graduated Non-Convexity), i.e., it certifies global optimality if the heuristic
estimates are optimal, or detects and allows escaping local optima when the
heuristic estimates are suboptimal.

该研究提出了第一个通用且可扩展的框架，用于设计可靠的几何感知算法，以在存在异常值的情况下证明其准确性，并在六个几何感知问题上进行了评估。

确证最优离群点鲁棒几何感知：半定松弛和可扩展全局优化

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

We propose the first general and practical framework to design certifiable
algorithms for robust geometric perception in the presence of a large amount of
outliers. We investigate the use of a truncated least squares (TLS) cost
function, which is known to be robust to outliers, but leads to hard,
nonconvex, and nonsmooth optimization problems. Our first contribution is to
show that -for a broad class of geometric perception problems- TLS estimation
can be reformulated as an optimization over the ring of polynomials and
Lasserre's hierarchy of convex moment relaxations is empirically tight at the
minimum relaxation order (i.e., certifiably obtains the global minimum of the
nonconvex TLS problem). Our second contribution is to exploit the structural
sparsity of the objective and constraint polynomials and leverage basis
reduction to significantly reduce the size of the semidefinite program (SDP)
resulting from the moment relaxation, without compromising its tightness. Our
third contribution is to develop scalable dual optimality certifiers from the
lens of sums-of-squares (SOS) relaxation, that can compute the suboptimality
gap and possibly certify global optimality of any candidate solution (e.g.,
returned by fast heuristics such as RANSAC or graduated non-convexity). Our
dual certifiers leverage Douglas-Rachford Splitting to solve a convex
feasibility SDP. Numerical experiments across different perception problems,
including single rotation averaging, shape alignment, 3D point cloud and mesh
registration, and high-integrity satellite pose estimation, demonstrate the
tightness of our relaxations, the correctness of the certification, and the
scalability of the proposed dual certifiers to large problems, beyond the reach
of current SDP solvers.

本文提出了第一种通用且实用的框架，用于设计可证明的算法以应对大量离群值的情况下进行鲁棒几何感知，该算法使用截断最小二乘（TLS）代价函数，TLS 估计可以重新构制为多项式环上的优化，支持证明获得 TLS 问题的全局最小值，同时也可以使用斯内尔定理进行基础缩减，使用 SOS 松弛的双优化认证器，大大减小了 SDP 优化问题的复杂度，解决了当前 SDP 求解器无法解决的大规模问题。