En mathématiques, le procédé d'algèbre linéaire de décomposition en valeurs singulières (ou SVD, de l'anglais ) d'une matrice est un outil important de factorisation des matrices rectangulaires réelles ou complexes. Ses applications s'étendent du traitement du signal aux statistiques, en passant par la météorologie.
Le théorème spectral énonce qu'une matrice normale peut être diagonalisée par une base orthonormée de vecteurs propres. On peut voir la décomposition en valeurs singulières comme une généralisation du théorème spectral à des matrices arbitraires, qui ne sont pas nécessairement carrées.
Contexte mathématique Énoncé du théorème Soit une matrice m×n dont les coefficients appartiennent au corps K, où K = ℝ ou K = ℂ. Alors il existe une factorisation de la forme : , avec 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 est la matrice adjointe à , matrice unitaire n×n sur K. On appelle cette factorisation la décomposition en valeurs singulières de .thumb|right | 280px | Décomposition en valeurs singulières dans le cas d'une matrice réelle à 2 dimensions . 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 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 . Les valeurs singulières σ1 et σ2 correspondent aux longueurs des grand et petit axes de l'ellipse.
La matrice contient un ensemble de vecteurs de base orthonormés de Kn, dits « d'entrée » ou « d'analyse » ; La matrice contient un ensemble de vecteurs de base orthonormés de Km, dits « de sortie » ; La matrice contient dans ses coefficients diagonaux les valeurs singulières de la matrice , elles correspondent aux racines des valeurs propres de . Une convention courante est de ranger les valeurs par ordre décroissant. Alors, la matrice est déterminée de façon unique par (mais et 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 est hermitienne, une caractérisation différente est envisageable. Soit une matrice n × n symétrique réelle. On pose f : Rn → R telle que f(x) = xT M x. Cette fonction est continue et atteint son maximum en un certain vecteur u quand elle est restreinte à la boule unité fermée }. D'après le théorème des multiplicateurs de Lagrange, u vérifie :
On montre facilement que la relation ci-dessus donne . Ainsi, est la plus grande valeur propre de . 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 ne sont plus nécessaires.
Preuve utilisant l'algèbre
Soit une matrice complexe m×n. Alors M*M est positive semi-définie, donc hermitienne. D'après le théorème spectral, il existe une matrice unitaire carrée de côté n, notée V, telle que : , où D est diagonale, définie positive et de même rang r que . En écrivant V de façon appropriée :
avec V1 matrice n×r de rang r et V2 matrice n×(n-r).
Ainsi, V*1M*MV1 = D, et MV2 = 0. On pose :
Alors on a :
On constate que c'est presque le résultat attendu, à ceci près que est une matrice r×m d'une isométrie partielle (). Pour achever la démonstration, on complète pour la rendre unitaire. On choisit tel que soit unitaire. Un calcul montre que :
En effet, on utilise MV2 = 0 et on constate que car et comme est unitaire, ce qui correspond au résultat attendu, en prenant pour la matrice adjointe de .
On aurait également pu commencer la démonstration en diagonalisant au lieu de , on aurait alors montré directement que et ont les mêmes valeurs propres non nulles.
Autre caractérisation
Les valeurs singulières peuvent également être caractérisées comme maxima de uTMv, considérée comme une fonction de u et v, sur des sous-espaces particuliers. Les vecteurs singuliers sont les valeurs de u et v pour lesquelles ces maxima sont atteints.
Soit M une matrice réelle m × n. Soit S et S l'ensemble des vecteurs unitaires (selon la norme 2) de Rm et Rn respectivement. On pose la fonction : , pour les vecteurs u ∈ S et v ∈ S.
On considère la fonction σ restreinte à S × S. Puisqu'à la fois S et S sont des ensembles compacts, leur produit est également compact. En outre, puisque σ est continue, elle atteint son maximum pour au moins une paire de vecteurs u ∈ S et v ∈ S. Ce maximum est noté σ1, et les vecteurs correspondants sont notés u1 et v1. Puisque σ est la plus grande valeur de σ(u,v), elle est positive : si elle était négative, en changeant le signe de u1 ou de v1, on la rendrait positive - et donc plus grande.
D'autres vecteurs singuliers et valeurs singulières peuvent être obtenus en maximisant σ(u, v) sur u, v, qui sont orthogonaux à u1 et v1, respectivement.
On peut de même traiter le cas de matrices complexes.
Valeurs singulières et vecteurs singuliers On appelle valeur singulière de toute racine carrée d'une valeur propre de , autrement dit tout réel positif σ tel qu'il existe un vecteur unitaire u dans Km et un vecteur unitaire v dans Kn vérifiant :
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, , les coefficients diagonaux de Σ sont égaux aux valeurs singulières de . Les colonnes de 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 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 Km constituée des vecteurs singuliers à gauche de ; Il est toujours possible de trouver une base unitaire pour Kn constituée des vecteurs singuliers à droite de ;
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 eiφ près (pour des réels, à un signe près). Par conséquent, si toutes les valeurs singulières de 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 et de la colonne de 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 u1 et u2 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 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 :
La décomposition en valeurs singulières de est alors :
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 et par leurs transposées, on obtient la matrice identité :
Et de même :
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 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 :
Plus généralement, étant donné une décomposition en valeurs singulières de , alors on a :
et
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 est égal au module de la valeur propre non nulle correspondante de et de . En outre, les colonnes de (vecteurs singuliers à gauche) sont vecteurs propres pour , et les colonnes de V (vecteurs singuliers à droite) sont vecteurs propres de .
Interprétation géométrique Puisque et V sont unitaires, on sait que les colonnes u1,...,um de forment une base orthonormée de Km et que les colonnes v1,...,vn de V forment une base orthonormée de Kn (par rapport au produit scalaire sur ces espaces).
La transformation linéaire T: Kn → Km, qui à chaque vecteur x associe Mx, a une expression relativement simple dans ces bases orthonormées : T(vi) = σi ui, pour i = 1,...,min(m,n), où σi est le i-ème coefficient diagonal de Σ, et T(vi) = 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 : Kn → Km, on peut trouver une base orthonormale pour Kn et une base orthonormale pour Km telles que T associe au i-ème vecteur de base de Kn un multiple positif du i-ème vecteur de base de Km, 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
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 représentent les tendances de l'ensemble d'étude (les vecteurs de 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.
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 Muller, Magaia, Herbst : « Singular Value Decomposition, Eigenfaces, and 3D reconstructions, » 2004..