Semidefinite relaxations for optimization problems over rotation matrices

Optimization problems with variables constrained to be in SO(d)-orthogonal matrices with determinant one-arise in attitude estimation, molecular imaging, and computer vision applications, among others. Recently it has been shown that the convex hull of SO(d) can be described in terms of linear matrix inequalities. This allows us to devise new semidefinite programming-based reformulations and relaxations of problems involving rotation matrices. In this paper we illustrate the use of these techniques for two different types of optimization problems over SO(d). The first type of problem arises in jointly estimating the attitude and spin-rate of a spin-stabilized satellite. We show how to exactly reformulate such problems as semidefinite programs. The second type of problem arises when estimating the orientations of a network of objects (such as cameras, satellites or molecules) from noisy relative orientation measurements. For this class of problems we formulate new semidefinite relaxations that are tighter than those existing in the literature, and show that they are exact when the underlying graph is a tree.