# Euclidean distance matrix completion via semidefinite facial reduction

(Difference between revisions)
 Revision as of 13:27, 24 November 2011 (edit) (→Properties of $\mathcal K$ [http://orion.math.uwaterloo.ca/~hwolkowi/henry/reports/edmapr04.pdf])← Previous diff Current revision (16:30, 25 September 2016) (edit) (undo) (→Semidefinite programming relaxation of the low-dimensional Euclidean distance matrix completion problem) (5 intermediate revisions not shown.) Line 6: Line 6: EDMC is a ''fundamental problem of distance geometry, (FPDG)''. EDMC is a ''fundamental problem of distance geometry, (FPDG)''. - Let $\mathcal S^n$ be the vector space of symmetric matrices equipped with the trace inner product, $\langle S, T \rangle = \mathrm{trace}(ST)$; let $D \in \mathcal E^n$, the set of $n \times n$ Euclidean distance matrices, i.e. $D_{ij}=|| p_i-p_j||^2$, for points $p_i\in \mathbb R^r, i=1,...n$, with embedding dimension $r$; + Let $\mathcal S^n$ be the vector space of symmetric matrices equipped with the trace inner product, $\langle S, T \rangle = \mathrm{trace}(ST)$; let $D \in \mathcal E^n$, the set of $n \times n$ Euclidean distance matrices, i.e. $D_{ij}=|| p_i-p_j||^2$, for points $p_i\in \mathbb{R}^r, i=1,...n$, with embedding dimension $r$; and, let $\mathcal S^n_+$ be the set (convex cone) of (symmetric) positive semidefinite matrices. Defining $\mathcal K : \mathcal S^n \rightarrow \mathcal S^n$ by and, let $\mathcal S^n_+$ be the set (convex cone) of (symmetric) positive semidefinite matrices. Defining $\mathcal K : \mathcal S^n \rightarrow \mathcal S^n$ by Line 13: Line 13: we have that $\mathcal K(\mathcal S^n_+) = \mathcal E^n$. Note that $\mathcal K$ is a one-one linear transformation between the ''centered symmetric matrices'', $S \in \mathcal S_c,$ and the ''hollow matrices'' $\mathcal S_H$, where centered means row (and column) sums are all zero, and hollow means that the diagonal is zero. we have that $\mathcal K(\mathcal S^n_+) = \mathcal E^n$. Note that $\mathcal K$ is a one-one linear transformation between the ''centered symmetric matrices'', $S \in \mathcal S_c,$ and the ''hollow matrices'' $\mathcal S_H$, where centered means row (and column) sums are all zero, and hollow means that the diagonal is zero.

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

$\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}$
+
$\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 $e \in \mathbb R^n$ is the vector of all ones, and $H\,$ is the adjacency matrix of the graph $G = (V,E)\,$ associated with the partial Euclidean distance matrix $D.$ + where $e \in \mathbb{R}^n$ is the vector of all ones, and $H\,$ is the adjacency matrix of the graph $G = (V,E)\,$ associated with the partial Euclidean distance matrix $D.$ ===Properties of $\mathcal K$ [http://orion.math.uwaterloo.ca/~hwolkowi/henry/reports/edmapr04.pdf]=== ===Properties of $\mathcal K$ [http://orion.math.uwaterloo.ca/~hwolkowi/henry/reports/edmapr04.pdf]=== Let $Let [itex] - \mathcal D_e(Y):=\operatorname{diag}(Y)e^{\rm{T}}+e\operatorname{diag}(Y)^{\rm{T}} + \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 [/itex], where diag denotes the diagonal of the argument. Then alternatively, we can write alternatively, we can write Line 33: Line 33:
$[itex] - \mathcal D^*(D) = 2 \operatorname{Diag} (De), + \mathcal D^*(D) = 2 {\text Diag} (De), \qquad \qquad - \mathcal K^*(D) = 2 (\operatorname{Diag} (De) -D), + \mathcal K^*(D) = 2 ({\text Diag} (De) -D),$
[/itex]
Line 42: Line 42:
$\mathcal K^\dagger(D) = -\frac 12 J \operatorname{offDiag} (D) J,$
$\mathcal K^\dagger(D) = -\frac 12 J \operatorname{offDiag} (D) J,$
- where the matrix $J:=I-\frac 1n ee^T$ + where the matrix $J:=I-\frac 1n ee^{\rm{T}}$ and the linear operator (orthogonal projection) and the linear operator (orthogonal projection) - $\operatorname{offDiag}(D):=D-\operatorname{Diag}\operatorname{diag}(D)$. The orthogonal projections onto the range of $\mathcal K$ and range of $\mathcal K^*$ is given by + $\operatorname{offDiag}(D):=D-{\text Diag}{\text diag}(D)$. The orthogonal projections onto the range of $\mathcal K$ and range of $\mathcal K^*$ is given by
$\mathcal K\mathcal K^\dagger (D)=\operatorname{offDiag}(D), \qquad [itex]\mathcal K\mathcal K^\dagger (D)=\operatorname{offDiag}(D), \qquad \mathcal K^\dagger \mathcal K (Y)=JYJ$, \mathcal K^\dagger \mathcal K (Y)=JYJ [/itex], 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 $Y = PP^T\,,$ and relaxing the (NP-hard) condition that $\mathrm{rank}(Y) = r\,,$ we obtain the semidefinite programming relaxation + Using the substitution $Y = PP^{\text T}\,,$ and relaxing the (NP-hard) condition that ${\text rank}(Y) = r\,,$ we obtain the semidefinite programming relaxation -
$\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}$
+
$\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 [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] == - Let $C \subseteq V$ be a clique in the graph $G\,$ such that the embedding dimension of $D[C]\,$ is $r\,.$ Then there exists $U \in \mathbb R^{n \times (n-|C|+r)}$ such that + Let $C \subseteq V$ be a clique in the graph $G\,$ such that the embedding dimension of $D[C]\,$ is $r\,.$ Then there exists $U \in \mathbb{R}^{n \times (n-|C|+r)}$ such that -
$\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.$
+
$\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}}.$

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

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:

\mathcal D^*(D) = 2 {\text Diag} (De), \qquad \mathcal K^*(D) = 2 ({\text Diag} (De) -D),

$

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

\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 

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}}.$