Estimating the rigid transformation between two LiDAR scans through putative
3D correspondences is a typical point cloud registration paradigm. Current 3D
feature matching approaches commonly lead to numerous outlier correspondences,
making outlier-robust registration techniques indispensable. Many recent
studies have adopted the branch and bound (BnB) optimization framework to solve
the correspondence-based point cloud registration problem globally and
deterministically. Nonetheless, BnB-based methods are time-consuming to search
the entire 6-dimensional parameter space, since their computational complexity
is exponential to the dimension of the solution domain. In order to enhance
algorithm efficiency, existing works attempt to decouple the 6 degrees of
freedom (DOF) original problem into two 3-DOF sub-problems, thereby reducing
the dimension of the parameter space. In contrast, our proposed approach
introduces a novel pose decoupling strategy based on residual projections,
effectively decomposing the raw problem into three 2-DOF rotation search
sub-problems. Subsequently, we employ a novel BnB-based search method to solve
these sub-problems, achieving efficient and deterministic registration.
Furthermore, our method can be adapted to address the challenging problem of
simultaneous pose and correspondence registration (SPCR). Through extensive
experiments conducted on synthetic and real-world datasets, we demonstrate that
our proposed method outperforms state-of-the-art methods in terms of
efficiency, while simultaneously ensuring robustness.

通过残差投影提出一种基于 BnB 的搜索方法，将 6 自由度的刚性变换问题分解为三个 2 自由度旋转搜索子问题，实现高效和确定性的点云配准

基于残差投影的高效确定性点云配准搜索策略

Efficient and Deterministic Search Strategy Based on Residual  Projections for Point Cloud Registration

A common challenge faced in practical supervised learning, such as medical
image processing and robotic interactions, is that there are plenty of tasks
but each task cannot afford to collect enough labeled examples to be learned in
isolation. However, by exploiting the similarities across those tasks, one can
hope to overcome such data scarcity. Under a canonical scenario where each task
is drawn from a mixture of k linear regressions, we study a fundamental
question: can abundant small-data tasks compensate for the lack of big-data
tasks? Existing second moment based approaches show that such a trade-off is
efficiently achievable, with the help of medium-sized tasks with
$\Omega(k^{1/2})$ examples each. However, this algorithm is brittle in two
important scenarios. The predictions can be arbitrarily bad (i) even with only
a few outliers in the dataset; or (ii) even if the medium-sized tasks are
slightly smaller with $o(k^{1/2})$ examples each. We introduce a spectral
approach that is simultaneously robust under both scenarios. To this end, we
first design a novel outlier-robust principal component analysis algorithm that
achieves an optimal accuracy. This is followed by a sum-of-squares algorithm to
exploit the information from higher order moments. Together, this approach is
robust against outliers and achieves a graceful statistical trade-off; the lack
of $\Omega(k^{1/2})$-size tasks can be compensated for with smaller tasks,
which can now be as small as $O(\log k)$.

通过利用任务之间的相似性，甚至用较小的任务来弥补缺少大规模数据任务的不足，提出了一种鲁棒的基于谱方法的算法，同时具备对异常值的鲁棒性和优良的统计折衷。

混合线性回归小批量的鲁棒元学习

Robust Meta-learning for Mixed Linear Regression with Small Batches

We study the efficient learnability of high-dimensional Gaussian mixtures in
the outlier-robust setting, where a small constant fraction of the data is
adversarially corrupted. We resolve the polynomial learnability of this problem
when the components are pairwise separated in total variation distance.
Specifically, we provide an algorithm that, for any constant number of
components $k$, runs in polynomial time and learns the components of an
$\epsilon$-corrupted $k$-mixture within information theoretically near-optimal
error of $\tilde{O}(\epsilon)$, under the assumption that the overlap between
any pair of components $P_i, P_j$ (i.e., the quantity $1-TV(P_i, P_j)$) is
bounded by $\mathrm{poly}(\epsilon)$.
Our separation condition is the qualitatively weakest assumption under which
accurate clustering of the samples is possible. In particular, it allows for
components with arbitrary covariances and for components with identical means,
as long as their covariances differ sufficiently. Ours is the first polynomial
time algorithm for this problem, even for $k=2$.
Our algorithm follows the Sum-of-Squares based proofs to algorithms approach.
Our main technical contribution is a new robust identifiability proof of
clusters from a Gaussian mixture, which can be captured by the constant-degree
Sum of Squares proof system. The key ingredients of this proof are a novel use
of SoS-certifiable anti-concentration and a new characterization of pairs of
Gaussians with small (dimension-independent) overlap in terms of their
parameter distance.

研究了在高维高斯混合假设下，少量数据受到对手损坏的情况下的高效可学习性，提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时，该问题是可多项式学习的；这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法，并使用基于 Sum-of-Squares 证明算法的技术，提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。

任意可簇合高斯混合模型的鲁棒学习

Robustly Learning any Clusterable Mixture of Gaussians

We develop a new family of convex relaxations for $k$-means clustering based
on sum-of-squares norms, a relaxation of the injective tensor norm that is
efficiently computable using the Sum-of-Squares algorithm. We give an algorithm
based on this relaxation that recovers a faithful approximation to the true
means in the given data whenever the low-degree moments of the points in each
cluster have bounded sum-of-squares norms.
We then prove a sharp upper bound on the sum-of-squares norms for moment
tensors of any distribution that satisfies the \emph{Poincare inequality}. The
Poincare inequality is a central inequality in probability theory, and a large
class of distributions satisfy it including Gaussians, product distributions,
strongly log-concave distributions, and any sum or uniformly continuous
transformation of such distributions.
As an immediate corollary, for any $\gamma > 0$, we obtain an efficient
algorithm for learning the means of a mixture of $k$ arbitrary \Poincare
distributions in $\mathbb{R}^d$ in time $d^{O(1/\gamma)}$ so long as the means
have separation $\Omega(k^{\gamma})$. This in particular yields an algorithm
for learning Gaussian mixtures with separation $\Omega(k^{\gamma})$, thus
partially resolving an open problem of Regev and Vijayaraghavan
\citet{regev2017learning}.
Our algorithm works even in the outlier-robust setting where an $\epsilon$
fraction of arbitrary outliers are added to the data, as long as the fraction
of outliers is smaller than the smallest cluster. We, therefore, obtain results
in the strong agnostic setting where, in addition to not knowing the
distribution family, the data itself may be arbitrarily corrupted.

基于平方和范数的 $k$-means 聚类的凸松弛算法及其学习算法，能够学习高斯混合物的均值。