Title: Approximate and Exact Completion Problems for Euclidean Distance Matrices using Semidefinite Programming

(slides)

A partial pre-distance matrix A is a matrix with zero diagonal and with certain elements fixed to given nonnegative values; the other elements are considered free. The EDM completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, EDM. The nearest (or approximate) EDM problem is to find a Euclidean distance matrix that is nearest in the Frobenius norm to the matrix A, when the free variables are discounted.

Applications for EDM include: molecular conformation problems in chemistry; multidimensional scaling and multivariate analysis problems in statistics; genetics, geography, etc...

We present two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal-dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant.

We conclude with numerical tests.