Using SVD to express the normalized norm of the output of a linear map

53 Views Asked by At

This is probably trivial, but it's been quite some time since my Linear Algebra exam, and my SVD skills are rusty.

1) Let $T$ be a linear map from $\mathbb{R}^n$ to $\mathbb{R}^n$, and $M$ the associated square matrix in the canonical basis.

$$\forall x\in \mathbb{R}^n,\ T(x)=Mx=U\Sigma Vx$$

I want to express

$$\frac{||Mx||}{||x||}$$

in terms of the singular values of $M$ ($||x||\neq0$ obviously). In a presentation, I read that

$$\frac{||Mx||}{||x||}=\sqrt{\frac{\sum_i\sigma_i^2}{\sum_ix_i^2}}$$

where the $\sigma_i$ are the singular values of $M$. This is clearly wrong (e.g., consider an isotropic $M$). What's the correct expression? I would really like to see the passages of the proof, so that next time I can derive the correct expression myself.

2) If $T$ is from $\mathbb{R}^m$ to $\mathbb{R}^n$, i.e., $M$ is not square, is it still possible to express $\frac{||Mx||}{||x||}$ in terms of the singular values of $M$?

1

There are 1 best solutions below

4
On BEST ANSWER

Let $\{\sigma_1,\dots,\sigma_r\}$ be the nonzero singular values of $M$ (where $r$ is the rank of $M$). As you pointed out (assuming the matrix $M$ has real entries) there exists an $m\times m$ orthogonal matrix $U$, an $n\times n$ orthogonal matrix $V$, and a diagonal $m\times n$ matrix $\Sigma$ (whose nonzero diagonal entries are the singular values $\sigma_1,\dots,\sigma_r$) such that $$ M=U\Sigma V. $$ Let $\{v_1,\dots,v_m\}$ denote the rows of $V$ and $\{u_1,\dots,u_n\}$ the columns of $V$ (both of which are orthonormal bases). In particular, it holds that $v_i^Tv_j = 0 $ for indices $i\neq j$ and $v_i^Tv_i=1$ for all $i$. (An analogous statement holds for the vectors $u_i$.)

We can expand $x$ in the basis $\{v_1,\dots,v_m\}$ as $$ x= x_1v_1+\cdots+x_nv_n $$ where $x_1,\dots,x_n\in\mathbb{R}$ are the coefficients of the vector $x$ in this basis such that $$ \lVert x\rVert = \sqrt{\sum_{i=1}^n x_i^2}. $$ Multiplying out, we find that $Mx$ expanded out in the $\{u_1,\dots,u_m\}$ basis is $$ Mx = \sigma_1 x_1 u_1 + \cdots + \sigma_r x_r u_r. $$ such that $\lVert Mx\rVert^2 = \sigma_1^2 x_1^2+\cdots+ \sigma_r^2 x_r^2$. I don't think you can really say much else.

To address your second question, note that $$ \sup_{x\neq 0} \frac{\lVert Mx\rVert}{\lVert x\rVert} = \sigma_1, $$ which is the largest singular value. Indeed, assuming $\sigma_1\geq \sigma_i$ for all other $i\in\{2,\dots,r\}$, we see that $$ \lVert Mx\rVert =\sqrt{ \sum_{i=1}^r \sigma_i^2 x_i^2} \leq \sigma_1\sqrt{\sum_{i=1}^n x_i^2} = \sigma_1 \lVert x\rVert, $$ with equality if and only if $x$ is parallel to $v_1$ (i.e. $x_i=0$ for all $i\in\{2,\dots,n\}$).


We can write $U$ and $V$ as $$ U = \sum_{i=1}^m u_ie_i^T\qquad\text{and }\qquad V = \sum_{i=1}^n e_iv_i^T, $$ where the $e_i$'s are the "standard" basis vectors (i.e., with zeros everywhere except a 1 in the $i$th position), and $\Sigma$ as $$ \Sigma = \sum_{i=1}^r \sigma_i \, e_ie_i^T. $$ It follows that $Vv_i = e_i$ and $Ue_i = u_i$ for all $i$. Moreover, $\Sigma e_i = \sigma_i e_i$. Thus $$ Mv_i = U\Sigma Vv_i = U\Sigma e_i = \sigma_i Ue_i = \sigma_i u_i. $$