Student seminar talk on matrix 2-norm as a dual linear program

cvxopt_spectral_norm.ipynb

rfp_low_rank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Schur Complement\n",
    "\n",
    "Note [that](http://en.wikipedia.org/wiki/Schur_complement) for square matrices $A \\in \\mathbf{R}^{m \\times m}$, $D \\in \\text{GL}_n\\left(\\mathbf{R}\\right)$, and rectangular $B, C \\in \\mathbf{R}^{m \\times n}$, the block matrix\n",
    "$$M = \\left[ \\begin{array}{c c}\n",
    "A & B \\\\\n",
    "C^T & D \\end{array}\\right]$$\n",
    "can be factored as\n",
    "$$M = \\left[ \\begin{array}{c c}\n",
    "I_m & BD^{-1} \\\\\n",
    "0 & I_n \\end{array} \\right] \\left[ \\begin{array}{c c}\n",
    "A - B D^{-1} C^T & 0 \\\\\n",
    "0 & D \\end{array} \\right] \\left[ \\begin{array}{c c}\n",
    "I_m & 0 \\\\\n",
    "D^{-1} C^T & I_n \\end{array}\\right].$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Special Cases of Schur Complement\n",
    "\n",
    "When $C = B$ and $D^T = D$ (i.e. $D$ is symmetric) we have\n",
    "$$\\left[ \\begin{array}{c c}\n",
    "I_m & BD^{-1} \\\\\n",
    "0 & I_n \\end{array} \\right]^T = \\left[ \\begin{array}{c c}\n",
    "I_m & 0 \\\\\n",
    "D^{-T} B^T & I_n \\end{array} \\right] = \\left[ \\begin{array}{c c}\n",
    "I_m & 0 \\\\\n",
    "D^{-1} C^T & I_n \\end{array}\\right] = L.$$\n",
    "With this, we have a matrix [congruence](http://en.wikipedia.org/wiki/Matrix_congruence)\n",
    "$$\\left[ \\begin{array}{c c}\n",
    "A & B \\\\\n",
    "B^T & D \\end{array}\\right] \\sim \\left[ \\begin{array}{c c}\n",
    "A - B D^{-1} B^T & 0 \\\\\n",
    "0 & D \\end{array} \\right] = \\Delta$$\n",
    "given by the invertible $L$. \n",
    "\n",
    "**NOTE**: For congruence $M = L^T \\Delta L$, we need $L$ invertible. Since lower-triangular, $\\det L = 1$ from the product of the diagonal entries."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In \"... [Minimum-Rank Solutions][1] ... via Nuclear Norm ...\"\n",
    "\n",
    "In the section **Low-dimensional Euclidean embedding problems** we have $D = I_q$, $B = C \\in \\mathbf{R}^{q \\times q}$ arbitrary and $A = f(X) \\in \\mathbf{R}^{q \\times q}$ symmetric. Here we have the congruence\n",
    "\n",
    "$$\\left[ \\begin{array}{c c}\n",
    "f(X) & B \\\\\n",
    "B^T & I_q \\end{array}\\right] \\sim \\left[ \\begin{array}{c c}\n",
    "f(X) - B B^T & 0 \\\\\n",
    "0 & I_q \\end{array} \\right]$$\n",
    "\n",
    "and we have \n",
    "\n",
    "$$\\operatorname{rank}\\left(\\left[ \\begin{array}{c c}\n",
    "f(X) & B \\\\\n",
    "B^T & I_q \\end{array}\\right]\\right) = \\operatorname{rank}\\left(f(X) - B B^T\\right) +\n",
    "\\operatorname{rank}(I_q)$$\n",
    "\n",
    "Thus, we have the equivalence\n",
    "$$f(X) \\succeq 0 \\Longleftrightarrow \\exists B, \\; f(X) = B B^T \\quad \\text{(Cholesky)}\n",
    "\\Longleftrightarrow \\exists B, \\; \\operatorname{rank}\\left(\\left[ \\begin{array}{c c}\n",
    "f(X) & B \\\\\n",
    "B^T & I_q \\end{array}\\right]\\right) \\leq q$$\n",
    "\n",
    "**NOTE**: We used a slightly modified version than the paper since we developed the matrix congruence for the Schur complement of the bottom-right block instead of for the top-left. Similar analysis could be done by the change of basis given by $e_i \\mapsto e_{(i + n) \\bmod{2n}}$\n",
    "\n",
    "[1]: http://www.eecs.berkeley.edu/~brecht/papers/07.rfp.lowrank.pdf"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

sdp_matrix_dual.ipynb