Decomposizione ai valori singolari

In algebra lineare, la decomposizione ai valori singolari, detta anche SVD (dall'acronimo inglese di 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:

Illustrazione della decomposizione ai valori singolari UΣV^⁎ di una matrice M reale 2×2

$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

In origine, la decomposizione ai valori singolari fu 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 nel 1873, e Camille Jordan nel 1874, in modo indipendente tra loro, scoprirono 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, sembra 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 Léon 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 Carl Eckart e Gale 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 «valeurs singulières» e a denotarli $\sigma _{k}$.

Metodi pratici per la computazione della SVD risalgono a Ervand Kogbetliantz fra il 1954 e il 1955 e a Magnus Hestenes nel 1958 e hanno un'implementazione simile al metodo di Jacobi, che usa rotazioni del piano o rotazioni di Givens. Tali approcci furono rimpiazzati dal metodo di Gene H. 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.

Definizione

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}\geq 0\quad \forall i\qquad s_{1}\geq s_{2}\geq \dots \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 \dots \geq s_{r}>s_{r+1}=\dots =s_{n}=0$ e la decomposizione SVD di $A$ è definita come:

$\mathbf {A} ={\begin{pmatrix}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{pmatrix}}=U\Sigma V^{*}={\begin{pmatrix}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{pmatrix}}{\begin{pmatrix}s_{1}&0&\ldots &0\\0&s_{2}&\ldots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\ldots &s_{r}\\\end{pmatrix}}{\begin{pmatrix}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{pmatrix}}$

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

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), utilizzata nell'elaborazione di immagini e nell'elaborazione dei segnali.

La SVD ha anche note applicazioni nel campo dell'analisi delle componenti principali.

Esempio

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 identità, 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

• (EN) Gene H. Golub, Charles F. Van Loan, Matrix computations, 3ª edizione, Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8.
• (EN) Lloyd N. Trefethen e David Bau III, Numerical linear algebra, Philadelphia, Society for Industrial and Applied Mathematics, 1997, ISBN 978-0-89871-361-9.
• (EN) Gene H. Golub e Charles F. Van Loan, Matrix Computations, 3rd, Johns Hopkins, 1996, ISBN 978-0-8018-5414-9.
• (EN) Horn, Roger A.; Johnson, Charles R., Section 7.3, in Matrix Analysis, Cambridge University Press, 1985, ISBN 0-521-38632-2.
• (EN) Horn, Roger A.; Johnson, Charles R., Chapter 3, in Topics in Matrix Analysis, Cambridge University Press, 1991, ISBN 0-521-46713-6.
• (EN) Samet, H., Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2006, ISBN 0-12-369446-9.
• (EN) Strang G., Section 6.7, in Introduction to Linear Algebra, 3rd, Wellesley-Cambridge Press, 1998, ISBN 0-9614088-5-5.
• (EN) Michael E. Wall, Andreas Rechtsteiner, Luis M. Rocha, Singular value decomposition and principal component analysis, in D.P. Berrar, W. Dubitzky, M. Granzow (a cura di), A Practical Approach to Microarray Data Analysis, Norwell, MA, Kluwer, 2003, pp. 91–109.

Voci correlate

• Autovettore e autovalore
• Decomposizione di una matrice
• Decomposizione polare
• Matrice trasposta coniugata
• Matrice unitaria
• Problema di Procuste ortogonale
• Teorema spettrale
• Valore singolare

Collegamenti esterni

• (EN) singular value decomposition, in PlanetMath.
• (EN) GSL Team, §14.4 Singular Value Decomposition, in GNU Scientific Library. Reference Manual, 2007.