  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. Consequently, we focus on Riemannian gradient descent for
minimization of the error and obtain a sufficient condition on an alignment for
the algorithm to converge (locally) linearly to it. 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 the non-degeneracy of a perfect alignment is equivalent to the
local rigidity of the resulting realization. By specializing the
characterization of a non-degenerate alignment to the noiseless setting, we
obtain necessary and sufficient conditions on the overlapping structure of the
views for a locally rigid realization. Similar results are also obtained in the
context of global rigidity.
