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.
(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.$$(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}$.]
(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$?
(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.$$(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).]
(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.]
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^{*}$.
(b) [10 points] Derive the dual problem corresponding to the above SDP.
(Hint: See Lecture 12, p. 23-25.)
(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^{*})$.