A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partially-specified symmetric matrix $A$ with zero diagonal, the Euclidean distance matrix completion problem (EDMCP) is to determine the unspecified entries to make $A$ a Euclidean distance matrix. We survey three different approaches to solving the EDMCP. We advocate expressing the EDMCP as a nonconvex optimization problem using the particle positions as variables and solving using a modified Newton or quasi-Newton method. To avoid local minima, we develop a randomized initialization technique that involves a nonlinear version of the classical multidimensional scaling, and a dimensionality relaxation scheme with optional weighting. Our experiments show that the method easily solves the artificial problems introduced by Mor\'{e} and Wu. It also solves the 12 much more difficult protein fragment problems introduced by Hendrickson, and the 6 larger protein problems introduced by Grooms, Lewis, and Trosset.

## Citation

unpublished manuscript, Department of Computer Science and Engineering, University of Minnesota, and Department of Computer Science, University of Maryland, June 2010.