Singular Value Decomposition (as an optimization)

$\def\half{\frac{1}{2}} \def\bm#1{\boldsymbol{#1}} \def\R{\mathbb{R}} \def\norm#1{\left\lVert #1 \right\rVert} \def\X{\bm{X}} \def\U{\bm{U}} \def\V{\bm{V}} \def\L{\bm{L}} \def\M{\bm{M}} \def\I{\bm{I}} \def\u{\bm{u}} \def\v{\bm{v}} \def\y{\bm{y}} \def\Q{\bm{Q}} \def\D{\bm{D}} \def\S{\bm{S}} \def\x{\bm{x}} \def\vec{\operatorname{vec}} \def\tr{\operatorname{tr}} \def\d{\operatorname{d}} \def\Xv{\widehat{\X\v}} \def\H{\operatorname{H}} \def\It{{\bm I}_2}$ The setting for the svd is the following optimization problem: $$ \sup_{\norm{u}=1,\norm{v}=1} \u^\top \X \v $$ where $\u \in \R^{m}$, $\v \in \R^{n}$ and $\X \in \R^{m \times n}$. This can be extended to the following optimization using matrices: $$ \begin{equation} \sup_{\U,\V} \qty[ \tr\qty(\U^\top \X \V ) -\frac{1}{2} \tr\qty(\L^\top\qty(\U^\top\U-\I_m)) -\frac{1}{2} \tr\qty(\M^\top\qty(\V^\top\V-\I_n)) ] \equiv \sup_{\U,\V} \phi(\U,\X,\V,\L,\M) \end{equation} $$ where $\U, \L, \I_m \in \R^{m \times m}$, $\V,\M,\I_n \in \R^{n \times n}$.

The differential of $\phi$ w.r.t. $\U$ is $$ \begin{align} \d\phi & = \tr\qty((\d\U^\top) \X \V ) - \frac{1}{2} \tr\qty(\L^\top\U^\top \d\U) - \frac{1}{2} \tr\qty(\L^\top(\d\U^\top) \U) \nonumber\\ & = \tr\qty(\V^\top \X^\top \d\U ) - \frac{1}{2} \tr\qty(\L^\top\U^\top \d\U) - \frac{1}{2} \tr\qty(\U^\top(\d\U) \L) \nonumber\\ & = \tr\qty(\V^\top \X^\top \d\U ) - \frac{1}{2} \tr\qty(\L^\top\U^\top \d\U) - \frac{1}{2} \tr\qty(\L \U^\top\d\U ) \nonumber\\ & = \tr\qty(\V^\top \X^\top \d\U ) - \tr\qty(\frac{1}{2}\qty(\L+\L^\top)\U^\top \d\U) \nonumber\\ \pdv{\phi}{\U^\top} & = \V^\top \X^\top - \frac{1}{2}\qty(\L+\L^\top)\U^\top. \label{condU} \end{align} $$ Using the same procedure we can show that $$ \begin{align} \d\phi & = \tr\qty(\U^\top \X \d\V ) - \tr\qty(\frac{1}{2}\qty(\M+\M^\top)\V^\top \d\V) \nonumber\\ \pdv{\phi}{\V^\top} & = \U^\top \X - \frac{1}{2}\qty(\M+\M^\top)\V^\top. \label{condV} \end{align} $$

Setting (\ref{condU}), (\ref{condV}) to zero we obtain the optimisation conditions: $$ \begin{align} \pdv{\phi}{\U^\top}=0 & \Rightarrow \V^\top \X^\top = \frac{1}{2}\qty(\L+\L^\top)\U^\top, \label{VU} \\ \pdv{\phi}{\V^\top}=0 & \Rightarrow \U^\top \X = \frac{1}{2}\qty(\M+\M^\top)\V^\top. \label{UV} \end{align} $$

Next, right multiply (\ref{VU}) with $\U$ to get $$ \V^\top \X^\top \U= \frac{1}{2}\qty(\L+\L^\top)\U^\top\U=\frac{1}{2}\qty(\L+\L^\top) $$ and, right multiply (\ref{UV}) with $\V$ to get $$ \U^\top \X \V= \frac{1}{2}\qty(\M+\M^\top)\V^\top\V= \frac{1}{2}\qty(\M+\M^\top). $$ If we transpose both sides of the last equation we obtain $$ \V^\top \X^\top \U=\frac{1}{2}\qty(\M+\M^\top) $$ and so $\frac{1}{2}\qty(\M+\M^\top)=\frac{1}{2}\qty(\L+\L^\top)=\S$ (a symmetric matrix). So (\ref{VU}) and (\ref{UV}) can be rewritten as $$ \begin{align*} \V^\top \X^\top & = \S\U^\top, \\ \U^\top \X & = \S\V^\top. \end{align*} $$ Taking the transpose of both sides of these equations we obtain the familiar form for the svd: $$ \begin{align} \X\V & = \U\S, \label{standardVU}\\ \X^\top \U & = \V\S. \label{standardUV} \end{align} $$ (\ref{standardVU}) and (\ref{standardUV}) generate the following eigenequations: $$ \begin{align} \X^\top\X\V & = \V\S^2, \label{eigen1}\\ \X\X^\top \U & = \U\S^2. \label{eigen2} \end{align} $$ Since $\X^\top\X$, $\X\X^\top$ are symmetric matrices their eigenvectors form an orthonormal basis and $\V^\top\V=\V\V^\top=\I_n$, $\U^\top\U=\U\U^\top=\I_m$ as required. It is also the case that both matrices are positive semi-definite since, for example, for any $\x \in \R^n$ $$ \x^\top \X^\top \X \x = (\X \x)^\top (\X \x) \geq 0. $$ Using $\V\V^\top=\I_n$ we can rewrite (\ref{standardVU}) as $$ \X = \U\S\V^\top $$ which is the full svd of $\X$.

Comments

Post a Comment

Popular posts from this blog

CSAT 1

Image
Test Section A 1. You have a card of 10cm by 10cm. What is the largest volume in cm 3 of a box (without a lid) that can be obtained by cutting out a square of side x from each corner and then folding the flaps up? We can obtain an idea of the solution by looking at the following diagram: The box will have a base (marked in red on the diagram) with area $(l-2x)^2$ and height $x$. Therefore the volume of this box will be \begin{equation*} V=(l-2x)^x. \end{equation*} To maximize the volume first calculate \[ \dv{V}{x}=-4(l-2x)x+(l-2x)^2 \] using the product rule $d(u\cdot v)=du \cdot v + u \cdot dv$. Solve for $\dv*{V}{x}=0$ to find a (potential) maximum. If we assume that $x\neq l$ (a reasonable assumption since $x=l/2$ creates a nothing box) then \begin{align*} -4(l-2x)x+(l-2x)^2& =0 \\ l-2x-4x & = 0 \\ x & = \frac{l}{6}. \end{align*} To check that this is i...
Read more

Poor man's Daletskii-Krein

Image
Consider a second-order, symmetric tensor $A$ whose components $\def\R{\mathbb{R}}{A^j}_i \in \R$. We know that such a tensor has an eigen decomposition \begin{equation} \label{eigendecomp} A = V \Lambda V^\top \end{equation} where $V$ is an orthonormal, second-order tensor and ${\Lambda^j}_i=\lambda^j \delta^j_i$ ($\lambda^i$ is the $i$th eigenvalue of $A$). One corollary of (\ref{eigendecomp}) is \begin{equation} \label{An} A^n = V \Lambda^n V^\top . \end{equation} A function $f:\R \to \R$ that is analytic at $x=0$ is equal to its Maclaurin series \begin{equation} \label{maclaurin} f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} x^n \end{equation} where $f^{(0)}(0)=f(0)$ and $f^{(n)}(0)=\eval{\dv[n]{f}{x}}_{x=0}$. If we define \begin{equation} \label{def-fA} f(A):= \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} A^n \end{equation} then $f(A)$ is also a second-order, sy...
Read more

PAT 2022

Image
1. What is the total resistance of the circuit ? 2. For which values of $x$ is $\qty(24-14x -3x^2)^{-1}$ positive? The $-1$ exponent does not change the sign. We can factorise $24-14x -3x^2$ as $(-3x+4)(x+6)$ which is positive either if $x < \frac{4}{3}, x > -6$ or if $x > \frac{4}{3}$, $x < -6$. The second condition cannot hold so we have to go with (D). 3. Molecules of oxygen in the atmosphere absorb solar radiation in bands centred at about 80 nm, 650 nm and 1000 nm. In which parts of the electromagnetic spectrum are these absorption bands? Picture from tikz.net The visible spectrum is in the very narrow band from 380 nm (violet) to 750 nm (red) so 650 nm is in the visible spectrum in the red zone. $1000 \ {\rm nm}=10^{-6} \ {\rm m}$ which is right at the edge of infrared. Finally $80 \ {\rm nm}= 0...
Read more