Euclidean distance matrix completion via semidefinite facial reduction

From Wikimization

(Difference between revisions)

Current revision

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

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^{\rm{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}{\text find}&P \in \mathbb{R}^{n \times r} \\ {\text s.t.}&H \circ \mathcal K(PP^{\rm{T}}) = H \circ D \\ & P^{\rm{T}}e = 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$ [1]

Let $LaTeX: \mathcal D_e(Y):={\text diag}(Y)e^{\text T}+e{\text diag}(Y)^{\text T}$ , where diag denotes the diagonal of the argument. Then alternatively, we can write

$LaTeX: \mathcal K(Y) = \mathcal D_e(Y) -2Y.$

The adjoints of these linear transformations are

$LaTeX: <p>\mathcal D^*(D) = 2 {\text Diag} (De), \qquad \mathcal K^*(D) = 2 ({\text Diag} (De) -D), </p>$

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

$LaTeX: \mathcal K^\dagger(D) = -\frac 12 J \operatorname{offDiag} (D) J,$

where the matrix $LaTeX: J:=I-\frac 1n ee^{\rm{T}}$ and the linear operator (orthogonal projection) $LaTeX: \operatorname{offDiag}(D):=D-{\text Diag}{\text diag}(D)$ . The orthogonal projections onto the range of $LaTeX: \mathcal K$ and range of $LaTeX: \mathcal K^*$ is given by

$LaTeX: \mathcal K\mathcal K^\dagger (D)=\operatorname{offDiag}(D), \qquad <p>\mathcal K^\dagger \mathcal K (Y)=JYJ$ ,

respectively. These are the hollow and centered subspaces of $LaTeX: \mathcal S^n$ , respectively. The nullspaces of $LaTeX: \mathcal K, \mathcal K^\dagger$ are the ranges of Diag, $LaTeX: \mathcal D_e$ , respectively.

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

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

$LaTeX: \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}$

Single Clique Facial Reduction Theorem [2]

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^{\rm{T}}.$

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Euclidean_distance_matrix_completion_via_semidefinite_facial_reduction"

@@ Line 6: / Line 6: @@
 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>\langle S, T \rangle = \mathrm{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 \mathbb R^r, i=1,...n</math>, with embedding dimension <math>r</math>;
+Let <math>\mathcal S^n</math> be the vector space of symmetric matrices equipped with the trace inner product, <math>\langle S, T \rangle = \mathrm{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 \mathbb{R}^r, i=1,...n</math>, with embedding dimension <math>r</math>;
 and, let <math>\mathcal S^n_+</math> be the set (convex cone) of (symmetric) positive semidefinite matrices.  Defining <math>\mathcal K : \mathcal S^n \rightarrow \mathcal S^n</math> by
@@ Line 13: / Line 13: @@
 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>
-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^{\rm{T}}).</math>
 Suppose <math>D\,</math> is a partial Euclidean distance matrix with embedding dimension <math>r\,</math>.  The ''low-dimensional Euclidean distance matrix completion'' problem is
-<center><math>\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}</math></center>
+<center><math>\begin{array}{rl}{\text find}&P \in \mathbb{R}^{n \times r} \\ {\text s.t.}&H \circ \mathcal K(PP^{\rm{T}}) = H \circ D \\ & P^{\rm{T}}e = 0, \end{array}</math></center>
-where <math>e \in \mathbb R^n</math> is the vector of all ones, and <math>H\,</math> is the adjacency matrix of the graph <math>G = (V,E)\,</math> associated with the partial Euclidean distance matrix <math>D.</math>
+where <math>e \in \mathbb{R}^n</math> is the vector of all ones, and <math>H\,</math> is the adjacency matrix of the graph <math>G = (V,E)\,</math> associated with the partial Euclidean distance matrix <math>D.</math>
 ===Properties of <math>\mathcal K </math> [http://orion.math.uwaterloo.ca/~hwolkowi/henry/reports/edmapr04.pdf]===
 Let <math>
-\mathcal D_e(Y):=\operatorname{diag} (Y)e^T+e\operatorname{diag}(Y)^T
+\mathcal D_e(Y):={\text diag}(Y)e^{\text T}+e{\text diag}(Y)^{\text T}
 </math>, where diag denotes the diagonal of the argument. Then
 alternatively, we can write
@@ Line 31: / Line 31: @@
 The adjoints of these linear transformations are
 <center><math>
-\mathcal D^*(D) = 2 \operatorname Diag (De),
+\mathcal D^*(D) = 2 {\text Diag} (De),
 \qquad
-\mathcal K^*(D) = 2 (\operatorname Diag (De) -D),
+\mathcal K^*(D) = 2 ({\text Diag} (De) -D),
 </math></center>
 where Diag is the diagonal matrix formed from its argument and is the adjoint of diag. The Moore-Penrose generalized inverse is
 <center><math>\mathcal K^\dagger(D) = -\frac 12 J \operatorname{offDiag} (D) J,</math></center>
-where the matrix
+where the matrix  <math> J:=I-\frac 1n ee^{\rm{T}}</math>
-<math>
-J:=I-\frac 1n ee^T
-<\math>,
 and the linear operator (orthogonal projection)
+<math>\operatorname{offDiag}(D):=D-{\text Diag}{\text diag}(D)</math>. The orthogonal projections onto the range of <math>\mathcal K</math> and range of <math>\mathcal K^*</math> is given by
+<center><math>\mathcal K\mathcal K^\dagger (D)=\operatorname{offDiag}(D), \qquad
+\mathcal K^\dagger \mathcal K (Y)=JYJ </math>,
+</center>
+respectively. These are the hollow  and centered subspaces of <math>\mathcal S^n</math>, respectively. The nullspaces of <math>\mathcal K, \mathcal K^\dagger</math> are the ranges of Diag, <math>\mathcal D_e</math>, respectively.
-<math>\operatorname{offDiag}(D):=D-\operatorname{Diag}\operatorname{diag}(D)<\math>.
 == Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem ==
-Using the substitution <math>Y = PP^T\,,</math> and relaxing the (NP-hard) condition that <math>\mathrm{rank}(Y) = r\,,</math> we obtain the semidefinite programming relaxation
+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}\mbox{find}& Y \in \mathcal S^n_+ \\ \mbox{s.t.}& H \circ \mathcal K(Y) = H \circ D \\ & Ye = 0. \end{array}</math></center>
+<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] ==
-Let <math>C \subseteq V</math> be a clique in the graph <math>G\,</math> such that the embedding dimension of <math>D[C]\,</math> is <math>r\,.</math>  Then there exists <math>U \in \mathbb R^{n \times (n-|C|+r)}</math> such that
+Let <math>C \subseteq V</math> be a clique in the graph <math>G\,</math> such that the embedding dimension of <math>D[C]\,</math> is <math>r\,.</math>  Then there exists <math>U \in \mathbb{R}^{n \times (n-|C|+r)}</math> such that
-<center><math> \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. </math></center>
+<center><math> \mathbf{face} \left\{ Y \in \mathcal S^n_+ : \mathcal{K}(Y[C]) = D[C], Ye = 0 \right\} = U \mathcal S^{n-|C|+r}_+ U^{\rm{T}}. </math></center>

Euclidean distance matrix completion via semidefinite facial reduction

From Wikimization

Current revision

Contents

Euclidean distance matrix completions (EDMC), background

Properties of $LaTeX: \mathcal K$ [1]

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

Single Clique Facial Reduction Theorem [2]

Views

Personal tools

Navigation

Search

Toolbox

Euclidean distance matrix completion via semidefinite facial reduction

From Wikimization

Current revision

Contents

Euclidean distance matrix completions (EDMC), background

Properties of [1]

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

Single Clique Facial Reduction Theorem [2]

Views

Personal tools

Navigation

Search

Toolbox

Properties of $LaTeX: \mathcal K$ [1]