\shrink
\section{Introduction}
\label{sec:introduction}
\shrink
\emph{\Perception}, estimating unknown geometric models (\eg~rotations, poses, 3D structure) from visual measurements (\eg~images and point clouds), is a fundamental problem in computer vision, robotics, and graphics. 

It finds extensive applications to object detection and localization~\cite{Yang19rss-teaser,Yang20arxiv-teaser}, motion estimation and 3D reconstruction~\cite{Choi15cvpr-robustReconstruction,Zhang15icra-vloam}, simultaneous localization and mapping~\cite{Cadena16tro-SLAMsurvey,Rosen18ijrr-sesync}, shape analysis~\cite{Maron16tog-PMSDP,Ovsjanikov12TOG-functionalMaps}, virtual and augmented reality~\cite{Klein07ismar-PTAM}, and medical imaging~\cite{Audette00mia-surveyMedical}.

A common formulation for \perception resorts to optimization to perform estimation:
\bea

\min_{\vxx \in \calX}  \;\; \textstyle  \sumallpoints \rho \left( r\left( \vxx, \measured_i \right) \right), \label{eq:generalPerception}
\eea
where $\measured_i \in \setmeasured,i=1,\dots,N,$ are the visual measurements, 
$\vxx \in \calX \subseteq \Real{n}$ is the to-be-estimated geometric model, $r: \calX \times \setmeasured \rightarrow \Real{}_+$ is the \emph{residual  function} that quantifies the disagreement between each measurement $\measured_i$ and the geometric model $\vxx$, 
and $\rho: \Real{}_+ \rightarrow \Real{}_+$ is the \emph{cost function} that determines how residuals are penalized. When the distribution of the 
measurement noise is known, maximum likelihood estimation provides a systematic way to design $\rho$; for instance, assuming Gaussian noise leads to the popular \emph{least squares} cost function $\rho(r) = r^2$~\cite{Horn87josa,Poggio85nature-computationalVision,Hartley04}. 

However, in practice, \emph{a large amount of} measurements, called \emph{outliers}, depart from the assumed noise distribution (\eg~due to sensor failure or incorrect data association). Therefore, a \emph{robust} cost function, such as the $\ell_1$-norm~\cite{Wang13ima}, Huber~\cite{Huber81}, Geman-McClure~\cite{Yang20ral-GNC}, and truncated least squares~\cite{Yang19iccv-QUASAR}, is necessary to prevent the outliers from corrupting the estimate. Both the constraints --defining the domain $\calX$-- 

and the objective function in~\eqref{eq:generalPerception}  are typically nonconvex in \perception problems.


Solving \perception with \emph{optimality guarantees} is of paramount importance for {safety-critical} and {high-integrity} applications such as autonomous driving and space robotics. Indeed, suboptimal solutions of~\eqref{eq:generalPerception} typically correspond to poor or outlier-contaminated estimates~\cite{Yang20ral-GNC}. 
However, obtaining globally optimal solutions, particularly in the presence of outliers, remains a challenging task. Related work is divided into (i) \emph{fast heuristics},~\eg~\ransac~\cite{Fischler81} and graduated non-convexity (\GNC)~\cite{Yang20ral-GNC}, that are efficient but brittle against high outlier rates and offer no optimality guarantees, and (ii) \emph{global solvers},~\eg~{Branch and Bound}~\cite{Izatt17isrr-MIPregistration,Yang16pami-goicp}, that guarantee optimality but run in worst-case exponential time. Recently, \emph{certifiable algorithms}~\cite{Bandeira16crm,Yang20arxiv-teaser,Boumal16nips,Carlone16tro-duality2D} are rising as a new paradigm for solving \perception with both \emph{a posteriori} optimality guarantees 
and polynomial-time complexity.

A popular framework for constructing a certifiable algorithm requires (i) a \emph{tight} \emph{convex relaxation} of problem~\eqref{eq:generalPerception}; (ii) a \emph{fast heuristics} that computes a candidate solution to problem~\eqref{eq:generalPerception} with high probability of success; and (iii) a fast \emph{duality-based} \emph{certifier} that verifies if the candidate solution is globally optimal for the relaxation.\footnote{Global optimality of the relaxation implies global optimality of problem~\eqref{eq:generalPerception} when the relaxation is tight.} However, although a growing body of tight convex relaxations

have been discovered for various instances of \perception \emph{without} outliers~\cite{Kahl07IJCV-GlobalOptGeometricReconstruction,Briales17cvpr-registration,Briales18cvpr-global2view,Rosen18ijrr-sesync,Eriksson18cvpr-strongDuality,Zhao20cvpr-certifiablyEssential,Yang20cvpr-shapeStar,Probst19ICCV-convexRelaxationNonminimal,Maron16tog-PMSDP,Chaudhury15Jopt-multiplePointCloudRegistration,Aholt12ECCV-qcqpTriangulation,Fredriksson12accv-rotationaveragingLagrangian,Agostinho2019arXiv-cvxpnpl,Giamou19ral-SDPExtrinsicCalibration,Heller14icra-handeyePOP,Wise20arXiv-certifiablyHandeye}, only a few (problem-specific) tight relaxations exist for \emph{outlier-robust} \perception~\cite{Yang19rss-teaser,Yang19iccv-QUASAR,Wang13ima,Lajoie19ral-DCGM,Carlone18ral-robustPGO2D}\optional{. Moreover, fast certifiers exist only when the dual variables can be computed in closed-form from KKT optimality conditions~\cite{Carlone16tro-duality2D,Eriksson18cvpr-strongDuality,Iglesias20cvpr-PSRGlobalOptimality,Garcia20arXiv-certifiableRelativePose}, except Yang~\etal~\cite{Yang20arxiv-teaser} proposed a certifier to numerically compute dual certificates in the case of an under-constrained KKT system.}{.} 

\input{fig-summary}

{\bf Contributions.} We contribute \final{the first} general and practical framework for designing certifiable algorithms for robust \perception with outliers \final{(Fig.~\ref{fig:summary})}. Our first contribution is to show that common \perception problems with the truncated least squares (\TLS) cost function can be reformulated as an optimization over the ring of polynomials, and \emph{Lasserre's hierarchy of moment relaxations}~\cite{Lasserre01siopt-LasserreHierarchy,lasserre10book-momentsOpt} is tight at the \emph{minimum relaxation order}, \finalLC{despite the strong non-convexity and non-smoothness of the problem.} Our second contribution is to propose a \emph{basis reduction} technique, that exploits the structural \emph{sparsity} of the polynomials and significantly reduces the size of the semidefinite programs (SDP) resulting from moment relaxation, \finalLC{while surprisingly maintaining tightness of the relaxation.} These two contributions lead to the {first} set of \emph{certifiably robust} solvers for a broad class of \perception problems. 
While scaling better than the standard moment relaxation, these solvers still rely on existing SDP solvers, whose runtime restricts 
their use to small-scale problems (\eg~$N=20$). 

Therefore, our third contribution is to study the \emph{dual} sums-of-squares (SOS) relaxation and design fast \emph{dual optimality certifiers} that scale to realistic problem sizes (\eg~$N=100$). 
Our certifiers leverage \emph{Douglas–Rachford Splitting} (\DRS), \final{initialized by solving an SOS program with \emph{correlative sparsity}~\cite{Waki06jopt-SOSSparsity,Wang20arXiv-cs-tssos},} to compute a \emph{suboptimality} gap for any candidate solution, 
and possibly certify \emph{global optimality}

when the suboptimality is zero. 

\finalLC{Dual certifiers enhance existing heuristics (\eg~\ransac and \gnc) with a fast certification that asserts the quality of their estimates and rejects failure cases, thus enhancing trustworthiness in  safety-critical applications.} We demonstrate our tight relaxations and fast certifiers on several perception problems including single rotation averaging~\cite{Hartley13ijcv,Lee20arXiv-robustSRA}, image-based pose estimation (also called shape alignment)~\cite{Yang20ral-GNC}, point cloud registration~\cite{Yang19rss-teaser}, mesh registration~\cite{Briales17cvpr-registration}, and in a satellite pose estimation application~\cite{Chen19ICCVW-satellitePoseEstimation}.

{\bf Notation.} Let $\polyring$ be the ring of real-valued multivariate polynomials in $\{x_i\}_{i=1}^n$. 
Using standard notation~\cite{lasserre10book-momentsOpt}, we denote every $f \in \polyring$ as $f = \sum_{\valpha \in \calF} c(\valpha) \vxx^{\valpha}$, where $\calF \subseteq \nnint^n$ is a finite set of nonnegative integer exponents, $c(\valpha)$ are real coefficients, and $\vxx^\valpha \doteq x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ are standard monomials. The degree of a monomial $\vxx^{\valpha}$ is $\deg{\vxx^{\valpha}} \doteq \sum_{i=1}^n \alpha_i$, and the degree of a polynomial $f$ is $\deg{f} = \max\{\deg{\vxx^{\valpha}}: \valpha \in \calF\}$. 

We use $\monod{\vxx}$ (resp. $\monoleqd{\vxx}$) to denote the set of monomials with degree $d$ (resp. with degree up to $d$). We use $\dimbasis{n}{d} \doteq \nchoosek{n+d}{d}$ to denote the dimension of $\monoleqd{\vxx}$. Similarly, we use $\monoleq{\vxx}{\calF} \doteq \{\vxx^\valpha: \valpha \in \calF \}$ to denote the set of monomials with exponents in $\calF$, and we use $\dimbasis{}{\calF}$ to denote its dimension. 

We use $\sym^n$ to denote the set of $n \times n$ symmetric matrices, and $\psd^n$ for the set of symmetric positive semidefinite (PSD) matrices. We also write $\MA \succeq 0$ to indicate $\MA \in \psd^n$. 

For $\MA \in \sym^n$ we use $\svec{\MA}$ to denote its symmetric vectorization~\cite{Toh12handbook-SDPT3Implementation}.
A polynomial $q \in \polyring$ is a sums-of-squares (SOS) polynomial if and only if $q$ can be written as $q = \monoleq{\vxx}{\calF}\tran \MQ \monoleq{\vxx}{\calF}$ for some monomial basis $\monoleq{\vxx}{\calF}$ and PSD matrix $\MQ \succeq 0$, in which case $q \geq 0, \forall \vxx \in \Real{n}$.
{"config": "arxiv", "file": "2006.06769/introduction.tex"}