Skip to content

Instantly share code, notes, and snippets.

@dhermes
Last active September 17, 2018 23:15
Show Gist options
  • Save dhermes/18793452c4e3b89b2ec86d7d73439483 to your computer and use it in GitHub Desktop.
Save dhermes/18793452c4e3b89b2ec86d7d73439483 to your computer and use it in GitHub Desktop.
Student seminar talk on matrix 2-norm as a dual linear program
Display the source blob
Display the rendered blob
Raw
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
{
"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
}
Display the source blob
Display the rendered blob
Raw
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment