On the Set of Euclidean Distance Matrix Completions

Henry Wolkowicz, University of Waterloo

work with Abdo Alfakih, University of Windsor

A partial pre-distance matrix W=(wij) 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...

In this talk we look at the geometry of completions of W.