DÉCOMPOSITION EN VALEURS SINGULIÈRES (SVD)

La décomposition en valeurs singulières (SVD) d'une matrice est une factorisation de cette matrice en trois matrices. Il possède des propriétés algébriques intéressantes et transmet d’importantes informations géométriques et théoriques sur les transformations linéaires. Il a également des applications importantes dans la science des données. Dans cet article, je vais essayer d'expliquer l'intuition mathématique derrière SVD et sa signification géométrique.

Mathématiques derrière SVD :

Le SVD de la matrice mxn A est donné par la formule A = USigma V^T

où:

DANS: mxm matrice des vecteurs propres orthonormés de $AA^{T}$ .
DANS^T: transposition d'un nxn matrice contenant les vecteurs propres orthonormés de .
: matrice diagonale avec r éléments égaux à la racine des valeurs propres positives de AAᵀ ou Aᵀ A (les deux matrices ont de toute façon les mêmes valeurs propres positives).

Exemples

Trouver le SVD pour la matrice A =
Pour calculer le SVD, nous devons d'abord calculer les valeurs singulières en trouvant les valeurs propres de AA^{T}.

$A cdot A^{T} =egin{bmatrix} 3& 2 & 2 2& 3& -2 end{bmatrix} cdot egin{bmatrix} 3 & 2 2 & 3 2 & -2 end{bmatrix} = egin{bmatrix} 17 et 8 8 et 17 end{bmatrix}$

L'équation caractéristique de la matrice ci-dessus est :

$W - lambda I =0 A A^{T} - lambda I =0$

$lambda^{2} - 34 lambda + 225 =0$

= (lambda-25)(lambda -9)

nos valeurs singulières sont donc : sigma_1 = 5 , ; sigma_2 = 3

Maintenant, nous trouvons les bons vecteurs singuliers, c'est-à-dire l'ensemble orthonormé des vecteurs propres de A^TA. Les valeurs propres de A^TA valent 25, 9 et 0, et puisque A^TA est symétrique on sait que les vecteurs propres seront orthogonaux.

Pour lambda =25,

vlc télécharger youtube

$A^{T}A - 25 cdot I = egin{bmatrix} -12 & 12& 2 12 & -12 & -2 2& -2 & -17 end{bmatrix}$

qui peut être réduit en ligne à :

egin{bmatrix} 1& -1& 0 0& 0& 1 0& 0& 0 end{bmatrix}

Un vecteur unitaire dans sa direction est :

$v_1 = egin{bmatrix} frac{1}{sqrt{2}} frac{1}{sqrt{2}} 0 end{bmatrix}$

De même, pour lambda = 9, le vecteur propre est :

$v_2 =egin{bmatrix} frac{1}{sqrt{18}} frac{-1}{sqrt{18}} frac{4}{sqrt{18}} fin{bmatrix}$

Pour le 3ème vecteur propre, on pourrait utiliser la propriété qu'il est perpendiculaire à v1 et v2 telle que :

$v_1^{T} v_3 =0 v_2^{T} v_3 =0$

Résoudre l'équation ci-dessus pour générer le troisième vecteur propre

$v_3 = egin{bmatrix} a b c end{bmatrix} = egin{bmatrix} a -a -a/2 end{bmatrix} = egin{bmatrix} frac{ 2}{3} frac{-2}{3} frac{-1}{3} end{bmatrix}$

Maintenant, on calcule U en utilisant la formule u_i = frac{1}{sigma} A v_i et cela donne U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatrix}$ . Par conséquent, notre équation SVD finale devient :

$A = egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{ -1}{sqrt{2}} end{bmatrix} egin{bmatrix} 5 & 0& 0 0 & 3& 0 end{bmatrix} egin{bmatrix} frac{1}{sqrt{2 }}& frac{1}{sqrt{2}} &0 frac{1}{sqrt{18}}& frac{-1}{sqrt{18}} & frac{4} {sqrt{18}} frac{2}{3}&frac{-2}{3} &frac{1}{3} end{bmatrix}$

Applications

Calcul du pseudo-inverse : Le pseudo-inverse ou inverse de Moore-Penrose est la généralisation de l'inverse matriciel qui peut ne pas être inversible (comme les matrices de bas rang). Si la matrice est inversible alors son inverse sera égal au pseudo inverse mais le pseudo inverse existe pour la matrice qui n'est pas inversible. Il est noté A⁺.

Suppose, we need to calculate the pseudo-inverse of a matrix M: Then, the SVD of M can be given as: Multiply both sides by M^{-1}.Multiply both side by V:Multiply by W^{-1}Since the W is the singular matrix, the inverse of W  is Multiply by>

L'équation ci-dessus donne le pseudo-inverse.

Résolution d'un ensemble d'équations linéaires homogènes (Mx =b) : si b=0, calculez SVD et prenez n'importe quelle colonne de V^Tassocié à une valeur singulière (en DANS ) égal à 0.

If , Multiply by>

Du pseudo-inverse, nous savons que $M^{-1} = V W^{-1} U^{T}$

Ainsi,

$x = V W^{-1} U^{T} b$

Rang, plage et espace nul :
- Le rang de la matrice M peut être calculé à partir de SVD par le nombre de valeurs singulières non nulles.
- La plage de la matrice M est constituée des vecteurs singuliers gauches de U correspondant aux valeurs singulières non nulles.
- L'espace nul de la matrice M est constitué des vecteurs singuliers droits de V correspondant aux valeurs singulières remises à zéro.

$M = U W V^{T}$

Problème d'ajustement de courbe : La décomposition en valeurs singulières peut être utilisée pour minimiser l’erreur des moindres carrés. Il utilise le pseudo inverse pour s’en approcher.
Outre l'application ci-dessus, la décomposition en valeurs singulières et le pseudo-inverse peuvent également être utilisés dans le traitement du signal numérique et le traitement d'images.

Mise en œuvre:

Dans ce code, nous allons essayer de calculer la décomposition en valeurs singulières en utilisant Numpy et Scipy. Nous calculerons le SVD et effectuerons également un pseudo-inverse. Au final, nous pouvons appliquer SVD pour compresser l'image

Python3

# Imports> from> skimage.color>import> rgb2gray> from> skimage>import> data> import> matplotlib.pyplot as plt> import> numpy as np> from> scipy.linalg>import> svd> '''> Singular Value Decomposition> '''> # define a matrix> X>=> np.array([[>3>,>3>,>2>], [>2>,>3>,>->2>]])> print>(X)> # perform SVD> U, singular, V_transpose>=> svd(X)> # print different components> print>(>'U: '>, U)> print>(>'Singular array'>, singular)> print>(>'V^{T}'>, V_transpose)> '''> Calculate Pseudo inverse> '''> # inverse of singular matrix is just the reciprocal of each element> singular_inv>=> 1.0> /> singular> # create m x n matrix of zeroes and put singular values in it> s_inv>=> np.zeros(X.shape)> s_inv[>0>][>0>]>=> singular_inv[>0>]> s_inv[>1>][>1>]>=> singular_inv[>1>]> # calculate pseudoinverse> M>=> np.dot(np.dot(V_transpose.T, s_inv.T), U.T)> print>(M)> '''> SVD on image compression> '''> cat>=> data.chelsea()> plt.imshow(cat)> # convert to grayscale> gray_cat>=> rgb2gray(cat)> # calculate the SVD and plot the image> U, S, V_T>=> svd(gray_cat, full_matrices>=>False>)> S>=> np.diag(S)> fig, ax>=> plt.subplots(>5>,>2>, figsize>=>(>8>,>20>))> curr_fig>=> 0> for> r>in> [>5>,>10>,>70>,>100>,>200>]:> >cat_approx>=> U[:, :r] @ S[>0>:r, :r] @ V_T[:r, :]> >ax[curr_fig][>0>].imshow(cat_approx, cmap>=>'gray'>)> >ax[curr_fig][>0>].set_title(>'k = '>+>str>(r))> >ax[curr_fig,>0>].axis(>'off'>)> >ax[curr_fig][>1>].set_title(>'Original Image'>)> >ax[curr_fig][>1>].imshow(gray_cat, cmap>=>'gray'>)> >ax[curr_fig,>1>].axis(>'off'>)> >curr_fig>+>=> 1> plt.show()>

Sortir:

[[ 3 3 2]  [ 2 3 -2]] --------------------------- U: [[-0.7815437 -0.6238505]  [-0.6238505 0.7815437]] --------------------------- Singular array [5.54801894 2.86696457] --------------------------- V^{T} [[-0.64749817 -0.7599438 -0.05684667]  [-0.10759258 0.16501062 -0.9804057 ]  [-0.75443354 0.62869461 0.18860838]] -------------------------- # Inverse  array([[ 0.11462451, 0.04347826],  [ 0.07114625, 0.13043478],  [ 0.22134387, -0.26086957]]) --------------------------->

Image k originale vs SVD

TechCodeview

Exemples

Applications

Mise en œuvre:

Python3