Euclidean distance matrix completion problems

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...

Full description

Saved in:
Bibliographic Details
Published in:Optimization methods & software 2012-10, Vol.27 (4-5), p.695-717
Main Authors: Fang, Haw-ren, O'Leary, Dianne P.
Format: Article
Language:English
Subjects:
dimensionality relaxation
distance geometry
Euclidean distance matrices
global optimization
modified Cholesky factorizations
molecular conformation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1055-6788
1029-4937
DOI:10.1080/10556788.2011.643888