Singular Value Decomposition

Singular Value Decompositon §

Teorema ($SVD$ completa). Sia $A\in {\mathcal{C}}^{m\times n}$, con $m\ge n$. Allora esistono due matrici unitarie $U\in {\mathbb{C}}^{m\times m}$ e $V\in {\mathbb{C}}^{n\times n}$ tali che:

$$U^{H}AV=\Sigma =diag({\sigma }_1,\dots ,{\sigma }_n)\in {\mathbb{R}}^{m\times n}$$

dove ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge g_n\ge 0$ detti valori singolari sono univocamente determinati. Osservazione Le matrici unitarie $U$ e $V$ non sono uniche, infatti itroducendo una matrice (unitaria) di fase: $S=diag(e^{i{\theta }_1},e^{i{\theta }_2},\dots )$

Dim Per induzione su $n$, vale per tutte le matrici con $m\ge n$.

• $n=1$, le matrici sono vettori con $k\ge n$ componenti, quindi del tipo $A=a=(a_1,a_2,\dots a_k{)}^T$. Poniamo ${\sigma }_1=\Vert A{\Vert }_2$, e scegliamo $U\in {\mathbb{C}}^{k\times k}$ la matrice del Riflettore di Householder associata al vettore $u=a+{\sigma }_1{e}^{i\arg a_1}{e}_1^{(k)}$, che è unitaria ed hermitiana. Scegliendo opportunamente $V=[e^{i\theta }]$ fa si che $U^{H}AV=Ua{e}^{i\theta }=-{\sigma }_1{e}^{i\arg a_1}={\sigma }_1{e}_1^{(k)}\in {\mathbb{R}}^{k\times 1}$.
• $n>1$ facciamo vedere che se la tesi vale per matrici in ${\mathbb{C}}^{k\times (n-1)}$ con $k\ge n-1$, allora vale anche per matrici in ${\mathbb{C}}^{m\times n}$ con $m\ge n$.

Per la definizione di norma spettrale, esiste un versore tale che:

$$||A|{|}_2=||Ax|{|}_2$$

definisco un nuovo versore:

$$y:=\frac{Ax}{||Ax||}⟹Ax={\sigma }_{1}y$$

dove con abbiamo posto ${\sigma }_1=||Ax||=||A||$.

Costruisco due matrici unitarie $U_1$ e $V_1$ che hanno per colonna $y$ ed $x$ rispettivamente. Facciamo il conto $U_1^{H}A{V}_1$, in particolare la prima colonna (l’unica che so calcolare)

$$U_1^{H}A{V}_1{e}_1=U_1^{H}Ax={\sigma }_1{U}_1^{H}y={\sigma }_1{e}_1$$

duque, in generale

$$A_1:=U_1^{H}A{V}_1=\left(\begin{array}{cc}{\sigma }_1& w^H\\ 0& B\end{array}\right)$$

Dimostriamo che $w^H=0^H$. Supponiamo per assurdo $w\ne 0$, definiamo il vettore $z:=({\sigma }_1,w)$, e calcoliamo il prodotto con $A_1$.

$$||A_{1}z|{|}_2^2=||z|{|}_2^4+||Bw|{|}_2^2$$

voglio far apparire il raggio spettrale al quadrato, divido per la norma al quadrato di $z$ (posso siccome $z\ne 0$ avendo supposto $w\ne 0$ ):

$$\frac{||A_{1}z|{|}^2}{||z|{|}^2}=||z|{|}^2+\frac{||Bw|{|}_2^2}{||z|{|}^2}\ge ||z|{|}^2={\sigma }_1^2+||w|{|}^2>{\sigma }_1^2$$

contraddizione con la definizione di raggio spettrale. Dunque $w=0$.

$$A_1=\left(\begin{array}{cc}{\sigma }_1& 0^H\\ 0& B\end{array}\right)$$

Ora noto che $B\in {\mathbb{C}}^{(m-1)\times (n-1)}$, dunque posso usare l’ipotesi induttiva:

$$U_2^{H}B{V}_2={\Sigma }_2$$

Facciamo vedere che ${\sigma }_1\ge {\sigma }_2$. Calcoliamo il raggio spettrale di $A_1^H{A}_1$:

$${\sigma }_1^2=\rho (A_1^H{A}_1)=\rho \left(\begin{array}{cc}{\sigma }_1^2& 0^H\\ 0& B^{H}B\end{array}\right)=\max \{{\sigma }_1^2,||B|{|}_2^2\}$$

E’ chiaro che moltiplicando a sinistra ed a destra la matrice $A_1$ con le matrici:

$$\left(\begin{array}{cc}1& 0^H\\ 0& U_2\end{array}\right)\left(\begin{array}{cc}1& 0^H\\ 0& V_2\end{array}\right)$$

Ottengo la tesi, ovvero:

$$U^{H}AV=\Sigma \square$$

Osservazione A differenza dei valori singolari, $U$ e $V$ non sono univocamente determinate, infatti se $S\in {\mathbb{C}}^{n\times n}$ è una matrice di fase e $Z\in {\mathbb{C}}^{(m-n)\times (m-n)}$ è una matrice unitria, continua a valere:

$$A=U\left(\begin{array}{cc}S& 0\\ 0& Z\end{array}\right)\Sigma S^H{V}^H$$

Interpretazione dei valori singolari §

Sono una generalizzazzione degli autovalori per matrici rettangolari. Se condieriamo le $m$ colonne di $U$ e le $n$ colonne di $V$, dalla decomposizione otteniamo che:

$$A=U\Sigma V^H=\sum _{i=1}^n{\sigma }_i{u}_i{v}_i^h$$

quindi:

$$A{v}_i={\sigma }_i{u}_i{A}^H{u}_i={\sigma }_i{v}_{i}i=1:n$$

infatti $v_i$ vengono detti vettori singolari destri di $A$ e i $u_i$ vettori singolari sinistri di $A$.

SVD ridotta §

Sia ${\sigma }_k$ l’ultimo valore singolare non nullo. Dati i molti elementi nulli di $\Sigma$, possiamo introdurre una fattorizzazione ridotta:

$$A=U_k{\Sigma }_k{V}_k^H$$

con ${\Sigma }_k\in {\mathbb{R}}^{k\times k}$ diagonale, $V_k\in {\mathbb{C}}^{n\times k}$ e $U_k\in {\mathbb{C}}^{m\times k}$.

Proposizione ($\ker$) Sia ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge sigm{a}_k>{\sigma }_{k+1}\cdots =0$. Ovvero ${\sigma }_k$ ultimo valore singolare non nullo. Allora il $\ker (A)$ è generato dai vettori singolari destri $v_{k+1},\dots ,v_n$. Dim $x\in \ker (A)$ significa $U\Sigma V^{H}x=0$, siccome $U$ è unitaria è equivale a $\Sigma V^{H}x=0$, ma per costruzione tutte le componenti $k+1,\dots ,m$ sono nulle, dunque basta richiedere $V_k^{H}x=0$ ovvero $x$ deve essere ortogonale alle prime $k$ colonne di $V$, quindi deve essere nello span delle altre colonne. $\square$

Proposizione $range(A)$ Sia ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge sigm{a}_k>{\sigma }_{k+1}\cdots =0$. Ovvero ${\sigma }_k$ ultimo valore singolare non nullo. Allora il $range(A)$ è generato dai primi $u_1,\dots u_k$ vettori singolari di sinistri. Dim $y\in range(A)$ signficia $\exists x{\mathbb{C}}^n$ tale che $U_k{\Sigma }_k{V}_k^{H}x=y$. Chiamiamo $z:={\Sigma }_k{V}_k^{H}x$, la condizione diventa

$$U_{k}z=y$$

ovvero $y$ è nello spazio generato dalle prime $k$ colonne di $U$. Viceversa, se $y=U_{k}z$ per un qualche $z\in {\mathbb{C}}^k$, riesco a trovare un $x\in {\mathbb{C}}^n$ tale che:

$$z={\Sigma }_k{V}_k^{H}x$$

siccome ${\Sigma }_k{V}_k^H$ è invertibile (Rouché-Capelli).

Corollario Il rango di $A$ è uguale al numero di valori singolari non nulli. Dim $rank(A)=dim(range(A))=k$. $\square$

Norme e valori singolari §

Proposizione Per i valori singolari di $A\in {\mathbb{C}}^{m\times n}$ vale:

$${\sigma }_i=\sqrt{{\lambda }_i(A^{H}A)}$$

(avendo supposto ordinati correttamente gli autovalori).

Dim Uso la SVD:

$$A^{H}A=(U\Sigma V^H{)}^H(U\Sigma V^H)=V{\Sigma }^H\Sigma V^H$$

La matrice ${\Sigma }^H\Sigma \in {\mathbb{R}}^{n\times n}$ non è altro che la matrice $diag({\sigma }_1^2,\dots ,{\sigma }_n^2)$. Osserviamo come $A^{H}A$ e ${\Sigma }^H\Sigma$ siano matrici simili, dunque hanno lo stesso spettro. $\square$

Corollario Da queste considerazioni segue che:

• $||A|{|}_2=\sqrt{\rho (A^{H}A)}={\sigma }_1$
• $||A|{|}_F=\sqrt{{\sum }_{i=1}^n|{\lambda }_i{|}^2}=\sqrt{{\sum }_{i=1}^n{\sigma }_i}$

Corollario Se $A$ è invertibile, allora vale $||A^{-1}|{|}_2=\frac{1}{{\sigma }_n}$ Dim Vale $A^{-1}=V{\Sigma }^{-1}{U}^H$, la norma spettrale è l’autovalore di modulo massimo, che sarà $\frac{1}{{\sigma }_n}$ (l’inverso del più piccolo).

Segue dirattmente che il numero di condizionamento spettrale può essere calcolato come:

$${\mathcal{K}}_2(A)=\frac{{\sigma }_1}{{\sigma }_n}$$

Approssimazione di rango basso §

Sia $A\in {\mathbb{C}}^{m\times n}$, con $m\ge n$ di rango $k\le n$, sia $1\le r<n$ un intero. Sia $\mathcal{B}$ l’insieme di tutte le matrici $m\times n$ di rango minore uguale a $r$, vogliamo determinare $B^{\ast }\in \mathcal{B}$ tale che:

$$B^{\ast }=argmi{n}_{B\in \mathcal{B}}||A-B|{|}_2,\delta =||A-B^{\ast }|{|}_2$$

Teorema Sia $A\in {\mathbb{C}}^{m\times n}$ di rango $k\le n$. Sia $r<k$. Allora la soluzione del problema precedente è data da:

$$B^{\ast }=A_r:=U_r{\Sigma }_r{V}_r^H\delta ={\sigma }_{r+1}$$

Dim Dimostriamo subito la seconda uguaglianza:

$$||A-A_r|{|}_2=||U^H(A-A_r)V|{|}_2={\sigma }_{r+1}$$

Supponaimo per assurdo che esista una $B\in \mathcal{B}$ tale che:

$$||A-B|{|}_2<{\sigma }_{r+1}$$

quindi una soluzione migliore di $A_r$. $B$ ha rango minore o uguale a $r$, il $\ker (B)$ ha dimensione almeno $n-r$. Sia $z\in \ker (B)$ e $z\ne 0$, vale:

$$||Az|{|}_2=||(A-B)z|{|}_2\le \Vert A-B\Vert \Vert z\Vert <{\sigma }_{r+1}\Vert z\Vert$$

Consideriamo ora il sottospazio $S=span(v_1,\dots ,v_{r+1})$. Per ogni vettore $z\in S$ vale:

$$\Vert Az{\Vert }_2^2=\Vert \Sigma V^{H}z{\Vert }_2^2={\Vert \Sigma \sum _{i=1}^{r+1}{\alpha }_i{v}_i\Vert }_2^2=\sum _{i=1}^{r+1}\Vert {\sigma }_i{\alpha }_i{\Vert }_2^2\ge {\sigma }_{r+1}^2\Vert z{\Vert }_2^2$$

questa disuguaglianza è incompatible con quella di prima (tranne nell’origine), dunque il sottospazio $S$ deve essere disgiunto da $\ker (B)$, ma ciò è impossibile perchè la dimensione della loro somma ha dimensione almemo $n+1$, assurdo. $\square$

L’utilità del valore $\delta ={\sigma }_{r+1}$, è che ci permette di stimare la probabilità che gli errori di macchina rendano la matrice di rango inferiore.

Effettivamente per quanto abbiamo dimostrato prima, il Numero di condizionamento di una matrice non è altro che l’inverso della distanza con le matrici di rango inferiore normalizzata per la norma spettrake della matrice:

$$\frac{{\sigma }_n}{\Vert A{\Vert }_2}=\frac{{\sigma }_n}{{\sigma }_1}=\frac{1}{{\mathcal{K}}_2(A)}=\left\{\frac{\Vert \delta A{\Vert }_2}{\Vert A{\Vert }_2}:A+\delta A\text{ eˋ singolare }\right\}$$