Non-degenerate Rigid Alignment in a Patch Framework

Abstract. Given a set of overlapping local views (patches) of a dataset, we consider the problem of finding a rigid alignment of the views that minimizes a 2-norm based alignment error. In general, the views are noisy and a perfect alignment may not exist. In this work, we characterize the non-degeneracy of an alignment in the noisy setting based on the kernel and positivity of a certain matrix. This leads to a polynomial time algorithm for testing the non-degeneracy of a given alignment. Subsequently, we focus on Riemannian gradient descent for minimizing the alignment error, providing a sufficient condition on an alignment for the algorithm to converge (locally) linearly to it. Additionally, we provide an exact recovery and noise stability analysis of the algorithm. In the case of noiseless views, a perfect alignment exists, resulting in a realization of the points that respects the geometry of the views. Under a mild condition on the views, we show that a non-degenerate perfect alignment characterizes the infinitesimally rigidity of a realization and thus the local rigidity of a generic realization. By specializing the non-degeneracy conditions to the noiseless case, we derive necessary and sufficient conditions on the overlapping structure of the views for a perfect alignment to be non-degenerate and, equivalently, for the resulting realization to be infinitesimally rigid.