Euclidean distance matrix completion via semidefinite facial reduction

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(→Euclidean distance matrix completions (EDMC), background)
(→Euclidean distance matrix completions (EDMC), background)
Line 6: Line 6:
EDMC is a ''fundamental problem of distance geometry, (FPDG)''.
EDMC is a ''fundamental problem of distance geometry, (FPDG)''.
-
Let <math>\mathcal S^n</math> be the vector space of symmetric matrices equipped with the trace inner product, <math>trace ST</math>; let <math>D \in \mathcal E^n</math>, the set of <math>n \times n</math> Euclidean distance matrices, i.e. <math>D_{ij}=|| p_i-p_j||^2</math>
+
Let <math>\mathcal S^n</math> be the vector space of symmetric matrices equipped with the trace inner product, <math>trace ST</math>; let <math>D \in \mathcal E^n</math>, the set of <math>n \times n</math> Euclidean distance matrices, i.e. <math>D_{ij}=|| p_i-p_j||^2</math>, for points <math>p_i\in \mathcal R^r, i=1,...n</math>
and let <math>\mathcal S^n_+</math> be the set of (symmetric) positive semidefinite matrices. Defining <math>\mathcal K : \mathcal S^n \rightarrow \mathcal S^n</math> by
and let <math>\mathcal S^n_+</math> be the set of (symmetric) positive semidefinite matrices. Defining <math>\mathcal K : \mathcal S^n \rightarrow \mathcal S^n</math> by

Revision as of 08:22, 3 January 2011

Nathan Krislock

Henry Wolkowicz

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: 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 \mathcal R^r, i=1,...n and let LaTeX: \mathcal S^n_+ be the set 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. 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\,.

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

Using the substitution LaTeX: Y = PP^T\,, and relaxing the 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

LaTeX: \mathbf{face} \left\{ Y \in \mathcal S^n_+ : \mathcal{K}(Y[C]) = D[C], Ye = 0 \right\} = U \mathcal S^{n-|C|+r}_+ U^T.
Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Euclidean_distance_matrix_completion_via_semidefinite_facial_reduction"
Personal tools