SINGULAR VALUE DECOMPOSITION (SVD) - TECHCODEVIEW.COM

Matriisin Singular Value Decomposition (SVD) on matriisin tekijöiden jakaminen kolmeen matriisiin. Sillä on mielenkiintoisia algebrallisia ominaisuuksia ja se välittää tärkeitä geometrisia ja teoreettisia näkemyksiä lineaarisista muunnoksista. Sillä on myös tärkeitä sovelluksia datatieteessä. Tässä artikkelissa yritän selittää SVD:n takana olevan matemaattisen intuition ja sen geometrisen merkityksen.

Matematiikka SVD:n takana:

mxn-matriisin A SVD saadaan kaavalla A = USigma V^T

missä:

SISÄÄN: mxm ortonormaalien ominaisvektorien matriisi $AA^{T}$ .
SISÄÄN^T: transponoi a nxn matriisi, joka sisältää ortonormaalit ominaisvektorit .
: diagonaalinen matriisi, jossa r elementtiä on yhtä suuri kuin AAᵀ:n tai Aᵀ A:n positiivisten ominaisarvojen juuri (molempien matriisien positiiviset ominaisarvot ovat joka tapauksessa samat).

Esimerkkejä

Etsi SVD matriisille A =
SVD:n laskemiseksi meidän on ensin laskettava singulaariarvot etsimällä AA^{T}:n ominaisarvot.

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

Yllä olevan matriisin ominaisyhtälö on:

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

json-muotoinen esimerkki

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

= (lambda-25)(lambda -9)

joten yksittäiset arvomme ovat: sigma_1 = 5 , ; sigma_2 = 3

Nyt löydämme oikeat singulaarivektorit eli ortonormaalijoukon A:n ominaisvektoreita^TA. A:n ominaisarvot^TA ovat 25, 9 ja 0, ja koska A^TA on symmetrinen, tiedämme, että ominaisvektorit ovat ortogonaalisia.

varten lambda =25,

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

lajiteltu tuple python

joka voi olla rivivähennetty arvoon:

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

Yksikkövektori sen suunnassa on:

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

Vastaavasti arvolle lambda = 9 ominaisvektori on:

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

Kolmannelle ominaisvektorille voisimme käyttää ominaisuutta, että se on kohtisuorassa v1:een ja v2:een nähden siten, että:

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

Yllä olevan yhtälön ratkaiseminen kolmannen ominaisvektorin luomiseksi

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

Nyt laskemme U kaavalla u_i = frac{1}{sigma} A v_i ja tämä antaa U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatrix}$ . Tästä syystä lopullisesta SVD-yhtälöstämme tulee:

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

prime ei koodia javassa

Sovellukset

Pseudo-inversion laskenta: Pseudoinversio tai Moore-Penrose-inversio on yleistys matriisin käänteisestä, joka ei välttämättä ole invertoitava (kuten matalan asteen matriisit). Jos matriisi on käännettävä, sen käänteinen on yhtä suuri kuin pseudoinversio, mutta pseudoinversio on olemassa matriisille, joka ei ole käännettävä. Sitä merkitään 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>

Yllä oleva yhtälö antaa pseudo-inverssin.

Homogeenisen lineaarisen yhtälön (Mx =b) ratkaiseminen: jos b = 0, laske SVD ja ota mikä tahansa sarake V:stä^Tliittyy yksikköarvoon (in SISÄÄN ) yhtä suuri kuin 0.

If , Multiply by>

Pseudo-inversistä tiedämme sen $M^{-1} = V W^{-1} U^{T}$

Siten,

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

Sijoitus, alue ja nollaväli:
- Matriisin M järjestys voidaan laskea SVD:stä nollasta poikkeavien singulaariarvojen lukumäärällä.
- Matriisin M alue on U:n vasemmanpuoleiset singulaarivektorit, jotka vastaavat nollasta poikkeavia singulaariarvoja.
- Matriisin M nollaavaruus on V:n oikeat singulaarivektorit, jotka vastaavat nollattuja singulaariarvoja.

$M = U W V^{T}$

merkkijono boolen javaan

Käyrän sovitusongelma: Yksittäisen arvon hajottamista voidaan käyttää pienimmän neliösumman virheen minimoimiseksi. Se käyttää pseudo-käänteisarvoa sen approksimointiin.
Yllä olevan sovelluksen lisäksi singulaarisen arvon hajottelua ja pseudoinversiota voidaan käyttää myös digitaalisessa signaalinkäsittelyssä ja kuvankäsittelyssä

Toteutus:

Tässä koodissa yritämme laskea Singular-arvon hajotuksen Numpyn ja Scipyn avulla. Laskemme SVD:n ja suoritamme myös pseudo-inversion. Lopulta voimme käyttää SVD:tä kuvan pakkaamiseen

Python 3

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

Lähtö:

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

Alkuperäinen vs SVD k-image