Distance Matrix Completion by Numerical Optimization

Consider the problem of determining whether or not a partial dissimilarity matrix can be completed to a Euclidean distance matrix. The dimension of the distance matrix may be restricted and the known dissimilarities may be permitted to vary subject to bound constraints. This problem, which naturally arises in the study of molecular conformation, can be formulated as an optimization problem. Completion is possible if and only if the global minimum of the optimization problem is zero; furthermore, using ideas from nonmetric multidimensional scaling, it is possible to construct a sequence of objective function values that is guaranteed to converge to the global minimum. Thus, this approach provides a constructive technique for obtaining approximate solutions to a very general class of distance matrix completion problems