Valeurs singulières  (Décomposition en)

Une matrice est un tableau de nombres dont il est difficile d'extraire les caractéristiques intéressantes pour résoudre un problème donné. Une stratégie efficace et générale pour mettre en évidence les propriétés d'une matrice est de la décomposer (ou "factoriser") en un produit de matrices plus simples et dont les caractéristiques sont clairement identifiables et interprétables.

Nous avons déjà vu trois exemples d'une telle approche :

    * La décomposition spectrale d'une matrice symétrique.

    * La factorisation de Cholesky d'une matrice semi-définie positive.

    * La décomposition d'une matrice sous forme normale.

Décomposition en Valeurs Singulières

La factorisation la plus générale et peut-être la plus utile est la Décomposition en Valeurs Singulières (que l'on désigne souvent par son acronyme anglo-saxon "SVD", pour "Singular Value Decomposition"). Elle s'énonce ainsi :

    * Soit A une matrice quelconque de taille mxn et de rang r. Alors il existe :

        - Une matrice orthogonale U d'ordre mxm,

        - Une matrice orthogonale V d'ordre nxn,

        - Et une matrice "pseudo-diagonale" (tous les éléments hors de la diagonale principale sont nuls, mais la matrice n'est pas carrée) de dimension mxn (et donc de même dimension que A),

telles que :

Cette décomposition peut se représenter ainsi :

Cette figure illustre le cas r < n < m, mais la décomposition est absolument générale, et est également valide si m n, ou si r = inf(m, n) (c'est à dire, si A est de rang plein).

-----

La "diagonale" de  contient les valeurs singulières de A. Ce sont des nombres réels et non négatifs. Nous supposons que les lignes de U et les colonnes de V' ont été réorganisées de façon à ce que les valeurs singulières soient rangées par ordre de valeurs décroissantes le long de la diagonale.

    * La partie supérieure de la diagonale (bande rouge) contient les valeurs singulières strictement positives. Nous montrerons :

        - Que leur nombre est égal à r, le rang de A. Le rang d'une matrice est donc révélé par le nombre de valeurs singulières non nulles.

        - Qu'elles sont égales aux racines carrées positives des valeurs propres de A'A (ou de AA').

    * La partie inférieure de la diagonale (bande grise) contient les (n - r) valeurs singulières nulles.

Décomposition en Valeurs Singulières "réduite"

 contient surtout des 0, ce qui suggère qu'il doit exister une version "réduite" de SVD où la plupart des 0 seraient éliminés. C'est bien le cas, et la version réduite de SVD se décrit de la façon suivante :

soit :

A = U₁V'₁

Elle s'obtient simplement :

    * En amputant U de ses (m - r) colonnes de droite.

    * En amputant V de ses (n - r) colonnes de droite (et donc U' de ses (n - r) lignes inférieures).

    * En ne conservant de  que la partie carrée supérieure gauche contenant les valeurs propres strictement positives. Le résultat est la matrice  de l'illustration ci-dessus.

La forme réduite de SVD est équivalente à la forme "pleine", qui s'obtient à partir de la forme réduite :

    * En ajoutant à U₁ (m - r) colonnes constituées de vecteurs orthonormaux perpendiculaires aux vecteurs de U₁, par exemple par la procédure d'orthogonalisation de Gram-Schmidt. Nous montrerons que, en dehors de cette contrainte d'orthonormalité, le choix de ces vecteurs complémentaires est sans influence sur la validité de la décomposition pleine, qui n'est donc pas unique.

    * De même, en ajoutant à V₁ (n - r) colonnes constituées de vecteurs orthonormaux perpendiculaires aux vecteurs de V₁,

    * Enfin, en convertissant  en  en mettant des 0 aux endroits appropriés.

-----

On peut montrer que la SVD réduite est unique si et seulement si toutes les valeurs singulières strictement positives sont distinctes.

Valeurs singulières et vecteurs singuliers

Les concepts de "valeurs propres" et de "vecteurs propres" n'ont de sens que pour des matrices carrées. Pour des matrices quelconques, ces notions se généralisent en celles de valeurs singulières et de vecteurs singuliers.

Un nombre positif s est dit être une "valeur singulière" de la matrice A mxn s'il existe deux vecteurs :

    * u de Rⁿ,  et

    * v de R^m,

tels que :

    * u sera dit être un "vecteur singulier gauche", et

    * v sera dit être un "vecteur singulier droite".

Nous montrerons que :

Interprétations géométriques de la Décomposition en Valeurs Singulières

La Décomposition en Valeurs Singulières peut s'interpréter géométriquement de diverses façons qui rendent plus compréhensible sa structure quelque peu abstraite. Nous donnons ci-dessous deux de ces interprétations.

Mécanisme d'un opérateur linéaire

Toute matrice mxn peut être interprétée comme étant la représentation matricielle d'un opérateur linéaire de Rⁿ dans R^m.

Soit alors une matrice A dont nous considérons la SVD :

    * U étant orthogonale, ses colonnes forment une base orthonormée de R^m.

    * V étant orthogonale, ses colonnes (les lignes de V' ) forment une base orthonormée de Rⁿ.

Un expression telle que Av =  su (voir ci-dessus) reçoit alors l'interprétation géométrique suivante : l'image dans R^m d'un vecteur singulier droit de Rⁿ est égal à s fois le vecteur singulier gauche associé à la valeur singulière s.

Soit alors x un vecteur de Rⁿ quelconque. Pour simplifier, supposons que A soit de rang plein, disons n ( m).

Alors pour obtenir Ax, il suffit de :

    * Projeter x sur la base de Rⁿ constituée des n vecteurs colonnes de V (les vecteurs singuliers droits). Les valeurs des projections sont les coordonnées de x dans cette base.

    * Multiplier chacune de ces n coordonnées par la valeurs singulière correspondante..

    * Utiliser les nombres ainsi obtenus comme coordonnées d'un vecteur y sur les n premiers vecteurs singuliers gauches dans R^m (les n premières colonnes de U ).

    * Affecter la valeur "0" aux (m - n) coordonnées restantes de y (sur les (m - n) dernières colonnes de U).

Alors y est le vecteur cherché Ax.

La figure ci-dessous illustre ce processus pour la première coordonnée v₁ d'un vecteur x (avec n = 2 et m = 3).

Quel que soit le vecteur x, sa troisième coordonnée dans R³ (sur u₃ ) sera toujours nulle. Il est important de remarquer que ceci n'est vrai qu'en raison du choix très particulier de la base dans R³ (c.à.d. des colonnes de la matrice U).

Nous laissons au lecteur le soin de déterminer comment cette interprétation doit être modifiée :
   * Si m < n.
   * Si A n'est pas de rang plein.

-----

Cette interprétation géométrique permet de bien comprendre les rôles respectifs de U₁ et V₁ de la forme réduite. Nous ne supposons plus maintenant que A soit de rang plein.

    * Oublions provisoirement les concepts de base et de matrice pour ne retenir que celui d' "opérateur linéaire de Rⁿ dans R^m".

        - L'ensemble des vecteurs de Rⁿ dont l'image dans R^m est le vecteur nul est un sous-espace vectoriel de Rⁿ appelé le noyau de l'opérateur.

        - L'ensemble des transformés des vecteurs de Rⁿ est un certain sous-espace vectoriel de R^m appelé l'image de l'opérateur. Sa dimension est au plus n, mais peut être strictement inférieure à n. Autrement dit, la dimension de l'image d'un opérateur peut être inférieure à la dimension de l'espace de départ : un opérateur linéaire peut "écraser" les dimensions. La dimension de Image s'appelle le rang de l'opérateur.

On montre que :

dim(Image) + dim(Noyau) = n

        - Tout vecteur de Rⁿ peut se décomposer de façon unique en la somme d'un vecteur du noyau, et d'un vecteur appartenant au sous-espace supplémentaire orthogonal du noyau (l'ensemble des vecteurs orthogonaux à tous les vecteurs du noyau), que nous noterons (Noyau)^z. Un vecteur de Rⁿ a le même transformé que sa projection sur (Noyau)^z, qui est donc le seul sous-espace "actif" de Rⁿ :  l'opérateur linéaire est entièrement défini par son action sur (Noyau)^z, qui est projeté de façon bijective sur (Image).

Toute base de (Noyau)^z et toute base de (Image) peuvent alors être utilisées pour définir l'opérateur sous forme matricielle.

    * Mais la SVD réduite nous dit que :

        - Il existe une certaine base orthonormée (de dimension r) de (Noyau)^z, matérialisée par les colonnes de V₁ (les lignes de V'₁),

        - Et une certaine base orthonormée (également de dimension r) de (Image), matérialisée par les colonnes de U₁,

telles que l'action de l'opérateur sur le vecteur x se résume à :

        - Projeter x sur la base V₁ de (Noyau)^z.

        - Multiplier les r coordonnées ainsi obtenues par les valeurs singulières correspondantes (qui sont non nulles).

        - Utiliser ces nouvelles valeurs comme coordonnées du vecteur Ax dans la base U₁ de (Image).

        - Pour passer à la forme pleine de SVD, compléter les bases de façon quelconque qui garantisse l'orthonormalité des bases complètes, et ajouter des coordonnées nulles à l'image de x.

-----

La SVD réduite donne donc du fonctionnement d'un opérateur linéaire une description complète, à la fois analytique et opérationnelle. Elle est vraiment au

cœur du fonctionnement d'un opérateur linéaire, la forme pleine de SVD n'étant que la version réduite complétée par des bases non véritablement essentielles.

Transformation de la sphère unité

Dans Rⁿ, considérons l'ensemble des vecteurs de longueur 1 : leurs extrémités forment la sphère unité (voir illustration ci-dessous) de dimension n.

On montre que les extrémités des transformés de ces vecteurs par A :

    * Forment un ellipsoïde de dimension r.

    * Les directions des axes principaux de l'ellispsoïde sont données par les colonnes de U₁ (et leurs antécédents par les colonnes de V₁ ).

    * Et que les longueurs de ces demi-axes principaux sont les valeurs singulières non nulles de A.

SVD et le Théorème d'Eckart-Young

En développant la SVD réduite d'une matrice A, on obtient :

A = _i  s_iu_iv'_i           i = 1, 2, ..., r

où les valeurs singulières sont ordonnées par valeurs décroissantes.

On remarquera la similarité formelle avec la décomposition spectrale d'une matrice symétrique.

Chacun des produits extérieurs u_iv'_i est une matrice de rang 1.

Supposons que nous ne retenions que les k premiers termes (k < r) de cette somme. Alors on peut montrer que :

A^* = _i  s_iu_iv'_i                  i = 1, 2, ..., k

est la meilleure approximation de A au sens des moindres carrés par une matrice de rang k. Aucune autre matrice de rang k ne peut rendre l'erreur quadratique d'approximation :

_ij   | a^*_ij - a_ij |²

plus faible.

Ce résultat est connu sous le nom de Théorème d'Eckart-Young. Il est à la base d'une méthode de compression d'information d'une matrice de données A (qui est alors considérée comme une table de données et non comme un opérateur linéaire).

SVD et matrices semi-définies positives

La décomposition spectrale d'une matrice semi-définie positive A s'écrit :

A = UDU'

où :

    * U est une matrice orthogonale.

    * D est la matrice diagonale des valeurs propres (non négatives) de A.

La décomposition spectrale de A est également sa Décomposition en Valeurs Singulières. En effet, les éléments diagonaux de D sont bien les racines carrées positives des valeurs propres de A'A, qui sont elle-mêmes les carrés des valeurs propres de A. Ainsi :

Ceci n'est pas vrai pour toute matrice symétrique en raison du fait que les élements diagonaux de D peuvent alors être négatifs.

Applications de la Décomposition en Valeurs Singulières

SVD est un outil d'une grande utilité dans de nombreuses circonstances.

Dans ce site, nous limiterons son application à l'Analyse en Composantes Principales (ACP) et à la Régression Ridge. Mais elle est pratiquement indispensable dès qu'il faut :

    * Calculer le rang d'une matrice, qui est alors égal au nombre de valeurs singulières non nulles.

    * Identifier le noyau d'une matrice, qui est alors le sous-espace de Rⁿ engendré par les (n - r) vecteurs singuliers droits correspondant aux valeurs singulières nulles. Ces vecteurs forment une base orthonormée du noyau de la matrice A.

    * Identifier l'image d'une matrice (le sous-espace engendré par ses colonnes) : c'est le sous-espace de R^m engendré par les r vecteurs singuliers gauches correspondant aux valeurs singulières non nulles. Ces vecteurs forment une base orthonormée de l'image de A.

Forme normale d'une matrice

La forme normale d'une matrice est une décomposition formellement similaire à la Décomposition en Valeurs Singulières, mais moins ambitieuse : son seul objectif est de mettre en évidence le rang d'une matrice quelconque.

La factorisation d'une matrice sous forme normale est abordée ici.

________________________________________________________________

La vraie difficulté de la Décomposition en Valeurs Singulières (SVD) était de l'inventer. Mais une fois identifiée la structure de la décomposition, il est relativement simple de montrer que toute matrice peut effectivement être mise sous cette forme. C'est ce que nous faisons dans ce Tutoriel. Bien que la démonstration ne soit certainement pas triviale, elle ne représente qu'un faible prix à payer pour l'obtention d'un résulat aussi puissant et universel.

DECOMPOSITION EN VALEURS SINGULIERES (SVD)

____________________________________________________________

Voir aussi :