  


Euclidean Distance Matrix Completion Problems
Hawren Fang(hrfangyahoo.com) Abstract: A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partiallyspecified 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 quasiNewton 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. Keywords: distance geometry, Euclidean distance matrices, global optimization, dimensionality relaxation, modified Cholesky factorizations, molecular conformation Category 1: Global Optimization (Applications ) Category 2: Applications  Science and Engineering (Chemical Engineering ) Citation: unpublished manuscript, Department of Computer Science and Engineering, University of Minnesota, and Department of Computer Science, University of Maryland, June 2010. Download: [PDF] Entry Submitted: 06/10/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  