Euclidean distance matrix completion via semidefinite facial reduction
From Wikimization
(→Euclidean distance matrix completions (EDMC), background) |
(→Euclidean distance matrix completions (EDMC), background) |
||
Line 11: | Line 11: | ||
<center><math>\mathcal K(Y)_{ij} := Y_{ii} + Y_{jj} - 2Y_{ij} ~~\mbox{for all}~ i,j = 1, \ldots, n</math>,</center> | <center><math>\mathcal K(Y)_{ij} := Y_{ii} + Y_{jj} - 2Y_{ij} ~~\mbox{for all}~ i,j = 1, \ldots, n</math>,</center> | ||
- | we have that <math> \mathcal K(\mathcal S^n_+) = \mathcal E^n</math>. <math>\mathcal K</math> is a one-one linear transformation between the ''centered | + | we have that <math> \mathcal K(\mathcal S^n_+) = \mathcal E^n</math>. Note that <math>\mathcal K</math> is a one-one linear transformation between the ''centered symmetric matrices'', <math>S \in \mathcal S_c,</math> and the ''hollow matrices'' <math>\mathcal S_H</math>, where centered means row (and column) sums are all zero, and hollow means that the diagonal is zero. |
<p> | <p> | ||
A matrix <math>D \in \mathcal S^n</math> is a Euclidean distance matrix with embedding dimension <math>r\,</math> if and only if there exists <math>P \in \mathbb R^{n \times r}</math> such that <math>D = \mathcal K(PP^T).</math> | A matrix <math>D \in \mathcal S^n</math> is a Euclidean distance matrix with embedding dimension <math>r\,</math> if and only if there exists <math>P \in \mathbb R^{n \times r}</math> such that <math>D = \mathcal K(PP^T).</math> |
Revision as of 08:46, 3 January 2011
Euclidean distance matrix completions (EDMC), background
EDMC is a fundamental problem of distance geometry, (FPDG). Let be the vector space of symmetric matrices equipped with the trace inner product, ; let , the set of Euclidean distance matrices, i.e. , for points , with embedding dimension ; and let be the set (convex cone) of (symmetric) positive semidefinite matrices. Defining by
we have that . Note that is a one-one linear transformation between the centered symmetric matrices, and the hollow matrices , where centered means row (and column) sums are all zero, and hollow means that the diagonal is zero.
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