SINGULIERE WAARDE-ONTLEDING (SVD)

De Singular Value Decomposition (SVD) van een matrix is een ontbinding van die matrix in drie matrices. Het heeft een aantal interessante algebraïsche eigenschappen en brengt belangrijke geometrische en theoretische inzichten over lineaire transformaties over. Het heeft ook enkele belangrijke toepassingen in de datawetenschap. In dit artikel zal ik proberen de wiskundige intuïtie achter SVD en de geometrische betekenis ervan uit te leggen.

Wiskunde achter SVD:

De SVD van mxn-matrix A wordt gegeven door de formule A = USigma V^T

waar:

IN: MXM matrix van de orthonormale eigenvectoren van $AA^{T}$ .
IN^T: transponeren van a nxn matrix met de orthonormale eigenvectoren van .
: diagonale matrix met r elementen gelijk aan de wortel van de positieve eigenwaarden van AAᵀ of Aᵀ A (beide matrices hebben sowieso dezelfde positieve eigenwaarden).

Voorbeelden

Zoek de SVD voor de matrix A =
Om de SVD te berekenen, moeten we eerst de singuliere waarden berekenen door de eigenwaarden van AA^{T} te vinden.

$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 & 8 8 & 17 end{bmatrix}$

De karakteristieke vergelijking voor de bovenstaande matrix is:

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

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

= (lambda-25)(lambda -9)

dus onze unieke waarden zijn: sigma_1 = 5 , ; sigma_2 = 3

Nu vinden we de juiste singuliere vectoren, d.w.z. de orthonormale set eigenvectoren van A^TA. De eigenwaarden van A^TA is 25, 9 en 0, en aangezien A^TA is symmetrisch, we weten dat de eigenvectoren orthogonaal zullen zijn.

Voor lambda =25,

Linux hernoemen map

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

wat rij-reduceerbaar kan zijn tot:

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

Een eenheidsvector in de richting ervan is:

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

Op dezelfde manier is voor lambda = 9 de eigenvector:

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

Voor de derde eigenvector kunnen we de eigenschap gebruiken dat deze loodrecht op v1 en v2 staat, zodat:

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

Het oplossen van de bovenstaande vergelijking om de derde eigenvector te genereren

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

Nu berekenen we U met de formule u_i = frac{1}{sigma} A v_i en dit geeft U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatrix}$ . Daarom wordt onze uiteindelijke SVD-vergelijking:

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

Toepassingen

Berekening van pseudo-inverse: Pseudo-inverse of Moore-Penrose-inverse is de generalisatie van de matrixinverse die mogelijk niet omkeerbaar is (zoals matrices van lage rang). Als de matrix inverteerbaar is, zal de inverse ervan gelijk zijn aan de pseudo-inverse, maar er bestaat een pseudo-inverse voor de matrix die niet inverteerbaar is. Het wordt aangegeven met 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>

De bovenstaande vergelijking geeft de pseudo-inverse.

Een reeks homogene lineaire vergelijkingen oplossen (Mx = b): als b=0, bereken dan SVD en neem een willekeurige kolom van V^Tgeassocieerd met een enkele waarde (in IN ) gelijk aan 0.

If , Multiply by>

Van de pseudo-inverse weten we dat $M^{-1} = V W^{-1} U^{T}$

Vandaar,

Vlc mediaspeler download youtube

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

Rang, bereik en nulruimte:
- De rangorde van matrix M kan worden berekend op basis van SVD door het aantal niet-nul singuliere waarden.
- Het bereik van matrix M is de linker singuliere vector van U die overeenkomt met de niet-nul singuliere waarden.
- De nulruimte van matrix M is de rechter singuliere vector van V die overeenkomt met de op nul gestelde singuliere waarden.

$M = U W V^{T}$

Curve-aanpassingsprobleem: Singuliere waarde-ontleding kan worden gebruikt om de kleinste kwadratenfout te minimaliseren. Het gebruikt de pseudo-inverse om het te benaderen.
Naast de bovenstaande toepassing kunnen decompositie van enkelvoudige waarden en pseudo-inverse ook worden gebruikt bij digitale signaalverwerking en beeldverwerking

Implementatie:

In deze code proberen we de ontbinding van de enkelvoudige waarde te berekenen met behulp van Numpy en Scipy. We zullen SVD berekenen en ook pseudo-inverse uitvoeren. Uiteindelijk kunnen we SVD toepassen voor het comprimeren van de afbeelding

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

Uitgang:

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

Origineel versus SVD k-beeld

TechCodeview

Voorbeelden

Toepassingen

Implementatie:

Python3