Decomposizione ai valori singolari

Da Wikipedia, l'enciclopedia libera.

In algebra lineare, la decomposizione ai valori singolari, anche detta SVD (dall'acronimo inglese Singular Value Decomposition) è una particolare fattorizzazione di una matrice basata sull'uso di autovalori e autovettori. Data una matrice M reale o complessa di dimensione m\times n, si tratta di una scrittura del tipo:

M = U \Sigma V^*

dove U è una matrice unitaria di dimensioni m\times m, \Sigma è una matrice diagonale rettangolare di dimensioni m\times n e V^* è la trasposta coniugata di una matrice unitaria V di dimensioni n\times n.

Gli elementi di \Sigma sono detti valori singolari di M; ognuna delle m colonne di U è detta vettore singolare sinistro mentre ognuna delle n colonne di V è detta vettore singolare destro. Si verifica che:

  • I vettori singolari di sinistra di M sono gli autovettori di MM^*
  • I vettori singolari di destra di M sono gli autovettori di M^* M
  • I valori singolari non nulli di M (che si trovano sulla diagonale principale di \Sigma) sono le radici quadrate degli autovalori non nulli di MM^* e M^* M.

Storia[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Sia A\in\mathbb{C}^{m\times n} una matrice. 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 rettangolare (non è quadrata ma possiede elementi non nulli solo quando gli indici di riga e colonna coincidono) di dimensioni m\times n e 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 ha dimensione m \times n mentre \Sigma è n\times n. Gli elementi della diagonale di \Sigma sono i 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.

Si supponga 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 rango 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]} e 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^{*} 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, essendo U e V^{*} due matrici unitarie, godono della seguente proprietà:

 U \cdot U^{*} = I \qquad V \cdot V^{*}=I

Applicazioni[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Data 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 è 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}

Si ha:

\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 si può 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[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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