English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose the first general and practical framework to design certifiablealgorithms for robust geometric perception in the presence of a large amount ofoutliers. We investigate the use of a truncated least squares (TLS) costfunction, which is known to be robust to outliers, but leads to hard,nonconvex, and nonsmooth optimization problems. Our first contribution is toshow that -for a broad class of geometric perception problems- TLS estimationcan be reformulated as an optimization over the ring of polynomials andLasserre's hierarchy of convex moment relaxations is empirically tight at theminimum relaxation order (i.e., certifiably obtains the global minimum of thenonconvex TLS problem). Our second contribution is to exploit the structuralsparsity of the objective and constraint polynomials and leverage basisreduction to significantly reduce the size of the semidefinite program (SDP)resulting from the moment relaxation, without compromising its tightness. Ourthird contribution is to develop scalable dual optimality certifiers from thelens of sums-of-squares (SOS) relaxation, that can compute the suboptimalitygap and possibly certify global optimality of any candidate solution (e.g.,returned by fast heuristics such as RANSAC or graduated non-convexity). Ourdual certifiers leverage Douglas-Rachford Splitting to solve a convexfeasibility SDP. Numerical experiments across different perception problems,including single rotation averaging, shape alignment, 3D point cloud and meshregistration, and high-integrity satellite pose estimation, demonstrate thetightness of our relaxations, the correctness of the certification, and thescalability of the proposed dual certifiers to large problems, beyond the reachof current SDP solvers.

One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers