Decomposizione ai valori singolari

In algebra lineare, la decomposizione ai valori singolari (o SVD, Singular Value Decomposition) è una particolare fattorizzazione basata sull'uso di autovalori e autovettori, utilizzata per produrre un'approssimazione della matrice originaria con minor rango.

Storia

La decomposizione ai valori singolari fu originariamente sviluppata da studiosi di geometria differenziale, allo scopo di determinare se una forma bilineare reale potesse essere equivalente ad un'altra tramite trasformazioni ortogonali indipendenti dei due spazi presi in considerazione. Eugenio Beltrami e Camille Jordan scoprirono indipendentemente, nel 1873 e nel 1874 rispettivamente, che i valori singolari della forma bilineare, rappresentati in una matrice, formano un insieme completo di invarianti per forme bilineari. Anche James Joseph Sylvester arrivò al risultato della SVD, apparentemente in maniera indipendente dagli studi di Beltrami e Jordan. Sylvester chiamò i valori singolari moltiplicatori canonici della matrice. Il quarto matematico a scoprire la decomposizione a valori singolari fu Autonne, nel 1915, che raggiunse la sua formulazione tramite lo studio delle matrici per decomposizione polare. La prima dimostrazione del procedimento di decomposizione per matrici rettangolari e a valori complessi sembra esser stata prodotta da Eckart e Young nel 1936.

Nel 1907, Erhard Schmidt definì un analogo dei valori singolari per gli operatori integrali (che sono compatti, sotto alcune deboli assunzioni); pare che, durante i suoi studi, Schmidt fosse ignaro dell'esistenza dei risultati sui valori singolari per le matrici finite. Questa teoria fu ulteriormente sviluppata da Émile Picard nel 1910, che fu il primo a chiamare i numeri σk singular values (oppure, valeurs singulières).

Metodi pratici per la computazione della SVD risalgono a Kogbetliantz fra il 1954 e il 1955 e a Hestenes nel 1958 e hanno un'implementazione simile al metodo di Jacobi, il quale usa rotazioni del piano o rotazioni di Givens. Tali approcci furono rimpiazzati dal metodo di Gene Golub e William Kahan pubblicato nel 1965 (Golub & Kahan 1965), che si basa su trasformazioni di Householder o riflessioni. Nel 1970, Golub e Christian Reinsch pubblicarono una variante dell'algoritmo di Golub/Kahan che è ancora uno dei più utilizzati attualmente.

Definizione

Sia $A\in\mathbb{C}^{m\times n}$, allora esiste una fattorizzazione della stessa nella forma:

$A = U \Sigma V^* \$

dove:

• $U$ è una matrice unitaria di dimensioni $m\times m$;
• $\Sigma$ è una matrice diagonale di dimensioni $m\times n$ (diagonale in senso lato, dove solo i primi $n$ elementi sono non nulli);
• $V^*$ è la trasposta coniugata di una matrice unitaria di dimensioni $n\times n$.

Tale fattorizzazione è indicata come fattorizzazione SVD completa. Nella versione normalmente utilizzata, denominata forma SVD ridotta, la matrice U è $m \times n$ mentre $\Sigma$ è $n\times n$. Gli elementi della diagonale di $\Sigma$ sono detti valori singolari di A e hanno le proprietà:

$s_{i} \ge 0 \quad \forall i \qquad s_{1}\geq s_{2}\geq \ldots \geq s_{n}$

Si può dimostrare che il rango della matrice A è uguale a quello della matrice $\Sigma$. In particolare si osserva che il rango di $\Sigma$ dipende dai valori singolari ed è proprio uguale al numero di valori singolari diversi da zero.

Supponiamo di avere una matrice A con rango $rk(A)= r$, allora si ha che $s_{1}\geq s_{2}\geq \ldots \geq s_{r} > s_{r+1} = \ldots = s_{n} = 0$ e la decomposizione SVD di A è definita come:

$\mathbf{A} = \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn}\\ \end{array} \right) = \underbrace{ \left( \begin{array}{cccc} u_{11} & u_{12} & \ldots & u_{1r}\\ u_{21} & u_{22} & \ldots & u_{2r}\\ \vdots & \vdots & \ddots & \vdots \\ u_{m1} & u_{m2} & \ldots & u_{mr}\\ \end{array} \right) }_{U} \cdot \underbrace{ \left( \begin{array}{cccc} s_{1} & 0 & \ldots & 0\\ 0 & s_{2} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & s_{r}\\ \end{array} \right) }_{\Sigma} \cdot \underbrace{ \left( \begin{array}{cccc} v_{11} & v_{12} & \ldots & v_{1n}\\ \bar{v_{21}} & v_{22} & \ldots & v_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ \bar{v_{r1}} & \bar{v_{r2}} & \ldots & v_{rn}\\ \end{array} \right) }_{V^{*}}$

dove $U$ è una matrice singolare sinistra ortogonale, $V^{*}$ è la matrice trasposta coniugata di una matrice singolare destra ortogonale e $\Sigma$ è una matrice singolare diagonale di ordine $r$ (cioè con $r$ valori diversi da zero).

Il rank della matrice $A$ e di conseguenza della matrice singolare $\Sigma$ forniscono la dimensione effettiva delle tre matrici $U_{[m \times r]}, \Sigma_{[r \times r]}, V^{*}_{[r \times n]}$ .

Le $r$ colonne della matrice $U$ e le $r$ righe della matrice $V^{*}$ rappresentano gli autovettori ortogonali associati agli $r$ autovalori rispettivamente di $A \cdot A^{T}$ e $A^{*} \cdot A$.

In altre parole, le $r$ colonne di $U$ corrispondono ai valori singolari diversi da zero dello spazio delle colonne della matrice $A$ e le $r$ righe di $V^{*}$ corrispondono ai valori singolari diversi da zero corrispondenti allo spazio delle righe della matrice $A$.

Inoltre $U$ e $V^{*}$, essendo due matrici unitarie, godono della seguente proprietà:

$U \cdot U^{*} = I \quad \mbox{e} \quad V \cdot V^{*}=I$

Applicazioni

La SVD ha numerose applicazioni nel campo dell'algebra lineare. Innanzitutto fornisce delle informazioni importanti sulla matrice A, come il suo rango, qual è il suo nucleo e qual è la sua immagine. Viene usata per definire la pseudo-inversa di una matrice rettangolare utile per la risoluzione del problema dei minimi quadrati. Trova utilizzo anche nella risoluzione di sistema di equazioni lineari omogeneo. Un'altra importante applicazione riguarda l'approssimazione della matrice A, con una di rango inferiore (SVD troncata), frequentamente utilizzata nell'elaborazione di immagini e segnali.

Esempio

Considerate la matrice

$\begin{bmatrix} 1 & 0 & 0 & 0 & 2\\ 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0\end{bmatrix}.$

Una decomposizione a valori singolari di questa matrice è data da

$U = \begin{bmatrix} 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & -1\\ 1 & 0 & 0 & 0\end{bmatrix} , \Sigma = \begin{bmatrix} 4 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0\\ 0 & 0 & \sqrt{5} & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{bmatrix} , V^* = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8}\\ 0 & 0 & 0 & 1 & 0\\ -\sqrt{0.8} & 0 & 0 & 0 & \sqrt{0.2}\end{bmatrix}$

che è

$\begin{bmatrix} 1 & 0 & 0 & 0 & 2\\ 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0\end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & -1\\ 1 & 0 & 0 & 0\end{bmatrix} \cdot \begin{bmatrix} 4 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0\\ 0 & 0 & \sqrt{5} & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{bmatrix} \cdot \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8}\\ 0 & 0 & 0 & 1 & 0\\ -\sqrt{0.8} & 0 & 0 & 0 & \sqrt{0.2}\end{bmatrix}.$

Moltiplicando le matrici $U$ o $V^*$ per le loro rispettive trasposte si ottiene come risultato la matrice identica, cioè entrambe le matrici sono ortogonali.

$\begin{bmatrix} 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & -1\\ 1 & 0 & 0 & 0\end{bmatrix} \cdot \begin{bmatrix} 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & -1 & 0\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{bmatrix}$

e

$\begin{bmatrix} 0 & 0 & \sqrt{0.2} & 0 & -\sqrt{0.8}\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & \sqrt{0.8} & 0 & \sqrt{0.2} \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8}\\ 0 & 0 & 0 & 1 & 0\\ -\sqrt{0.8} & 0 & 0 & 0 & \sqrt{0.2}\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\end{bmatrix}.$

È possibile notare, inoltre, che la decomposizione a valori singolari non è unica per ogni matrice. Per esempio, scegliendo la stessa matrice $U$ possiamo ottenere

$V^* = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8}\\ \sqrt{0.4} & 0 & 0 & \sqrt{0.5} & -\sqrt{0.1}\\ -\sqrt{0.4} & 0 & 0 & \sqrt{0.5} & \sqrt{0.1} \end{bmatrix}$

che è un'altra valida decomposizione a valori singolari.

Bibliografia

• Gene H. Golub; Charles F. Van Loan, Matrix computations, 3^a edizione, Johns Hopkins University Press, 1996. ISBN 0-8018-5414-8

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica