Solving Euclidean distance matrix completion problems via semidefinite programming

Solving Euclidean distance matrix completion problems via semidefinite programming

0.00 Avg rating0 Votes
Article ID: iaor20003767
Country: Netherlands
Volume: 12
Issue: 1/2/3
Start Page Number: 13
End Page Number: 30
Publication Date: Jan 1999
Journal: Computational Optimization and Applications
Authors: , ,
Keywords: matrices, computational analysis
Abstract:

Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix. In this paper, we solve the EDMCP by generalizing 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 problem. Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed.

Reviews

Required fields are marked *. Your email address will not be published.