Euclidean distance matrix completion via semidefinite facial reduction
From Wikimization
(Difference between revisions)
m (Protected "Euclidean distance matrix completion via semidefinite facial reduction" [edit=autoconfirmed:move=autoconfirmed]) |
Revision as of 20:20, 2 December 2009
Euclidean distance matrix completion
Let be the set of Euclidean distance matrices, and let be the set of (symmetric) positive semidefinite matrices. Defining by
we have that A matrix is a Euclidean distance matrix with embedding dimension if and only if there exists such that
Suppose is a partial Euclidean distance matrix with embedding dimension . The low-dimensional Euclidean distance matrix completion problem is
where is the vector of all ones, and is the adjacency matrix of the graph associated with the partial Euclidean distance matrix
Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem
Using the substitution and relaxing the condition that we obtain the semidefinite programming relaxation
Single Clique Facial Reduction Theorem [1]
Let be a clique in the graph such that the embedding dimension of is Then there exists such that