SINGULÁRNA HODNOTA ROZKLADU (SVD) - TECHCODEVIEW.COM

Dekompozícia singulárnej hodnoty (SVD) matice je rozklad tejto matice na tri matice. Má niektoré zaujímavé algebraické vlastnosti a poskytuje dôležité geometrické a teoretické poznatky o lineárnych transformáciách. Má tiež niekoľko dôležitých aplikácií v dátovej vede. V tomto článku sa pokúsim vysvetliť matematickú intuíciu za SVD a jej geometrický význam.

Matematika za SVD:

SVD matice A mxn je dané vzorcom A = USigma V^T

kde:

IN: mxm matice ortonormálnych vlastných vektorov $AA^{T}$ .
V^T: transponovať a nxn matice obsahujúcej ortonormálne vlastné vektory .
: diagonálna matica s r prvkami rovnými koreňu kladných vlastných hodnôt AAᵀ alebo Aᵀ A (obe matice majú aj tak rovnaké kladné vlastné hodnoty).

Príklady

Nájdite SVD pre maticu A =
Na výpočet SVD musíme najprv vypočítať singulárne hodnoty nájdením vlastných hodnôt AA^{T}.

$A cdot A^{T} =začiatok{bmatrix} 3& 2 & 2 2& 3& -2 end{bmatrix} cdot egin{bmatrix} 3 & 2 2 & 3 2 & -2 end{bmatrix} = egin{bmatrix} 17 a 8 8 a 17 end{bmatrix}$

Charakteristická rovnica pre vyššie uvedenú maticu je:

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

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

= (lambda-25) (lambda -9)

takže naše jednotné hodnoty sú: sigma_1 = 5 , ; sigma_2 = 3

Teraz nájdeme správne singulárne vektory, tj ortonormálnu množinu vlastných vektorov A^TA. Vlastné hodnoty A^TA sú 25, 9 a 0 a keďže A^TA je symetrické, vieme, že vlastné vektory budú ortogonálne.

Pre lambda =25,

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

ktoré možno riadok zredukovať na:

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

Jednotkový vektor v jeho smere je:

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

Podobne pre lambda = 9 je vlastný vektor:

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

Pre 3. vlastný vektor by sme mohli použiť vlastnosť, že je kolmý na v1 a v2 tak, že:

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

Riešenie vyššie uvedenej rovnice na vygenerovanie tretieho vlastného vektora

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

Teraz vypočítame U pomocou vzorca u_i = frac{1}{sigma} A v_i a dostaneme U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatrix}$ . Naša konečná rovnica SVD sa teda stáva:

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

Aplikácie

Výpočet pseudoinverznej: Pseudoinverzia alebo Moore-Penrose inverzia je zovšeobecnenie inverznej matice, ktorá nemusí byť invertovateľná (ako napríklad matice nízkej úrovne). Ak je matica invertibilná, jej inverzná sa bude rovnať pseudoinverznej, ale existuje pseudoinverzná matica, ktorá nie je invertovateľná. Označuje sa 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>

Vyššie uvedená rovnica dáva pseudoinverznú hodnotu.

Riešenie množiny homogénnej lineárnej rovnice (Mx =b): ak b = 0, vypočítajte SVD a zoberte ľubovoľný stĺpec V^Tspojené s jednotnou hodnotou (in IN ) rovná 0.

If , Multiply by>

Z pseudoinverzie to vieme $M^{-1} = V W^{-1} U^{T}$

spracovanie výnimiek v jazyku Java

teda

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

Hodnosť, rozsah a nulový priestor:
- Hodnotu matice M možno vypočítať z SVD počtom nenulových singulárnych hodnôt.
- Rozsah matice M je ľavé singulárne vektory U zodpovedajúce nenulovým singulárnym hodnotám.
- Nulový priestor matice M sú pravé singulárne vektory V zodpovedajúce nulovým singulárnym hodnotám.

$M = U W V^{T}$

Problém prispôsobenia krivky: Dekompozícia singulárnych hodnôt sa môže použiť na minimalizáciu chyby najmenších štvorcov. Na jej aproximáciu používa pseudoinverziu.
Okrem vyššie uvedenej aplikácie možno pri digitálnom spracovaní signálu a spracovaní obrazu použiť aj dekompozíciu singulárnej hodnoty a pseudoinverznú hodnotu

Implementácia:

V tomto kóde sa pokúsime vypočítať rozklad singulárnej hodnoty pomocou Numpy a Scipy. Budeme počítať SVD a tiež vykonávať pseudoinverzné. Nakoniec môžeme použiť SVD na kompresiu obrázka

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

Výkon:

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

Pôvodný vs SVD k-obrázok