Instantly share code, notes, and snippets. dhermes/cvxopt_spectral_norm.ipynb Last active Sep 17, 2018

Student seminar talk on matrix 2-norm as a dual linear program Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
 { "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 } Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.