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 th e distance matrix may be restricted and the known dissimilarities may be pe rmitted to vary subject to bound constraints. This problem can be formulate d as an optimization problem for which the global minimum is zero if and on ly if completion is possible. The optimization problem is derived in a very natural way from an embedding theorem in classical distance geometry and f rom the classical approach to multidimensional scaling. It belongs to a gen eral family of problems studied by Trosset (Technical Report 97-3, Departme nt of Computational & Applied Mathematics-MS 134, Rice University, Houston, TX 77005-1892, 1997) and can be formulated as a nonlinear programming prob lem with simple bound constraints. Thus, this approach provides a construct ive technique for obtaining approximate solutions to a general class of dis tance matrix completion problems.