A matrix $D\in\mathbb{R}^{n\times n}$ is called an Euclidean distance matrix if there exists points $x_{1}, ..., x_{n}$ in $\mathbb{R}^{r}$ such that $D_{ij} = \parallel x_{i} - x_{j} \parallel_{2}^{2}$ for $i,j=1,...,n$. In many practical applications like NMR spectroscopy, one can measure pairwise distances between atoms (and hence construct matrix $D$), and would like to infer the point configuration $x_{1}, ..., x_{n}$ (which is same as determining the structure of the molecule). The dimension of the space $r$ is called the "embedding dimension". Assume $r < n$.
(a) [10 points] The matrix $D$ has some properties obvious from its definition: $D_{ii}=0$, $D_{ij}\geq 0$, $D_{ij}=D_{ji}$, $\sqrt{D}_{ij} + \sqrt{D}_{jk} \geq \sqrt{D}_{ik}$, for all $i,j,k=1,...,n$. For $r=2$, $n=3$, give a simple example showing that the matrix $D$ is sign-indefinite.
Consider the points $x_{1}, x_{2}, x_{3} \in \mathbb{R}^{2}$ such that they are pairwise equi-distant, i.e., they form an equilateral triangle with side length 1. Then the matrix $$D = \begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{pmatrix}$$ has eigenvalues $-1, -1, 2$, i.e., $D$ is sign-indefinite.
(b) [10 points] Let $X = [x_{1} \quad x_{2} \quad ... \quad x_{n}] \in \mathbb{R}^{r\times n}$, and $G:=X^{\top}X$ be the associated Gram matrix. If $\text{diag}(G)$ denotes the column vector of the diagonal elements of $G$, then prove that
$$D = \text{diag}(G) 1^{\top} \: + \: 1 (\text{diag}(G))^{\top} \: - \: 2G.$$We have $D_{ij} := (x_{i}-x_{j})^{\top}(x_{i}-x_{j}) = x_{i}^{\top}x_{i} - 2 x_{i}^{\top}x_{j} + x_{j}^{\top}x_{j}$. Therefore, $D = \text{diag}(G) 1^{\top} \: + \: 1 (\text{diag}(G))^{\top} \: - \: 2G.$
(c) [10 points] Use part (b) to show that the Euclidean distance matrix is invariant under rotation and translation.
[Hint: Consider the transformations $X \mapsto QX$, $X \mapsto X + a 1^{\top}$, for an $r\times r$ orthogonal matrix $Q$, and $a\in\mathbb{R}^{r}$.]
Consider the transformations given in the hint.
When $X \mapsto QX$, we have $G := X^{\top}X \mapsto X^{\top}Q^{\top}QX = X^{\top}X = G$.
On the other hand, for $X \mapsto X + a1^{\top}$, we have $G := X^{\top}X \mapsto \left(X^{\top} + 1a^{\top}\right)\left(X + a1^{\top}\right)$.
From part (b), we notice that both these transformtions leave matrix $D$ invariant. Hence the statement.
(d) [5 points] Consider the $n\times n$ matrix $K := I - \frac{1}{n}11^{\top}$. What is the geometric meaning of multiplying a vector in $\mathbb{R}^{n}$ by matrix $K$?
For any vector $v\in\mathbb{R}^{n}$, the matrix-vector product $Kv$ centers the vector $v$ by subtracting the mean of all coordinates from each coordinate. In other words, it "centers" the vector by shifting the origin to the centroid of the coordinates.
(e) [10 points] Use parts (b) and (d) to prove that $KDK \preceq 0$. From here, one can conclude that a matrix $D\in\mathbb{R}^{n\times n}$ is an Euclidean distance matrix if and only if
$$ D_{ii} = 0, \quad D_{ij}=D_{ji}, \quad KDK \preceq 0.$$$KDK \stackrel{\text{(b)}}{=} K \left(\text{diag}(G) 1^{\top} \: + \: 1 (\text{diag}(G))^{\top} \: - \: 2G\right) K \stackrel{\text{(d)}}{=} - 2 KGK = -2 KX^{\top}XK \stackrel{\text{(}K=K^{\top}\text{)}}{=} -2 \left(XK\right)^{\top}\left(XK\right) \preceq 0$.
(f) [10 points] Use part (e) to prove that the set
$$\{D\in\mathbb{R}^{n\times n} \:\mid\:D\;\text{is a Euclidean distance matrix}\},$$is a convex cone.
[Comment: this is perhaps surprising given the conclusion in part (a).]
For any $\alpha > 0$, the map $D \mapsto \alpha D$ leaves the three conditions in part (e) invariant. So this set is a cone.
That the set is convex follows from the fact that the first two equality conditions in part (e) are linear in $D$; the last inequality condition is an LMI in $D$. Therefore, together they define a convex set. (Alternatively, you can directly show that for $D_{1},D_{2}$ being Euclidean distance matrices, the matrix $\theta D_{1} + (1-\theta)D_{2}$ satisfies the three conditions in part (e) for all $0\leq \theta \leq 1$.)
Thus, the set $\{D\in\mathbb{R}^{n\times n} \:\mid\:D\;\text{is a Euclidean distance matrix}\}$ is a convex cone.
(g) [5+5+5=15 points] From practical experiment, suppose $\Delta\in\mathbb{R}^{n\times n}$ is a matrix of noisy pairwise distance measurements. Then, one wishes to solve the following problem for determining the true Euclidean distance matrix $D$ with embedding dimension at most $r$, given by
$$\begin{align} &\underset{D\in\mathbb{R}^{n\times n}}{\text{minimize}}\quad \parallel D - \Delta\parallel_{\text{Frobenius}}^{2}\\ &\text{subject to}\quad D = D^{\top},\\ & \;\qquad\qquad D_{ii} = 0, \; i=1,...,n,\\ & \qquad\qquad\, KDK \preceq 0,\\ & \qquad\qquad\,\text{rank}(KDK) \leq r. \end{align}$$Is the above optimization problem convex? Why/why not? If it is a convex problem, then what type of convex problem is it? If not, give a simple convex relaxation of this problem.
[Comment: Once $D$ is obtained by solving the above, the point configuration $X$ can be estimated by methods such as "multi-dimensional scaling". We will not pursue that here.]
The above optimization problem is not convex.
The nonconvexity is due to the rank constraint.
A simple convex relaxation results by omitting the rank constraint, since all other constraints as well as the objective function are convex in $D$.
Consider the following SDP:
$$\begin{align} p^{*} \quad = \quad &\underset{(x_{1},x_{2})\in\mathbb{R}^{2}}{\text{minimize}}\quad x_{1}\\ &\text{subject to} \quad \begin{pmatrix} 0 & x_{1} & 0\\ x_{1} & x_{2} & 0\\ 0 & 0 & x_{1}+1\end{pmatrix} \succeq 0. \end{align}$$(a) [10 points] Analytically (by hand) compute the optimal value $p^{*}$.
The LMI constraint in this case is simply equivalent to requiring all of the principal (not just leading) minors of the $3 \times 3$ matrix being $\geq 0$. This gives the following inequalities: $$0 \geq 0, \quad x_{2} \geq 0, \quad x_{1}+1 \geq 0, \quad -x_{1}^{2}\geq 0, \quad x_{2}(x_{1}+1)\geq 0.$$
Since $x_{1}$ is real, the fourth inequality implies $x_{1}=0$, which combined with other inequalities yields $x_{2} \geq 0$. Therefore, $p^{*}= \underset{(x_{1},x_{2})\in\{0\}\times\mathbb{R}_{\geq 0}}{\text{minimize}}\; x_{1} = 0$.
(b) [10 points] Derive the dual problem corresponding to the above SDP.
(Hint: See Lecture 12, p. 23-25.)
Letting $x=(x_{1},x_{2})^{\top}$, the primal constraint can be written as $F(x) = F_{0} + x_{1}F_{1} + x_{2}F_{2} \succeq 0$, with $F_{0},F_{1},F_{2}\in\mathbb{S}^{3}$, given by
$$F_{0} = \begin{pmatrix}0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}, \quad F_{1} = \begin{pmatrix}0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}, \quad F_{2} = \begin{pmatrix}0 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{pmatrix}.$$Thus, we can write the primal SDP in standard form (as in Lecture 12, p. 23) with $c = (1,0)^{\top}$. Then the dual problem becomes (as in Lecture 12, p. 25)
$$\begin{align} d^{*} = \quad &\underset{Z\in\mathbb{S}^{3}_{+}}{\text{maximize}}\:-\text{trace}(F_{0}Z)\\ &\text{subject to} \quad \text{trace}\left(F_{i}Z\right) = c_{i}, \quad i=1,2. \end{align}$$(c) [10 points] By computing (analytically, or by cvxpy, whichever you prefer) the optimal value $d^{*}$ for the dual problem derived in part (b), find the duality gap $(p^{*} - d^{*})$.
From part (b), the objective $-\text{trace}(F_{0}Z) = -Z_{33}$. The first equality constraint in part (b) becomes: $\text{trace}\left(F_{1}Z\right) = Z_{12}+Z_{21}+Z_{33}=1$. The second equality constraint in part (b) becomes: $\text{trace}\left(F_{2}Z\right) = Z_{22}=0$. However, $Z_{22}=0$ and $Z \succeq 0$ together implies $Z_{12}=Z_{21} = 0$, which by first equality constraint, in turn implies $Z_{33}=1$. Therefore, $d^{*} = \text{maximize}\,-Z_{33}=-1$.
From part (a), we know that $p^{*}=0$. Hence the duality gap $(p^{*}-d^{*}) = 0-(-1) = 1$.