Euclidean distance matrix completion problems
- 1 October 2012
- journal article
- research article
- Published by Informa UK Limited in Optimization Methods and Software
- Vol. 27 (4-5), 695-717
- https://doi.org/10.1080/10556788.2011.643888
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
This publication has 34 references indexed in Scilit:
- Euclidean distance matrices, semidefinite programming and sensor network localizationPortugaliae Mathematica, 2011
- Modified Cholesky algorithms: a catalog with new approachesMathematical Programming, 2007
- OPT++ACM Transactions on Mathematical Software, 2007
- The Protein Data BankNucleic Acids Research, 2000
- An evaluation of computational strategies for use in the determination of protein structure from distance constraints obtained by nuclear magnetic resonanceProgress in Biophysics and Molecular Biology, 1991
- Conformational analysis by scaled energy embeddingJournal of Computational Chemistry, 1984
- Conformational analysis by energy embeddingJournal of Computational Chemistry, 1982
- Some distance properties of latent root and vector methods used in multivariate analysisBiometrika, 1966
- A Theorem on Boolean MatricesJournal of the ACM, 1962
- Remarks to Maurice Frechet's Article ``Sur La Definition Axiomatique D'Une Classe D'Espace Distances Vectoriellement Applicable Sur L'Espace De HilbertAnnals of Mathematics, 1935