| dc.description.abstract | In this thesis, we consider the rigid registration problem, which arises in applications such as
sensor network localization, multiview registration, and protein structure determination. The
abstract setup for this problem is as follows. We are given a collection of N labelled points in
d-dimensional Euclidean space. There are M observers, each of whom observes a subset of
points and assigns coordinates to them in their local frame of reference. For each observer, we
know which points they observe, and the (possibly noisy) local coordinates assigned to these
points. Based on this information, we wish to infer the global coordinates of the N points. We
investigate the following questions in this context:
1. Uniqueness: Suppose that the local coordinates are noiseless. In this case, we know that
the true global coordinates are a solution of the problem. But is this the only solution?
We use results from graph rigidity theory to give a necessary and sufficient condition
for the problem to have a unique solution. In two-dimensional space, this leads to a
particularly efficient connectivity-based test for uniqueness.
2. Tightness of a convex relaxation: In general, when the local coordinates are noisy, we
use least squares fitting to estimate the global coordinates. After a suitable reduction,
this can be posed as a rank-constrained semidefinite program (REG-SDP). Dropping
the rank-constraint yields a convex relaxation, which has been empirically observed to
solve REG-SDP when the noise is below a certain threshold. Motivated by an analysis
of Bandeira et al [1], we offer an explanation of this phenomenon by analyzing the
Lagrange dual of the relaxed problem.
3. Convergence of an iterative solver: Instead of working with a convex relaxation, we can
try directly solving REG-SDP by appropriately splitting the constraint set, and formally
applying the alternating direction method of multipliers (ADMM). Empirically, this
nonconvex ADMM algorithm has been demonstrated to perform well in the context
of multiview registration. We analyze convergence of the iterates generated by this
algorithm, and show how noise in the measurements affects convergence behavior. | en_US |
