Euclidean distance matrix completion problems

Abstract

A Euclidean distance matrix (EDM) 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 an EDM.

We survey three different approaches to solving the EDMCP. We advocate expressing the EDMCP as a non-convex 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é and Wu. It also solves the 12 much more difficult protein fragment problems introduced by Hendrickson, and the six larger protein problems introduced by Grooms, Lewis and Trosset.

Keywords:

• distance geometry
• Euclidean distance matrices
• global optimization
• dimensionality relaxation
• modified Cholesky factorizations
• molecular conformation

AMS Subject Classifications :

• 49M15
• 65K05
• 90C26
• 92E10

Acknowledgements

We thank the Department of Computer Science and Engineering and the Minnesota Supercomputing Institute, University of Minnesota for having provided the computer resources for experiments. We are grateful to Yousef Saad for helpful discussions on dimensionality reduction techniques, to Che-Rung Lee for help with OPT++, to David Fushman for discussions on molecular biology and to the referees for helpful comments on the presentation. This work was supported in part by NSF Grant CCF 0514213 and DOE Grant DESC0002218.

Notes

Some authors define an EDM Δ by , so our D is their , where ‘ˆ’ denotes Hadamard (elementwise) product.

Note that the reported function evaluations count only those used in the OPT++ solvers 24 and do not include the 100 function evaluations for each initialization to select the pre-EDM in Algorithm 2. The cost of the eigencomputation in Algorithm 1, invoked by Algorithm 2, is also omitted in the tables. Neither of these neglected costs is significant, compared to the computational cost of the optimization algorithms.