FinalSolnAMS229Fall18.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1. (70 points) Euclidean Distance Matrix\n",
    "\n",
    "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$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "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\n",
    "$$D = \\begin{pmatrix}\n",
    "0 & 1 & 1\\\\\n",
    "1 & 0 & 1\\\\\n",
    "1 & 1 & 0\n",
    "\\end{pmatrix}$$\n",
    "has eigenvalues $-1, -1, 2$, i.e., $D$ is sign-indefinite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(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\n",
    "\n",
    "$$D = \\text{diag}(G) 1^{\\top} \\: + \\: 1 (\\text{diag}(G))^{\\top} \\: - \\: 2G.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution: \n",
    "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.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) **[10 points]** Use part (b) to show that the Euclidean distance matrix is invariant under rotation and translation.\n",
    "\n",
    "[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}$.]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "Consider the transformations given in the hint.\n",
    "\n",
    "When $X \\mapsto QX$, we have $G := X^{\\top}X \\mapsto X^{\\top}Q^{\\top}QX = X^{\\top}X = G$.\n",
    "\n",
    "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)$.\n",
    "\n",
    "From part (b), we notice that both these transformtions leave matrix $D$ invariant. Hence the statement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(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$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(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\n",
    "\n",
    "$$ D_{ii} = 0, \\quad D_{ij}=D_{ji}, \\quad KDK \\preceq 0.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "$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$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(f) **[10 points]** Use part (e) to prove that the set \n",
    "\n",
    "$$\\{D\\in\\mathbb{R}^{n\\times n} \\:\\mid\\:D\\;\\text{is a Euclidean distance matrix}\\},$$ \n",
    "\n",
    "is a convex cone.\n",
    "\n",
    "[Comment: this is perhaps surprising given the conclusion in part (a).]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "For any $\\alpha > 0$, the map $D \\mapsto \\alpha D$ leaves the three conditions in part (e) invariant. So this set is a cone. \n",
    "\n",
    "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$.)\n",
    "\n",
    "Thus, the set $\\{D\\in\\mathbb{R}^{n\\times n} \\:\\mid\\:D\\;\\text{is a Euclidean distance matrix}\\}$ is a convex cone."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(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\n",
    "\n",
    "$$\\begin{align}\n",
    "&\\underset{D\\in\\mathbb{R}^{n\\times n}}{\\text{minimize}}\\quad \\parallel D - \\Delta\\parallel_{\\text{Frobenius}}^{2}\\\\\n",
    "&\\text{subject to}\\quad D = D^{\\top},\\\\\n",
    "& \\;\\qquad\\qquad D_{ii} = 0, \\; i=1,...,n,\\\\\n",
    "& \\qquad\\qquad\\, KDK \\preceq 0,\\\\\n",
    "& \\qquad\\qquad\\,\\text{rank}(KDK) \\leq r.\n",
    "\\end{align}$$\n",
    "\n",
    "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.\n",
    "\n",
    "[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.]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "The above optimization problem is not convex.\n",
    "\n",
    "The nonconvexity is due to the rank constraint.\n",
    "\n",
    "A simple convex relaxation results by omitting the rank constraint, since all other constraints as well as the objective function are convex in $D$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem 2. (30 points) SDP Revisited "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the following SDP:\n",
    "\n",
    "$$\\begin{align}\n",
    "p^{*} \\quad = \\quad &\\underset{(x_{1},x_{2})\\in\\mathbb{R}^{2}}{\\text{minimize}}\\quad x_{1}\\\\\n",
    "&\\text{subject to} \\quad \\begin{pmatrix} 0 & x_{1} & 0\\\\\n",
    "x_{1} & x_{2} & 0\\\\\n",
    "0 & 0 & x_{1}+1\\end{pmatrix} \\succeq 0.\n",
    "\\end{align}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) **[10 points]** Analytically (by hand) compute the optimal value $p^{*}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "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:\n",
    "$$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.$$\n",
    "\n",
    "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$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) **[10 points]** Derive the dual problem corresponding to the above SDP. \n",
    "\n",
    "(Hint: See Lecture 12, p. 23-25.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "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\n",
    "\n",
    "$$F_{0} = \\begin{pmatrix}0 & 0 & 0\\\\\n",
    "0 & 0 & 0\\\\\n",
    "0 & 0 & 1\n",
    "\\end{pmatrix}, \\quad F_{1} = \\begin{pmatrix}0 & 1 & 0\\\\\n",
    "1 & 0 & 0\\\\\n",
    "0 & 0 & 1\n",
    "\\end{pmatrix}, \\quad F_{2} = \\begin{pmatrix}0 & 0 & 0\\\\\n",
    "0 & 1 & 0\\\\\n",
    "0 & 0 & 0\n",
    "\\end{pmatrix}.$$\n",
    "\n",
    "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) \n",
    "\n",
    "$$\\begin{align}\n",
    "d^{*} = \\quad &\\underset{Z\\in\\mathbb{S}^{3}_{+}}{\\text{maximize}}\\:-\\text{trace}(F_{0}Z)\\\\\n",
    "&\\text{subject to} \\quad \\text{trace}\\left(F_{i}Z\\right) = c_{i}, \\quad i=1,2.\n",
    "\\end{align}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(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^{*})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Solution:\n",
    "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$.\n",
    "\n",
    "From part (a), we know that $p^{*}=0$. Hence the duality gap $(p^{*}-d^{*}) = 0-(-1) = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}