  Point-set registration is a classical image processing problem that looks for
the optimal transformation between two sets of points. In this work, we analyze
the impact of outliers when finding the optimal rotation between two point
clouds. The presence of outliers motivates the use of least unsquared
deviation, which is a non-smooth minimization problem over non-convex domain.
We compare approaches based on non-convex optimization over special orthogonal
group and convex relaxations. We show that if the fraction of outliers is
larger than a certain threshold, any naive convex relaxation fails to recover
the ground truth rotation regardless of the sample size and dimension. In
contrast, minimizing the least unsquared deviation directly over the special
orthogonal group exactly recovers the ground truth rotation for any level of
corruption as long as the sample size is large enough. These theoretical
findings are supported by numerical simulations.
