Solving Euclidean distance matrix completion problems via semidefinite programming

Given a partial symmetric matrix A with only certain elements specified, th e Euclidean distance matrix completion problem (EDMCP) is to find the unspe cified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by ge neralizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming prob lem (SDP). Numerical results are included which illustrate the efficiency a nd robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed.