Énoncé du théorème

Soit M une matrice m×n dont les coefficients appartiennent au corps K, où K = ℝ ou K = ℂ. Alors il existe une factorisation de la forme :

${\displaystyle M=U\Sigma V^{*}\,\!}$,

avec U une matrice unitaire m×m sur K, Σ une matrice m×n dont les coefficients diagonaux sont des réels positifs ou nuls et tous les autres sont nuls, et V^* est la matrice adjointe à V, matrice unitaire n×n sur K. On appelle cette factorisation la décomposition en valeurs singulières de M.

Décomposition en valeurs singulières dans le cas d'une matrice réelle à 2 dimensions M. Cette transformation déforme, par exemple, un cercle unitaire bleu ci-dessus à gauche en une ellipse dans le coin supérieur droit de l'image. La transformation M peut alors être décomposée en une rotation V^* suivie d'une compression ou étirement Σ le long des axes de coordonnées suivie en fin d'une nouvelle rotation U. Les valeurs singulières σ₁ et σ₂ correspondent aux longueurs des grand et petit axes de l'ellipse.

• La matrice V contient un ensemble de vecteurs de base orthonormés de Kⁿ, dits « d'entrée » ou « d'analyse » ;
• La matrice U contient un ensemble de vecteurs de base orthonormés de K^m, dits « de sortie » ;
• La matrice Σ contient dans ses coefficients diagonaux les valeurs singulières de la matrice M, elles correspondent aux racines des valeurs propres de ${\displaystyle M^{*}M}$.
• Une convention courante est de ranger les valeurs Σ_i,i par ordre décroissant. Alors, la matrice Σ est déterminée de façon unique par M (mais U et V ne le sont pas).

Existence

Une valeur propre λ d'une matrice est caractérisée par l'existence d'un vecteur u non nul satisfaisant la relation M u = λ u. Quand M est hermitienne, une caractérisation différente est envisageable. Soit M une matrice n × n symétrique réelle. On pose f : Rⁿ → R telle que f(x) = x^T M x. Cette fonction est continue et atteint son maximum en un certain vecteur u quand elle est restreinte à la boule unité fermée {x ${\displaystyle \in }$ Rⁿ, ||x|| ≤ 1}. D'après le théorème des multiplicateurs de Lagrange, u vérifie :

${\displaystyle \nabla f=\nabla \;x^{T}Mx=\lambda \cdot \nabla \;x^{T}x.}$

On montre facilement que la relation ci-dessus donne M u = λ u. Ainsi, λ est la plus grande valeur propre de M. Les mêmes opérations sur le complément orthogonal de u donnent la seconde plus grande valeur, et ainsi de suite. Le cas d'une matrice complexe hermitienne est similaire, avec f(x) = x* M x, fonction de 2n variables à valeurs réelles.

Les valeurs singulières sont similaires, en tant qu'elles peuvent être décrites de façon algébrique ou à partir de principes variationnels. En revanche, au contraire du cas des valeurs propres, l'hermiticité et la symétrie de M ne sont plus nécessaires.

Valeurs singulières et vecteurs singuliers

On appelle valeur singulière de M toute racine carrée d'une valeur propre de M^*M, autrement dit tout réel positif σ tel qu'il existe un vecteur unitaire u dans K^m et un vecteur unitaire v dans Kⁿ vérifiant :

${\displaystyle M^{*}u=\sigma v\quad {\textrm {et}}\quad Mv=\sigma u\,\!}$

Les vecteurs u et v sont appelés vecteur singulier à gauche et vecteur singulier à droite pour σ, respectivement.

Dans toute décomposition en valeurs singulières,

${\displaystyle M=U\Sigma V^{*}\,\!}$,

les coefficients diagonaux de Σ sont égaux aux valeurs singulières de M. Les colonnes de U et de V sont, respectivement, vecteur singulier à gauche et à droite pour les valeurs singulières correspondantes.

Par conséquent, le théorème ci-dessus énonce que :

• Une matrice M de type m × n possède au moins une et au plus p = min(m,n) valeurs singulières distinctes ;
• Il est toujours possible de trouver une base unitaire pour K^m constituée des vecteurs singuliers à gauche de M ;
• Il est toujours possible de trouver une base unitaire pour Kⁿ constituée des vecteurs singuliers à droite de M ;

Une valeur singulière pour laquelle on peut trouver deux vecteurs singuliers à gauche (respectivement, à droite) qui sont linéairements indépendants est dite dégénérée.

Les valeurs singulières non dégénérées ont toujours un unique vecteur singulier à gauche et à droite, à un déphasage près, c’est-à-dire à une multiplication par un facteur de la forme e^iφ près (pour des réels, à un signe près). Par conséquent, si toutes les valeurs singulières de M sont non dégénérées et non nulles, alors sa décomposition en valeurs singulières est unique, à une multiplication d'une colonne de U et de la colonne de V correspondante par un même déphasage.

Les valeurs singulières dégénérées, par définition, possèdent plusieurs vecteurs singuliers. De plus, si u₁ et u₂ sont deux vecteurs singuliers à gauche qui correspondent à une même valeur singulière σ, alors tout vecteur unitaire obtenu par combinaison linéaire de ces deux vecteurs est également un vecteur singulier à gauche pour σ. Il en est de même pour les vecteurs singuliers à droites. Ainsi, si M possède des valeurs singulières dégénérées, alors sa décomposition en valeurs singulières n'est pas unique.

Exemple

Soit la matrice :

${\displaystyle M={\begin{pmatrix}1&0&0&0&2\\0&0&3&0&0\\0&0&0&0&0\\0&4&0&0&0\end{pmatrix}}}$

La décomposition en valeurs singulières de M est alors :

${\displaystyle U={\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&-1\\1&0&0&0\end{pmatrix}},\quad \Sigma ={\begin{pmatrix}4&0&0&0&0\\0&3&0&0&0\\0&0&{\sqrt {5}}&0&0\\0&0&0&0&0\end{pmatrix}},\quad V^{\ast }={\begin{pmatrix}0&1&0&0&0\\0&0&1&0&0\\1/{\sqrt {5}}&0&0&0&2/{\sqrt {5}}\\0&0&0&1&0\\-2/{\sqrt {5}}&0&0&0&1/{\sqrt {5}}\end{pmatrix}}}$

On vérifie que Σ ne possède des valeurs non nulles que sur sa diagonale. De plus, comme montré ci-dessous, en multipliant les matrices U et V^* par leurs transposées, on obtient la matrice identité :

${\displaystyle UU^{*}={\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&-1\\1&0&0&0\end{pmatrix}}{\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&-1&0\end{pmatrix}}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}}$

Et de même  :

${\displaystyle VV^{*}={\begin{pmatrix}0&0&1/{\sqrt {5}}&0&-2/{\sqrt {5}}\\1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&0&2/{\sqrt {5}}&0&1/{\sqrt {5}}\end{pmatrix}}{\begin{pmatrix}0&1&0&0&0\\0&0&1&0&0\\1/{\sqrt {5}}&0&0&0&2/{\sqrt {5}}\\0&0&0&1&0\\-2/{\sqrt {5}}&0&0&0&1/{\sqrt {5}}\end{pmatrix}}={\begin{pmatrix}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{pmatrix}}}$

Lien avec la décomposition en valeurs propres

La décomposition en valeurs singulières est très générale, dans le sens où elle s'applique à toute matrice rectangulaire m × n. La décomposition en valeurs propres, en revanche, ne fonctionne que pour certaines matrices carrées. Néanmoins, quand elles sont toutes les deux définies, elles sont liées.

Dans le cas d'une matrice M hermitienne semi-définie positive, c'est-à-dire dont toutes les valeurs propres sont des réels positifs, alors les valeurs singulières et vecteurs singuliers correspondent aux valeurs propres et vecteurs propres de M :

${\displaystyle M=U\Sigma V^{*}\,}$

Plus généralement, étant donné une décomposition en valeurs singulières de M, alors on a :

${\displaystyle M^{*}M=V\Sigma ^{*}U^{*}\,U\Sigma V^{*}=V(\Sigma ^{*}\Sigma )V^{*}\,}$ et ${\displaystyle MM^{*}=U\Sigma V^{*}\,V\Sigma ^{*}U^{*}=U(\Sigma \Sigma ^{*})U^{*}\,}$

Le côté droit de ces relations décrit la décomposition en valeurs propres du côté gauche. Ainsi, le carré du module de chaque valeur singulière non nulle de M est égal au module de la valeur propre non nulle correspondante de M*M et de MM*. En outre, les colonnes de U (vecteurs singuliers à gauche) sont vecteurs propres pour ${\displaystyle MM^{*}}$, et les colonnes de V (vecteurs singuliers à droite) sont vecteurs propres de M*M.

Interprétation géométrique

Puisque U et V sont unitaires, on sait que les colonnes u₁,...,u_m de U forment une base orthonormée de K^m et que les colonnes v₁,...,v_n de V forment une base orthonormée de Kⁿ (par rapport au produit scalaire sur ces espaces).

La transformation linéaire T: Kⁿ → K^m, qui à chaque vecteur x associe Mx, a une expression relativement simple dans ces bases orthonormées : T(v_i) = σ_i u_i, pour i = 1,...,min(m,n), où σ_i est le i-ème coefficient diagonal de Σ, et T(v_i) = 0 pour i > min(m,n).

Le contenu géométrique du théorème de décomposition en valeurs singulières peut être résumé ainsi : pour toute application linéaire T : Kⁿ → K^m, on peut trouver une base orthonormale pour Kⁿ et une base orthonormale pour K^m telles que T associe au i-ème vecteur de base de Kⁿ un multiple positif du i-ème vecteur de base de K^m, les vecteurs restants ayant pour image 0. Dans ces bases, l'application T est ainsi représentée par une matrice diagonale dont les coefficients sont des réels positifs.

Interprétation statistique

Les valeurs de la diagonale de la matrice Σ, rapidement décroissantes, peuvent être comprises comme des coefficients d'énergie. En sélectionnant uniquement les premières, on peut construire un modèle simplifié, empirique, décrivant les données.

On peut également interpréter cette décomposition dans l'esprit de l'étude statistique d'un ensemble de données. Alors, les principales colonnes de U représentent les tendances de l'ensemble d'étude (les vecteurs de U représentent les « directions de plus grande variation » de l'ensemble). Les valeurs diagonales de Σ sont alors analogues à l'« énergie » ou la « représentativité » qui va pondérer ces comportements ; elles décroissent d'autant plus vite que l'ensemble statistique est ordonné.

On peut considérer, par exemple dans l'optique du data mining, que les informations « importantes » de l'ensemble sont celles qui présentent une structure plus marquée. Alors, en annulant la diagonale de Σ au-delà d'un certain indice, puis en reconstituant la matrice de départ, on obtient des données filtrées, représentant l'information dominante de l'ensemble de départ. De façon équivalente, on peut considérer nulles des données d'énergie inférieure à un certain seuil.

Effet de la décomposition SVD sur un ensemble de données, ici la largeur (W) et la hauteur (L) de visages humains. Les vecteurs U₁ et U₂ sont les deux premiers de la matrice U.

Ainsi, la SVD permet de construire un modèle empirique, sans théorie sous-jacente, d'autant plus précis qu'on y injecte de termes.

Il est par ailleurs possible de reconstruire, en utilisant une base de vecteurs singuliers d'un premier jeu de données, un autre jeu de données avec plus ou moins de précision, afin de déterminer la similarité entre les deux. Selon ce principe, des systèmes de décomposition, de reconnaissance et de reconstruction faciale ont été développés^[1].

L'efficacité de la méthode dépend en particulier de la manière dont on lui présente les informations. Dans l'exemple d'un visage, si on utilise naïvement la luminosité des différents pixels d'une photographie pour construire une base de vecteurs singuliers, alors il sera difficile de reconstruire le même visage dans une pose légèrement différente (ou si l'éclairement du visage a varié) : les pixels ont changé - parfois beaucoup - mais pas l'information implicite (à savoir le visage). On préfère, dans ces domaines d'application, traiter les données dans l'espace, d'où l'ajout d'un système de reconnaissance en 3D, qui permet d'« expliquer » les variations observées en reliant celles-ci, et de les relier aux données connues^[1].

SVD/ICA

Il est courant d'associer les résultats de la décomposition en valeurs singulières à ceux de l'analyse en composantes indépendantes (ou ICA)^[7]. Les algorithmes qui exploitent une combinaison des deux sont couramment appelés SVD/ICA. En effet, l'analyse en composantes indépendantes tient compte des termes d'ordre supérieurs ou égaux à 2 négligés par la décomposition en valeurs singulières.

Décomposition généralisée

Le procédé de décomposition en valeurs singulières généralisée, ou GSVD, étend le concept de la décomposition en valeurs singulières en utilisant des semi-normes quadratiques et s'applique aux systèmes linéaires.

Une matrice A de taille m × n et une matrice B de taille p × n réelles ou complexes étant données, leur décomposition généralisée est :

${\displaystyle A=U\Sigma _{1}[0,R]Q^{*}}$

et

${\displaystyle B=V\Sigma _{2}[0,R]Q^{*}}$

avec U, V et Q des matrices unitaires et R une matrice triangulaire supérieure, non singulière, carrée r × r, en notant r ≤ n le rang de [A^*,B^*].

Par ailleurs, Σ₁ et Σ₂ sont des matrices m × r et p × r respectivement, nulles partout sauf sur leur diagonale principale, qui contient les réels α_i et β_i respectivement, tels que :

${\displaystyle 0\leq \alpha _{i},\beta _{i}\leq 1\quad {\textrm {et}}\quad \alpha _{i}^{2}+\beta _{i}^{2}=1}$.

Les rapports ${\displaystyle \sigma _{i}=\alpha _{i}/\beta _{i}}$ sont analogues aux valeurs singulières. Dans le cas particulier, mais important, où B est carrée et inversible, elles sont les valeurs singulières, U et V sont alors les vecteurs singuliers de la matrice AB⁻¹.

Décomposition 2D

On peut généraliser la décomposition en valeurs singulières à plusieurs dimensions, en particulier pour traiter les images. Ici, une image puis ses valeurs singulières (3DSVD). Ici encore, elles décroissent rapidement.

Il est possible d'étendre le concept de décomposition en valeurs singulières à des matrices complexes, ou, de manière équivalente à des matrices constituées de vecteurs 2D. Le calcul est proche de celui de la décomposition en valeurs singulières simple. On parle de décomposition en valeurs singulières 2D, ou 2DSVD.

De même que pour le cas simple, il existe des algorithmes spécialisés qui donnent une approximation d'un ensemble de matrices de rang faible, par exemple des images ou des cartes météorologiques.

Soit X=(x₁,...,x_n) un ensemble de réels (c'est-à-dire de vecteurs 1D). Pour la décomposition en valeurs singulières, on construit la matrice de covariance et la matrice de Gram :

${\displaystyle F=XX^{T}\ ,\ G=X^{T}X}$.

On calcule ensuite leurs vecteurs propres U=(u₁,...,u_n) et V=(v₁,...,v_n). Puisque ${\displaystyle VV^{T}=I,UU^{T}=I}$, on a :

${\displaystyle X=UU^{T}XVV^{T}=U(U^{T}XV)V^{T}=U\Sigma V^{T}}$.

En ne gardant que les K vecteurs propres principaux de U et V, on obtient ainsi une approximation de rang faible de la matrice X. Pour les algorithmes de 2DSVD, on travaille avec des matrices 2D, c'est-à-dire un ensemble de matrices (X₁,...,X_n). On construit les matrices de covariance ligne-ligne et colonne-colonne :

${\displaystyle F=\sum _{i}X_{i}X_{i}^{T}\ ,\ G=\sum _{i}X_{i}^{T}X_{i}}$.

Pour ce faire, on agit de la même façon que pour la décomposition classique, et on calcule leurs vecteurs propres U et V. On approche les X_i :

${\displaystyle X_{i}=UU^{T}X_{i}VV^{T}=U(U^{T}X_{i}V)V^{T}=UM_{i}V^{T}}$

par une méthode identique à celle de la décomposition en valeurs singulières.

On obtient ainsi une approximation de (X₁,...,X_n) par la fonction :

${\displaystyle J=\sum _{i}\left|X_{i}-LM_{i}R^{T}\right|^{2}}$

Les algorithmes de 2DSVD sont principalement utilisés en compression et représentation d'images. L'utilisation de la SVD pour la compression d'images a toutefois été montrée comme étant sous-optimale par rapport à une DCT, notamment à cause de l'obligation de transmettre la transformée elle-même, en plus des données image^[8]. Son rôle dans le domaine de la compression est de fait marginal.

Décomposition 3D

En considérant l'utilisation de matrices dépliées, on peut étendre la décomposition en valeurs singulières aux cas tridimensionnels, ou 3DSVD. De tels algorithmes sont utilisés en sismologie, en météorologie et en acoustique, où l'analyse de données 3D (ou 2D dépendant du temps) est souvent nécessaire.

Décompositions réduites

Dans les utilisations, il est assez rare de devoir utiliser la forme complète de la décomposition en valeurs singulières, y compris la décomposition complète du noyau sous forme unitaire. Il est en effet courant, plus rapide, et moins coûteux en termes de mémoire, d'utiliser des versions réduites de la SVD. Les décompositions suivantes sont valables pour les matrices m × n de rang r.

Normes de Ky Fan

La somme des k plus grandes valeurs singulières de M est une norme sur l'espace vectoriel des matrices, appelée norme de Ky Fan ou norme k de M.

La première des normes de Ky Fan, la norme 1 de Ky Fan, est la même que la norme d'opérateur de M en tant qu'opérateur linéaire, selon les normes euclidiennes de K^m et Kⁿ. En d'autres termes, la norme 1 de Ky Fan est la norme d'opérateur induite par le produit intérieur euclidien standard l². Pour cette raison, on l'appelle également norme 2 d'opérateur. On peut facilement vérifier la relation entre la norme 1 de Ky Fan et les valeurs singulières. C'est vrai en général, pour un opérateur borné M sur un espace de Hilbert (potentiellement infini) :

${\displaystyle \|M\|=\|M^{*}M\|^{\frac {1}{2}}.}$

Cependant, dans le cas des matrices, (M*M)^½ est une matrice normale, donc ||M*M||^½ est la plus grande valeur propre de (M*M)^½, donc la plus grande valeur singulière de M.

La dernière norme de Ky Fan, qui est égale à la somme de toutes les valeurs singulières, est la norme de trace définie par ||M|| = Tr (M*M)^½.

On considère la forme linéaire définie dans l'algèbre des matrices d'ordre n par:

${\displaystyle u_{X}:Y\to {\rm {Tr}}(^{t}YX)}$

On considère la norme spectrale ${\displaystyle \|\ \|_{2}}$ des matrices et l'on définit la norme duale de ${\displaystyle u_{X}}$ par:

${\displaystyle \|u_{X}\|=\sup _{\|Y\|_{2}=1}|{\rm {Tr}}(^{t}YX)|}$

On vérifie alors aisément que cette norme duale est en fait la norme trace de X définie ci-dessus. De plus, cette norme est une norme d'algèbre.

Norme de Hilbert-Schmidt

Les valeurs singulières sont liées à une autre norme sur l'espace des opérateurs. On considère le produit scalaire de Hilbert-Schmidt sur les matrices n × n, défini par <M, N> = Tr N*M. Alors la norme induite est ||M|| = <M, M>^½ = (Tr M*M)^½. La trace étant un invariant de similitude, cela implique que :

${\displaystyle \|M\|=\left(\sum s_{i}^{2}\right)^{\frac {1}{2}}}$,

où les s_i sont les valeurs singulières de M. On l'appelle norme de Frobenius, norme 2 de Schatten ou norme de Hilbert-Schmidt de M. On montre également que si :

${\displaystyle \,M=(m_{ij})}$,

alors cette norme coïncide avec :

${\displaystyle {\biggl (}\sum _{ij}|m_{ij}|^{2}{\biggr )}^{\frac {1}{2}}}$.

Valeurs singulières et opérateurs compacts

Pour étendre la notion de valeur singulière et de vecteurs singuliers au cas des opérateurs, on doit se restreindre aux opérateurs compacts sur les espaces de Hilbert. On rappelle certaines propriétés utiles :

• Les opérateurs compacts sur les espaces de Banach, donc de Hilbert, possèdent un spectre discret ;
• Si T est compact, tout λ de son spectre, non nul, est une valeur propre ;
• Un opérateur compact auto-adjoint peut être diagonalisé par ses vecteurs propres ;
• Si M est compact, alors M*M l'est également.

En utilisant la diagonalisation, l'image unitaire de la racine carrée positive de M, notée T_f, possède une famille orthonormale de vecteurs propres {e_i}, correspondants aux valeurs propres strictement positives {σ_i}. Pour tout ψ ∈ H,

${\displaystyle \;M\psi =UT_{f}V^{*}\psi =\sum _{i}\langle UT_{f}V^{*}\psi ,Ue_{i}\rangle Ue_{i}=\sum _{i}\sigma _{i}\langle \psi ,Ve_{i}\rangle Ue_{i},}$

quand la série converge normalement dans H. On remarque que cette expression est proche de celle dans le cas de dimension finie.

Les σ_i sont appelées valeurs singulières de M. {U e_i} et {V e_i} sont analogues aux vecteurs singuliers à gauche et à droite respectivement pour M.

Calcul du pseudo-inverse

La décomposition en valeurs singulières permet de calculer le pseudo-inverse d'une matrice. En effet, le pseudo-inverse d'une matrice M connaissant sa décomposition en valeurs singulières M = UΣV*, est donné par :

${\displaystyle M^{+}=V\Sigma ^{+}U^{*},\,}$

avec Σ⁺ le pseudo-inverse de Σ où tout coefficient non nul est remplacé par son inverse. Le pseudo-inverse lui-même permet de résoudre la méthode des moindres carrés.

Image, rang et noyau

Une autre utilisation de la décomposition en valeurs singulières est la représentation explicite de l'image et du noyau d'une matrice M. Les vecteurs singuliers à droite correspondant aux valeurs singulières nulles de M engendrent le noyau de M. Les vecteurs singuliers à gauche correspondant aux valeurs singulières non nulles de M engendrent son image.

Par conséquent, le rang de M est égal au nombre de valeurs singulières non nulles de M. De plus, les rangs de M, de M*M et de MM* sont égaux. M*M et MM* ont les mêmes valeurs propres non nulles.

En algèbre linéaire, on peut prévoir numériquement le rang effectif d'une matrice, puisque les erreurs d'arrondi pourraient autrement engendrer des valeurs petites mais non nulles, faussant le calcul du rang de la matrice.

Approximations de matrices, le théorème d'Eckart Young

Approximations successives d'une image, avec 1, 2, 4, 8, 16, 32, 64, 128 puis toutes les valeurs singulières (image originale à gauche).

Certaines applications pratiques ont besoin de résoudre un problème d'approximation de matrices M à partir d'une matrice ${\displaystyle {\tilde {M}}}$ ayant un rang donné, égal à r. Dans le cas où on tente de minimiser la distance au sens de la norme spectrale (ou aussi de Frobenius) entre M et ${\displaystyle {\tilde {M}}}$, en gardant ${\displaystyle {\mbox{rg}}({\tilde {M}})=r}$, on constate que la solution est la décomposition en valeurs singulières de M, c'est-à-dire :

${\displaystyle {\tilde {M}}=U{\tilde {\Sigma }}V^{*}}$

avec ${\displaystyle {\tilde {\Sigma }}}$ égale à Σ, si ce n'est qu'elle ne contient que les ${\displaystyle r}$ plus grandes valeurs singulières, les autres étant remplacées par 0. Voici une démonstration :

Ainsi, ${\displaystyle {\tilde {M}}}$, matrice de rang r, est la meilleure approximation de M au sens de la norme de Frobenius (ou spectrale) quand ${\displaystyle \sigma _{i}=s_{i}\quad (i=1,\cdots ,r)}$. De plus, ses valeurs singulières sont les mêmes que les r premières plus grandes de M.

Application au traitement automatique des langues

Une des principales utilisation de la décomposition en valeurs singulières en traitement automatique des langues est l'analyse sémantique latente (ou LSA, de l'anglais latent semantic analysis), une méthode de la sémantique vectorielle. Ce procédé a pour but l'analyse des relations entre un ensemble de documents et des termes ou expressions qu'on y trouve, en établissant des « concepts » communs à ces différents éléments.

Brevetée en 1988^[9], on parle également d'indexation sémantique latente (LSI). Voici une description sommaire du principe de cet algorithme.

Dans un premier temps, on construit une matrice représentant les différentes occurrences des termes (d'un dictionnaire prédéterminé, ou extraits des documents), en fonction des documents. Par exemple, prenons trois œuvres littéraires :

• Document 1 : « J'adore Wikipédia »
• Document 2 : « J'adore le chocolat »
• Document 3 : « Je déteste le chocolat »

Alors la matrice M associée à ces documents sera :

	J'	Je	adore	déteste	le	Wikipédia	chocolat
Document 1	1	0	1	0	0	1	0
Document 2	1	0	1	0	1	0	1
Document 3	0	1	0	1	1	0	1

Éventuellement, on peut réduire certains mots à leur radical ou à un mot équivalent, ou même négliger certains termes trop courts pour avoir un sens ; la matrice contient alors Je, adorer, détester, Wikipédia, chocolat. Les coefficients (ici 1 ou 0) sont en général non pas un décompte mais une valeur proportionnelle au nombre d'occurrences du terme dans le document, on parle de pondération tf (term frequency). D'autres pondérations comme idf (inverse document frequency ou TF-IDF) peuvent être impliquées.

Alors M sera de la forme :

${\displaystyle {\begin{matrix}&{\textbf {terme}}_{j}\\&\downarrow \\{\textbf {document}}_{i}^{T}\rightarrow &{\begin{pmatrix}x_{1,1}&\dots &x_{1,n}\\\vdots &\ddots &\vdots \\x_{m,1}&\dots &x_{m,n}\\\end{pmatrix}}\end{matrix}}}$

On peut également travailler avec la transposée de M, que l'on note N. Alors les vecteurs lignes de N correspondent à un terme donné, et donnent accès à leur « relation » à chaque document :

${\displaystyle {\textbf {terme}}_{i}^{T}={\begin{bmatrix}x_{i,1}&\dots &x_{i,n}\end{bmatrix}}}$

Et de même, une colonne de la matrice N représente un document donné, et donne accès à sa relation à chaque terme :

${\displaystyle {\textbf {document}}_{j}={\begin{bmatrix}x_{1,j}\\\vdots \\x_{m,j}\end{bmatrix}}}$

On accède à la corrélation entre les termes de deux documents en effectuant leur produit scalaire. La matrice symétrique obtenue en calculant le produit ${\displaystyle S=NN^{T}}$ contient tous ces produits scalaires. L'élément de S d'indice (i,p) contient le produit :

${\displaystyle S_{i,p}={\textbf {terme}}_{i}^{T}{\textbf {terme}}_{p}={\textbf {terme}}_{p}^{T}{\textbf {terme}}_{i}}$.

De même, la matrice symétrique ${\displaystyle Z=N^{T}N}$ contient les produits scalaires entre tous les documents, qui donne leur corrélation selon les termes :

${\displaystyle Z_{j,q}={\textbf {document}}_{j}^{T}{\textbf {document}}_{q}={\textbf {document}}_{q}^{T}{\textbf {document}}_{j}}$.

On calcule maintenant la décomposition en valeurs singulières de la matrice N, qui donne les matrices telles que :

${\displaystyle M=U\Sigma V^{T}}$

Alors les matrices de corrélation deviennent :

${\displaystyle {\begin{matrix}S&=&(U\Sigma V^{T})(U\Sigma V^{T})^{T}=(U\Sigma V^{T})(V^{T^{T}}\Sigma ^{T}U^{T})=U\Sigma V^{T}V\Sigma ^{T}U^{T}=U\Sigma \Sigma ^{T}U^{T}\\Z&=&(U\Sigma V^{T})^{T}(U\Sigma V^{T})=(V^{T^{T}}\Sigma ^{T}U^{T})(U\Sigma V^{T})=V\Sigma ^{T}U^{T}U\Sigma V^{T}=V\Sigma ^{T}\Sigma V^{T}\end{matrix}}}$

La matrice U contient les vecteurs propres de S, la matrice V contient ceux de Z. On a alors :

${\displaystyle {\begin{matrix}&({\textbf {document}}_{j})&&&&&&&({\widehat {{\textbf {document}}_{j})}}\\&\downarrow &&&&&&&\downarrow \\({\textbf {terme}}_{i}^{T})\rightarrow &{\begin{pmatrix}x_{1,1}&\dots &x_{1,n}\\\\\vdots &\ddots &\vdots \\\\x_{m,1}&\dots &x_{m,n}\\\end{pmatrix}}&=&({\widehat {{\textbf {terme}}_{i}}}^{T})\rightarrow &{\begin{pmatrix}{\begin{bmatrix}\,\\\,\\{\textbf {u}}_{1}\\\,\\\,\end{bmatrix}}\dots {\begin{bmatrix}\,\\\,\\{\textbf {u}}_{l}\\\,\\\,\end{bmatrix}}\end{pmatrix}}&\cdot &{\begin{pmatrix}\sigma _{1}&\dots &0\\\vdots &\ddots &\vdots \\0&\dots &\sigma _{l}\\\end{pmatrix}}&\cdot &{\begin{pmatrix}{\begin{bmatrix}&&{\textbf {v}}_{1}&&\end{bmatrix}}\\\vdots \\{\begin{bmatrix}&&{\textbf {v}}_{l}&&\end{bmatrix}}\end{pmatrix}}\\&M&&&U&&\Sigma &&V^{T}\end{matrix}}}$

Les valeurs singulières, ${\displaystyle \sigma _{1},\dots ,\sigma _{l}}$ peuvent alors être sélectionnées, pour obtenir une « approximation » de la matrice à un rang k arbitraire, qui permet une analyse plus ou moins précise des données.

Cinématique inverse

En robotique, le problème de la cinématique inverse, qui consiste essentiellement à savoir « comment bouger pour atteindre un point, » peut être abordé par la décomposition en valeurs singulières.

Autres exemples

Une utilisation courante de la décomposition en valeurs singulières est la séparation d'un signal sur deux sous-espaces supplémentaires, par exemple un sous-espace « signal » et un sous-espace de bruit. La décomposition en valeurs singulières est beaucoup utilisée dans l'étude de l'inversion de matrices, très pratique dans les méthodes de régularisation. On l'emploie également massivement en statistique, en traitement du signal, en reconnaissance de formes et dans le traitement informatique des langues naturelles.

De grandes matrices sont décomposées au travers de cet algorithme en météorologie, pour l'algorithme de Lanczos par exemple.

L'étude géologique et sismique, qui a souvent à faire avec des données bruitées, fait également usage de cette décomposition et de ses variantes multidimensionnelles pour « nettoyer » les spectres obtenus. Étant donné un certain nombre d'échantillons connus, certains algorithmes peuvent, au moyen d'une décomposition en valeurs singulières, opérer une déconvolution sur un jeu de données.

Les valeurs singulières sont également utilisées en automatique. Elles permettent de généraliser le principe de gain d'une fonction de transfert à un système multi-entrées multi-sorties. Les valeurs singulières sont utilisées dans le calcul de la norme H_∞ pour l'élaboration d'une commande H_∞.

Sources

• (it) Eugenio Beltrami, « Sulle funzioni bilineari », Giornale di matematiche,‎ 1873, p. 98–106 (lire en ligne)
• Camille Jordan, « Mémoire sur les formes bilinéaires », Journal de mathématiques pures et appliquées, deuxième série, n^o 19,‎ 1874, p. 35–54 (lire en ligne)
• Camille Jordan, « Sur la réduction des formes formes bilinéaires », Comptes rendus hebdomadaires des séances de l'Académie des sciences, n^o 78,‎ 1874, p. 614–617 (lire en ligne)
• Camille Jordan, « Essai sur la géométrie à n dimensions », Bulletin de la société mathématique, n^o 3,‎ 1875, p. 103–174 (lire en ligne)
• James Joseph Sylvester, « Sur la réduction biorthogonale d'une forme linéo-linéaire à sa forme canonique », Comptes rendus hebdomadaires des séances de l'Académie des sciences, n^o 108,‎ 1889, p. 651–653 (lire en ligne)
• Émile Picard, « Quelques remarques sur les équations intégrales de première espèce et sur certains problèmes de physique mathématique », Comptes rendus hebdomadaires des séances de l'Académie des sciences, n^o 148,‎ 1909, p. 1563–1568 (lire en ligne)
• Émile Picard, « Sur un théorème général relatif aux équations intégrales de première espèce et sur quelques problèmes de physique mathématique », Rendiconti del circolo matematico de Palermo, vol. 1, n^o 29,‎ 1910, p. 79–97 (lire en ligne)

Bibliographie

• (en) Hervé Abdi, « Singular Value Decomposition (SVD) and Generalized Singular Value Decomposition (GSVD) », dans Encyclopedia of Measurement and Statistics, Thousand Oaks, Sage Publications, 2007, 907-912 p. (ISBN 978-1-4129-1611-0, lire en ligne)
• (en) James Demmel et W. Kahan, « Accurate Singular Values of Bidiagonal Matrices », SIAM Journal on Scientific and Statistical Computing, vol. 11, n^o 5,‎ 1990, p. 873-912 (ISSN 0196-5204, OCLC 4633509299, lire en ligne, consulté le 8 octobre 2014)
• (en) Gene H. Golub et Charles F. Van Loan, Matrix computations, Baltimore, Johns Hopkins University Press, coll. « Johns Hopkins studies in the mathematical sciences », 1996, 3^e éd., 694 p. (ISBN 978-0-8018-5413-2)
• (en) Carl Eckart et Gale Young, « The approximation of one matrix by another of lower rank », Psychometrika, vol. 1, n^o 3,‎ septembre 1936, p. 211-218 (ISSN 0090-7499, lire en ligne, consulté le 8 octobre 2014)
• (en) Halldor Bjornsson et Silvia A. Venegas, « A manual for EOF and SVD analyses of climate data », CCGCR Report, Montréal, McGill University, vol. 97, n^o 1,‎ février 1997 (lire en ligne, consulté le 8 octobre 2014)
• (en) Per Christian Hansen, « The truncated SVD as a method for regularization », BIT, vol. 27,‎ 1987, p. 34–553 (lire en ligne, consulté le 8 octobre 2014)
• (en) Roger A. Horn et Charles R. Johnson, « The polar form and the singular value decomposition », dans Matrix analysis, Cambridge, Cambridge University Press, 1985 (ISBN 978-0-521-30586-0), p. 411-427
• (en) Roger A. Horn et Charles R. Johnson, « Chapter 3 - Singular value inequalities », dans Topics in matrix analysis, Cambridge, Cambridge University Press, 1994 (ISBN 978-0-521-46713-1, lire en ligne), p. 134-238
• (en) Gilbert Strang, Introduction to linear algebra, Wellesley, Wellesley-Cambridge Press, 1993, 472 p. (ISBN 978-0-9614088-5-5)
• (en) Chris Ding et Jieping Ye, « Two-Dimensional Singular Value Decomposition (2DSVD) for 2D Maps and Images », Proc. SIAM Int'l Conf. Data Mining, vol. 5,‎ 3 octobre 2004, p. 32-43 (lire en ligne, consulté le 8 octobre 2014)
• (en) Jieping Ye, « Approximations de faible rang de matrices généralisées », Machine Learning, vol. 61,‎ 9 juin 2005, p. 167-191 (ISSN 1573-0565, lire en ligne, consulté le 8 octobre 2014)
• (de) Günter Gramlich, Anwendungen der linearen Algebra : mit MATLAB ; mit 68 Beispielen und 41 Aufgaben, Leipzig, Carl-Hanser-Verl., coll. « Mathematik-Studienhilfen », 2004, 179 p. (ISBN 978-3-446-22655-5)

Articles connexes

• Analyse en composantes principales
• Analyse en composantes indépendantes
• Théorème spectral
• Algèbre linéaire

Liens externes