Instantly share code, notes, and snippets.

# dhermes/cvxopt_spectral_norm.ipynb

Last active September 17, 2018 23:15
Star You must be signed in to star a gist
Student seminar talk on matrix 2-norm as a dual linear program
Display the source blob
Display the rendered blob
Raw
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 { "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] ... 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", ": 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