DESCOMPUNEREA VALORII SINGULARE (SVD) - TECHCODEVIEW.COM

Descompunerea valorii singulare (SVD) a unei matrice este o factorizare a acelei matrice în trei matrici. Are câteva proprietăți algebrice interesante și transmite perspective geometrice și teoretice importante despre transformările liniare. Are, de asemenea, câteva aplicații importante în știința datelor. În acest articol, voi încerca să explic intuiția matematică din spatele SVD și semnificația sa geometrică.

Matematica în spatele SVD:

SVD a matricei mxn A este dată de formula A = USigma V^T

Unde:

ÎN: mxm matricea vectorilor proprii ortonormali ai $AA^{T}$ .
ÎN^T: transpunerea lui a nxn matrice conţinând vectorii proprii ortonormali ai .
: matrice diagonală cu r elemente egale cu rădăcina valorilor proprii pozitive ale lui AAᵀ sau Aᵀ A (ambele matrice au oricum aceleași valori proprii pozitive).

Exemple

Găsiți SVD pentru matricea A =
Pentru a calcula SVD, mai întâi, trebuie să calculăm valorile singulare prin găsirea valorilor proprii ale 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 și 8 8 și 17 end{bmatrix}$

Ecuația caracteristică pentru matricea de mai sus este:

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

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

= (lambda-25)(lambda -9)

deci valorile noastre singulare sunt: sigma_1 = 5 , ; sigma_2 = 3

Acum găsim vectorii singulari corecti, adică setul ortonormal de vectori proprii ai lui A^TA. Valorile proprii ale lui A^TA sunt 25, 9 și 0 și deoarece A^TA este simetric, știm că vectorii proprii vor fi ortogonali.

Pentru lambda =25,

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

care poate fi reducere de rând la:

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

Un vector unitar în direcția acestuia este:

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

În mod similar, pentru lambda = 9, vectorul propriu este:

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

Pentru al 3-lea vector propriu, am putea folosi proprietatea că este perpendicular pe v1 și v2 astfel încât:

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

Rezolvarea ecuației de mai sus pentru a genera al treilea vector propriu

$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}$

Acum, calculăm U folosind formula u_i = frac{1}{sigma} A v_i și aceasta dă U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}} și frac{-1 }{sqrt{2}} end{bmatrix}$ . Prin urmare, ecuația noastră finală SVD devine:

$A = egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}} și 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}$

Aplicații

Calculul pseudo-invers: Pseudo inversă sau inversă Moore-Penrose este generalizarea inversului matricei care poate să nu fie inversabilă (cum ar fi matricele de rang scăzut). Dacă matricea este inversabilă, atunci inversul său va fi egal cu Pseudo inversă, dar există pseudo inversă pentru matricea care nu este inversabilă. Este notat cu 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>

Ecuația de mai sus dă pseudo-inversul.

Rezolvarea unei mulțimi de ecuații liniare omogene (Mx =b): dacă b=0, calculați SVD și luați orice coloană a lui V^Tasociat cu o valoare singulară (în ÎN ) egal cu 0.

If , Multiply by>

Din Pseudo-invers, știm că $M^{-1} = V W^{-1} U^{T}$

Prin urmare,

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

hashmap în java

Rang, interval și spațiu nul:
- Rangul matricei M poate fi calculat din SVD prin numărul de valori singulare diferite de zero.
- Domeniul matricei M este Vectorii singulari stângi ai lui U corespunzând valorilor singulare diferite de zero.
- Spațiul nul al matricei M este Vectorii singulari drepti ai lui V corespunzători valorilor singulare zero.

$M = U W V^{T}$

Problema de ajustare a curbei: Descompunerea valorii singulare poate fi utilizată pentru a minimiza eroarea cel mai mic pătrat. Folosește pseudo-inversul pentru a o aproxima.
Pe lângă aplicația de mai sus, descompunerea valorii singulare și pseudo-inversa pot fi utilizate și în procesarea semnalului digital și procesarea imaginilor

Implementare:

În acest cod, vom încerca să calculăm descompunerea valorii singulare folosind Numpy și Scipy. Vom calcula SVD și vom efectua, de asemenea, pseudo-invers. În final, putem aplica SVD pentru comprimarea imaginii

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()>

Ieșire:

[[ 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]]) --------------------------->

Imaginea k originală vs SVD