Matrix Completion and Semidefinite Programming 

   Henry Wolkowicz
 Department of Combinatorics and Optimization
 University of Waterloo
 Waterloo, Ontario  N2L 3G1


We look at both the
positive semidefinite completion problem
(finding numbers for the unspecified (free)
elements of a symmetric matrix in order to make it positive
semidefinite) and the very closely related Euclidean distance
matrix completion problem.
By transforming these problems into
approximate completion problems, we are able to find
efficient solution techniques
using semidefinite programming and interior-point methods.