Semidefinite Programming and Euclidean Distance Matrix Completions

   Henry Wolkowicz (with Abdo Alfakih)
 Department of Combinatorics and Optimization
 University of Waterloo
 Waterloo, Ontario  N2L 3G1


Abstract:   

Suppose we are given a partial symmetric nonnegative matrix $A$
with zero diagonal, and certain elements fixed.
The Euclidean matrix completion problem consists in
finding numbers for the unspecified (free)
elements in order to make $A$ a Euclidean distance matrix.
These problems have many applications and
have been extensively studied.
Much is known in terms of existence of
completions. 

In this talk we will transform the problem into an
approximate completion problem.
We will show that this transformation allows for efficient solutions
using semidefinite programming and interior-point techniques.