Euclidean distance matrix completion via semidefinite facial reduction

From Wikimization

Revision as of 12:41, 3 January 2011 by Hwolkowi (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

1 Euclidean distance matrix completions (EDMC), background
- 1.1 Properties of
2 Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem
3 Single Clique Facial Reduction Theorem [1]

Euclidean distance matrix completions (EDMC), background

EDMC is a fundamental problem of distance geometry, (FPDG). Let $LaTeX: \mathcal S^n$ be the vector space of symmetric matrices equipped with the trace inner product, $LaTeX: \langle S, T \rangle = \mathrm{trace}(ST)$ ; let $LaTeX: D \in \mathcal E^n$ , the set of $LaTeX: n \times n$ Euclidean distance matrices, i.e. $LaTeX: D_{ij}=|| p_i-p_j||^2$ , for points $LaTeX: p_i\in \mathbb R^r, i=1,...n$ , with embedding dimension $LaTeX: r$ ; and, let $LaTeX: \mathcal S^n_+$ be the set (convex cone) of (symmetric) positive semidefinite matrices. Defining $LaTeX: \mathcal K : \mathcal S^n \rightarrow \mathcal S^n$ by

$LaTeX: \mathcal K(Y)_{ij} := Y_{ii} + Y_{jj} - 2Y_{ij} ~~\mbox{for all}~ i,j = 1, \ldots, n$ ,

we have that $LaTeX: \mathcal K(\mathcal S^n_+) = \mathcal E^n$ . Note that $LaTeX: \mathcal K$ is a one-one linear transformation between the centered symmetric matrices, $LaTeX: S \in \mathcal S_c,$ and the hollow matrices $LaTeX: \mathcal S_H$ , where centered means row (and column) sums are all zero, and hollow means that the diagonal is zero.

A matrix $LaTeX: D \in \mathcal S^n$ is a Euclidean distance matrix with embedding dimension $LaTeX: r\,$ if and only if there exists $LaTeX: P \in \mathbb R^{n \times r}$ such that $LaTeX: D = \mathcal K(PP^T).$ Suppose $LaTeX: D\,$ is a partial Euclidean distance matrix with embedding dimension $LaTeX: r\,$ . The low-dimensional Euclidean distance matrix completion problem is

$LaTeX: \begin{array}{rl}\mbox{find}&P \in \mathbb R^{n \times r} \\ \mbox{s.t.}&H \circ \mathcal K(PP^T) = H \circ D \\ & P^Te = 0, \end{array}$

where $LaTeX: e \in \mathbb R^n$ is the vector of all ones, and $LaTeX: H\,$ is the adjacency matrix of the graph $LaTeX: G = (V,E)\,$ associated with the partial Euclidean distance matrix $LaTeX: D\.$

Properties of $LaTeX: \mathcal K$

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

Using the substitution $LaTeX: Y = PP^T\,,$ and relaxing the (NP-hard) condition that $LaTeX: \mathrm{rank}(Y) = r\,,$ we obtain the semidefinite programming relaxation

$LaTeX: \begin{array}{rl}\mbox{find}& Y \in \mathcal S^n_+ \\ \mbox{s.t.}& H \circ \mathcal K(Y) = H \circ D \\ & Ye = 0. \end{array}$

Single Clique Facial Reduction Theorem [1]

Let $LaTeX: C \subseteq V$ be a clique in the graph $LaTeX: G\,$ such that the embedding dimension of $LaTeX: D[C]\,$ is $LaTeX: r\,.$ Then there exists $LaTeX: U \in \mathbb R^{n \times (n-|C|+r)}$ such that