# Euclidean distance matrix completion via semidefinite facial reduction

### From Wikimization

(→Properties of <math>\mathcal K </math> [http://orion.math.uwaterloo.ca/~hwolkowi/henry/reports/edmapr04.pdf]) |
Current revision (15:30, 25 September 2016) (edit) (undo) (→Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem) |
||

Line 53: | Line 53: | ||

== Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem == | == Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem == | ||

- | Using the substitution <math>Y = PP^{\ | + | Using the substitution <math>Y = PP^{\text T}\,,</math> and relaxing the (NP-hard) condition that <math>{\text rank}(Y) = r\,,</math> we obtain the semidefinite programming relaxation |

- | <center><math>\begin{array}{rl} | + | <center><math>\begin{array}{rl}{\text find}& Y \in \mathcal S^n_+ \\ {\text s.t.}& H \circ \mathcal K(Y) = H \circ D \\ & Ye = 0. \end{array}</math></center> |

== Single Clique Facial Reduction Theorem [http://www.optimization-online.org/DB_HTML/2009/05/2297.html] == | == Single Clique Facial Reduction Theorem [http://www.optimization-online.org/DB_HTML/2009/05/2297.html] == |

## Current revision

## Contents |

## 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

### Properties of [1]

Let , where diag denotes the diagonal of the argument. Then alternatively, we can write

The adjoints of these linear transformations are

where Diag is the diagonal matrix formed from its argument and is the adjoint of diag. The Moore-Penrose generalized inverse is

where the matrix and the linear operator (orthogonal projection) . The orthogonal projections onto the range of and range of is given by

respectively. These are the hollow and centered subspaces of , respectively. The nullspaces of are the ranges of Diag, , respectively.

## Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem

Using the substitution and relaxing the (NP-hard) condition that we obtain the semidefinite programming relaxation

## Single Clique Facial Reduction Theorem [2]

Let be a clique in the graph such that the embedding dimension of is Then there exists such that