Math 202A: Lecture 15

Let V,W be any two objects of \mathbf{FHil}, and let A be any morphism in \mathrm{Hom}(V,W). Let \sigma_1=\|A\| be the operator norm of A, and let

V_1=\mathrm{Opt}(A)=\{v \in V \colon \|Av\|=\sigma_1\|v\|\}

be the set of vectors in V which are maximally stretched by A. In Lecture 14, we showed that V_1 is a nonzero subspace of V. As a consequence,

W_1=A(V_1) = \{w \in W \colon w=Av \text{ for some }v \in V_1\}

is a subspace of W. Thus we have associated to A two geometrically defined subspaces V_1 \leq V and W_1 \leq W, and we can view A as a linear transformation between these subspaces, i.e. as a morphism A \in \mathrm{Hom}(V_1,W_1).

Proposition 15.1. For A \neq 0, there exists an isometric isomorphism U_1 \colon V_1 \to W_1 such that A = \sigma_1 U_1.

Proof: U_1=\frac{1}{\sigma_1}A_1. \square

Now let us consider the orthogonal decompositions

V = V_1 \oplus V_1^\perp \quad\text{and}\quad W=W_1 \oplus W_1^\perp.

It is a quite important fact that A respects this decomposition: not only does A map V_1 into W_1, it maps V_1^\perp into W_1^\perp. This fact will allow us to prove the Singular Value Decomposition geometrically, by induction on the rank of A.

Theorem 15.1. We have A(V_1^\perp) \leq W_1^\perp.

Proof: Let u \in V be any vector which is orthogonal to every vector v \in V_1. We have to show that

\langle Au,Av\rangle = 0 \quad\text{ for all } v \in V_1.

If u=0_V this is true simply because A is a linear transformation. If \|u\|>0 then we can assume without loss in generality that \|u\|=1, again because A is a linear transformation:

\langle A\left( \frac{u}{\|u\|} \right),Av \rangle = \frac{1}{\|u\|}\langle Au,Av\rangle.

Thus, our job is to show that if u \in V is a unit vector orthogonal to every vector in V_1, then Au is orthogonal to Av for all v\in V_1. So, let v \in V_1 be arbitrary, and consider the scalar product

\alpha := \langle Au,Av\rangle.

We will show that \alpha =0. First, let us show this under the following assumption.

Nonnegative assumption: \alpha \geq 0.

Let \varepsilon >0, and consider the corresponding perturbation v+\varepsilon u of the stretch optimizer v \in V_1 in the direction of the unit vector u \in V. As with every vector in V, this perturbation satisfies

\|A(v+\varepsilon u)\|^2 \leq \sigma_1^2 \|v+\varepsilon u\|^2.

Let us carefully examine each side of this equality. The LHS is

\langle Av + \varepsilon Au,Av + \varepsilon Au\rangle = \langle Av,Av\rangle + \varepsilon \langle Av,Au\rangle +\varepsilon \langle Au,Av \rangle + \varepsilon^2 \langle u,u\rangle.

Simplifying using v \in V_1, the definition of \alpha, and \|u\|=1, this becomes

\|A(v+\varepsilon u)\|^2 = \sigma_1^2\|v\|^2 + 2\alpha\varepsilon + \varepsilon^2.

As for the RHS, this is

\sigma_1^2 \|v+\varepsilon u\|^2 = \sigma_1^2\|v\|^2 +\varepsilon^2\sigma_1^2.

Thus we obtain the inequality

2\alpha\varepsilon + \varepsilon^2 \leq \varepsilon^2\sigma_1^2\,

which implies

2\alpha\varepsilon < \varepsilon^2\sigma_1^2.

We have thus shown that 2\alpha < \varepsilon \sigma_1^2 for every \varepsilon >0, which forces \alpha=1. \square

Problem 15.2. Complete the proof of Theorem 15.1 by removing the assumption \alpha \geq 0. (Hint: this is not hard, so don’t make it hard).

Problem 15.3. For A nonzero, show that the rank of the restriction A \in \mathrm{Hom}(V_1^\perp,W_1^\perp) is strictly less than the rank of A \in \mathrm{Hom}(V,W).

Now we can state the geometric form of the singular value decomposition: a remarkable stratification of the source and target spaces of any linear transformation between finite-dimensional Hilbert spaces which provides a remarkably detailed understanding of its structure.

Theorem 15.2 (SVD, geometric form) Let r be the rank of A \in \mathrm{Hom}(V,W). Then, there exist positive numbers \sigma_1 \geq \dots \geq \sigma_r > 0 and orthogonal decompositions

V = \mathrm{Ker}(A) \oplus V_1 \oplus \dots \oplus V_r \quad\text{and}\quad W=\mathrm{Im}(A)^\perp \oplus W_1 \oplus \dots \oplus W_r

such that for each 1 \leq i \leq r the restriction of A to V_i is of the form A=\sigma_i U_i for U_i \in \mathrm{Hom}(V_i,W_i) and isometry.$

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply