DEKOMPOZYCJA WARTOŚCI OSOBLIWYCH (SVD) - TECHCODEVIEW.COM

Rozkład wartości osobliwych (SVD) macierzy to rozkład tej macierzy na czynniki na trzy macierze. Ma kilka interesujących właściwości algebraicznych i przekazuje ważne spostrzeżenia geometryczne i teoretyczne na temat przekształceń liniowych. Ma również kilka ważnych zastosowań w nauce danych. W tym artykule postaram się wyjaśnić matematyczną intuicję stojącą za SVD i jej geometryczne znaczenie.

Matematyka za SVD:

SVD macierzy A mxn jest określona wzorem A = USigma V^T

Gdzie:

W: mxm macierz ortonormalnych wektorów własnych $AA^{T}$ .
W^T: transpozycja a nxn macierz zawierająca ortonormalne wektory własne .
: macierz diagonalna z r elementami równymi pierwiastkowi z dodatnich wartości własnych AAᵀ lub Aᵀ A (i tak obie macierze mają te same dodatnie wartości własne).

Przykłady

Znajdź SVD dla macierzy A =
Aby obliczyć SVD, najpierw musimy obliczyć wartości osobliwe, znajdując wartości własne AA^{T}.

$A cdot A^{T} =egin{bmatrix} 3& 2 i 2 2& 3& -2 end{bmatrix} cdot egin{bmatrix} 3 i 2 2 i 3 2 i -2 end{bmatrix} = egin{bmatrix} 17 i 8 8 i 17 end{bmatrix}$

Równanie charakterystyczne dla powyższej macierzy to:

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

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

= (lambda-25)(lambda -9)

więc nasze wartości osobliwe to: sigma_1 = 5 , ; sigma_2 = 3

Teraz znajdujemy odpowiednie wektory osobliwe, czyli ortonormalny zbiór wektorów własnych A^TA. Wartości własne A^TA to 25, 9 i 0, a ponieważ A^TA jest symetryczne, wiemy, że wektory własne będą ortogonalne.

Dla lambda =25,

Edyta Mack Hirsch

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

które można zredukować do wiersza:

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

Wektor jednostkowy w jego kierunku to:

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

Podobnie dla lambda = 9 wektor własny ma postać:

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

W przypadku trzeciego wektora własnego moglibyśmy skorzystać z własności prostopadłości do v1 i v2 w taki sposób, że:

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

Rozwiązanie powyższego równania w celu wygenerowania trzeciego wektora własnego

$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 obliczamy U za pomocą wzoru u_i = frac{1}{sigma} A v_i i to daje U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmacierz}$ . Stąd nasze końcowe równanie SVD ma postać:

$A = egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{ -1}{sqrt{2}} end{bmatrix} egin{bmatrix} 5 i 0& 0 0 i 3& 0 end{bmatrix} egin{bmatrix} frac{1}{sqrt{2 }}& frac{1}{sqrt{2}} &0 frac{1}& frac{18}& frac{-1}{sqrt{18}} & frac{4} {sqrt{18}} frac{2}{3}&frac{-2}{3} &frac{1}{3} end{bmatrix}$

Aplikacje

Obliczanie pseudoodwrotności: Pseudoodwrotność lub odwrotność Moore'a-Penrose'a to uogólnienie odwrotności macierzy, która może nie być odwracalna (np. macierze niskiego rzędu). Jeśli macierz jest odwracalna, to jej odwrotność będzie równa pseudoodwrotności, ale pseudoodwrotność istnieje dla macierzy, która nie jest odwracalna. Oznacza to 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>

Powyższe równanie daje pseudoodwrotność.

Rozwiązywanie układu jednorodnego równania liniowego (Mx =b): jeśli b=0, oblicz SVD i weź dowolną kolumnę V^Tpowiązany z pojedynczą wartością (w W ) równe 0.

If , Multiply by>

Wiemy to z pseudoodwrotności $M^{-1} = V W^{-1} U^{T}$

Stąd,

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

Ranga, zasięg i przestrzeń zerowa:
- Rangę macierzy M można obliczyć z SVD na podstawie liczby niezerowych wartości osobliwych.
- Zakres macierzy M to lewe wektory osobliwe U odpowiadające niezerowym wartościom osobliwym.
- Przestrzenią zerową macierzy M są prawe wektory osobliwe V odpowiadające wyzerowanym wartościom osobliwym.

$M = U W V^{T}$

Problem z dopasowaniem krzywej: Aby zminimalizować błąd najmniejszych kwadratów, można zastosować rozkład wartości osobliwych. Do przybliżenia używa pseudoodwrotności.
Oprócz powyższego zastosowania, rozkład wartości osobliwych i pseudoodwrotność mogą być również stosowane w cyfrowym przetwarzaniu sygnału i przetwarzaniu obrazu

Realizacja:

W tym kodzie spróbujemy obliczyć rozkład wartości Singular za pomocą Numpy i Scipy. Będziemy obliczać SVD, a także wykonywać pseudoodwrotność. Na koniec możemy zastosować SVD do kompresji obrazu

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

Wyjście:

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

Obraz oryginalny vs SVD k