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 求解器无法解决的大规模问题。

一环统治全局：具有离群点的可验证强鲁棒性几何感知

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

We consider a parametric family of quadratically constrained quadratic
programs (QCQP) and their associated semidefinite programming (SDP)
relaxations. Given a nominal value of the parameter at which the SDP relaxation
is exact, we study conditions (and quantitative bounds) under which the
relaxation will continue to be exact as the parameter moves in a neighborhood
around the nominal value. Our framework captures a wide array of statistical
estimation problems including tensor principal component analysis, rotation
synchronization, orthogonal Procrustes, camera triangulation and resectioning,
essential matrix estimation, system identification, and approximate GCD. Our
results can also be used to analyze the stability of SOS relaxations of general
polynomial optimization problems.

研究了二次约束二次规划及其半定松弛的一个参数化族，并给出了在参数值改变时半定松弛的精确性条件，在估计问题中有广泛应用，并可用于分析一般多项式优化问题的松弛稳定性。

半正定松弛局部稳定性

On the local stability of semidefinite relaxations

Given a large data matrix $A\in\mathbb{R}^{n\times n}$, we consider the
problem of determining whether its entries are i.i.d. with some known marginal
distribution $A_{ij}\sim P_0$, or instead $A$ contains a principal submatrix
$A_{{\sf Q},{\sf Q}}$ whose entries have marginal distribution $A_{ij}\sim
P_1\neq P_0$. As a special case, the hidden (or planted) clique problem
requires to find a planted clique in an otherwise uniformly random graph.
Assuming unbounded computational resources, this hypothesis testing problem
is statistically solvable provided $|{\sf Q}|\ge C \log n$ for a suitable
constant $C$. However, despite substantial effort, no polynomial time algorithm
is known that succeeds with high probability when $|{\sf Q}| = o(\sqrt{n})$.
Recently Meka and Wigderson \cite{meka2013association}, proposed a method to
establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy.
Here we consider the degree-$4$ SOS relaxation, and study the construction of
\cite{meka2013association} to prove that SOS fails unless $k\ge C\,
n^{1/3}/\log n$. An argument presented by Barak implies that this lower bound
cannot be substantially improved unless the witness construction is changed in
the proof. Our proof uses the moments method to bound the spectrum of a certain
random association scheme, i.e. a symmetric random matrix whose rows and
columns are indexed by the edges of an Erd\"os-Renyi random graph.

提出一种基于低阶半正定松弛和矩阵谱的方法，用于在特定条件下解决隐含团问题的下界证明。