Theoretical and Algorithmic Aspects of Rigid Registration

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.