Nuclear magnetic resonance (NMR) spectroscopy is the most-used technique for protein structure determination besides X-ray crystallography. Typically the 3D structure of a protein is obtained through finding the coordinates of atoms subject to pairwise distance constraints. However, for large proteins there are usually insufficient distance measurements and the structure determination problem becomes ill-posed. Residual dipolar coupling (RDC) measurements provide additional geometric information on the angles between bond directions and the principal-axis-frame. The optimization problem involving RDC is non-convex and we present a novel convex programming relaxation to it by incorporating quaternion algebra. In simulations we attain the Cramer-Rao lower bound with relatively efficient running time. From real data, we obtain the protein backbone structure for ubiquitin with 1 Angstrom resolution.  This is joint work with Amit Singer and David Cowburn.