DEKOMPOZICE SINGULÁRNÍ HODNOTY (SVD) - TECHCODEVIEW.COM

Dekompozice singulární hodnoty (SVD) matice je rozklad této matice na tři matice. Má některé zajímavé algebraické vlastnosti a přináší důležité geometrické a teoretické poznatky o lineárních transformacích. Má také některé důležité aplikace v datové vědě. V tomto článku se pokusím vysvětlit matematickou intuici za SVD a její geometrický význam.

Matematika za SVD:

SVD matice A mxn je dáno vzorcem A = USigma V^T

kde:

V: mxm matice ortonormálních vlastních vektorů $AA^{T}$ .
V^T: transponovat a nxn matice obsahující ortonormální vlastní vektory .
: diagonální matice s r prvky rovnými odmocnině kladných vlastních hodnot AAᵀ nebo Aᵀ A (obě matice mají stejně kladná vlastní čísla).

Příklady

Najděte SVD pro matici A =
Abychom vypočítali SVD, musíme nejprve vypočítat singulární hodnoty nalezením vlastních čísel 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 & 8 8 & 17 end{bmatrix}$

Charakteristická rovnice pro výše uvedenou matici 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 singulární hodnoty jsou: sigma_1 = 5 , ; sigma_2 = 3

Nyní najdeme správné singulární vektory, tj. ortonormální množinu vlastních vektorů A^TA. Vlastní čísla A^TA jsou 25, 9 a 0, a protože A^TA je symetrické, víme, že vlastní vektory budou ortogonální.

Pro lambda =25,

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

který může být řádek-redukován na:

liška vs vlk

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

Jednotkový vektor v jeho směru je:

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

Podobně pro lambda = 9 je vlastní vektor:

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

Pro 3. vlastní vektor bychom mohli použít vlastnost, že je kolmý na v1 a v2, takže:

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

Řešení výše uvedené rovnice pro generování třetího vlastního vektoru

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

Nyní vypočítáme U pomocí vzorce 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še konečná rovnice SVD tedy bude:

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

Aplikace

Výpočet pseudoinverze: Pseudoinverzní nebo Moore-Penrose inverze je zobecnění maticové inverze, která nemusí být invertibilní (jako jsou matice nízké úrovně). Pokud je matice invertibilní, pak její inverzní bude rovna pseudoinverzní, ale pseudoinverzní existuje pro matici, která není invertibilní. Označuje se 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>

Výše uvedená rovnice dává pseudoinverzní.

Řešení sady Homogenní lineární rovnice (Mx =b): pokud b=0, vypočítejte SVD a vezměte libovolný sloupec V^Tspojené s jednotnou hodnotou (in V ) rovno 0.

If , Multiply by>

Z Pseudoinverze to víme $M^{-1} = V W^{-1} U^{T}$

Proto,

používání internetu

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

Hodnost, rozsah a nulový prostor:
- Hodnost matice M lze vypočítat z SVD počtem nenulových singulárních hodnot.
- Rozsah matice M je Levé singulární vektory U odpovídající nenulovým singulárním hodnotám.
- Nulový prostor matice M je pravé singulární vektory V odpovídající vynulovaným singulárním hodnotám.

$M = U W V^{T}$

Problém s přizpůsobením křivky: K minimalizaci chyby nejmenších čtverců lze použít rozklad singulárních hodnot. K jeho aproximaci používá pseudoinverzní.
Kromě výše uvedené aplikace může být rozklad singulární hodnoty a pseudoinverzní také použit v digitálním zpracování signálu a zpracování obrazu

Implementace:

V tomto kódu se pokusíme vypočítat rozklad singulární hodnoty pomocí Numpy a Scipy. Budeme počítat SVD a také provádět pseudoinverzní. Nakonec můžeme použít SVD pro kompresi obrázku

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ýstup:

[[ 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ázek