This paper reports on a system for estimating the alignment between robotic trajectories under constrained communications. Multi-agent collaborative inspection and navigation tasks depend on the ability to determine an alignment between robotic trajectories or maps. The properties of the underwater environment make determining such an alignment difficult because of extreme limitations on communication and the lack of absolute position measurements such as GPS. In this paper, we propose a method that takes advantage of convex relaxation techniques to determine an alignment between robotic trajectories based on sparse observations of a low-dimensional underlying feature space. We use a linear approximation of the l2-norm to approximately enforce that the estimated transformation is an element of SO(2). Because the relaxed optimization problem is linear, we can take advantage of existing convex optimization libraries, which do not require an initial estimate of relative pose. In addition, because the proposed method does not need to perform data association, we can align trajectories using low-dimensional feature vectors and can thus decrease the amount of data that must be transferred between agents by several orders of magnitude when compared to image feature descriptors such as SIFT and SURF. We evaluate the proposed method on simulated datasets and apply it to real-world data collected during autonomous ship hull inspection field trials.