SINGULARWERTZERLEGUNG (SVD)

Die Singular Value Decomposition (SVD) einer Matrix ist eine Faktorisierung dieser Matrix in drei Matrizen. Es verfügt über einige interessante algebraische Eigenschaften und vermittelt wichtige geometrische und theoretische Erkenntnisse über lineare Transformationen. Es gibt auch einige wichtige Anwendungen in der Datenwissenschaft. In diesem Artikel werde ich versuchen, die mathematische Intuition hinter SVD und seine geometrische Bedeutung zu erklären.

Mathematik hinter SVD:

Die SVD der mxn-Matrix A wird durch die Formel angegeben A = USigma V^T

Wo:

IN: mxm Matrix der orthonormalen Eigenvektoren von $AA^{T}$ .
IN^T: transponieren von a nxn Matrix, die die orthonormalen Eigenvektoren von enthält .
: Diagonalmatrix mit r Elementen gleich der Wurzel der positiven Eigenwerte von AAᵀ oder Aᵀ A (beide Matrizen haben ohnehin die gleichen positiven Eigenwerte).

Beispiele

Finden Sie die SVD für die Matrix A =
Um die SVD zu berechnen, müssen wir zunächst die Singulärwerte berechnen, indem wir Eigenwerte von AA^{T} ermitteln.

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

Die charakteristische Gleichung für die obige Matrix lautet:

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

Alter von Pete Davidson

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

tostring Java-Methode

= (lambda-25)(lambda -9)

Unsere einzigartigen Werte sind also: sigma_1 = 5 , ; sigma_2 = 3

Jetzt finden wir die richtigen singulären Vektoren, d. h. den orthonormalen Satz der Eigenvektoren von A^TA. Die Eigenwerte von A^TA sind 25, 9 und 0, und da A^TA ist symmetrisch, wir wissen, dass die Eigenvektoren orthogonal sein werden.

Für lambda=25,

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

was zeilenreduziert werden kann zu:

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

Ein Einheitsvektor in seiner Richtung ist:

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

Ebenso ist für lambda = 9 der Eigenvektor:

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

Für den 3. Eigenvektor könnten wir die Eigenschaft verwenden, dass er senkrecht zu v1 und v2 steht, sodass:

Java instanziiert

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

Lösen Sie die obige Gleichung, um den dritten Eigenvektor zu erzeugen

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

Jetzt berechnen wir U mit der Formel u_i = frac{1}{sigma} A v_i und das ergibt U = $egin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatrix}$ . Daher lautet unsere endgültige SVD-Gleichung:

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

wie man in Java einen String in int umwandelt

Anwendungen

Berechnung der Pseudoinversen: Pseudoinvers oder Moore-Penrose-Invers ist die Verallgemeinerung der Matrixinversen, die möglicherweise nicht invertierbar ist (z. B. Matrizen mit niedrigem Rang). Wenn die Matrix invertierbar ist, ist ihre Umkehrung gleich Pseudoinvers, aber für die Matrix, die nicht invertierbar ist, existiert eine Pseudoinverse. Es wird mit A bezeichnet⁺.

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>

Die obige Gleichung ergibt die Pseudoinverse.

Lösen eines Satzes homogener linearer Gleichungen (Mx =b): Wenn b=0, berechnen Sie SVD und nehmen Sie eine beliebige Spalte von V^Tmit einem singulären Wert verbunden (in IN ) gleich 0.

If , Multiply by>

Aus der Pseudo-Inversen wissen wir das $M^{-1} = V W^{-1} U^{T}$

Somit,

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

Rang, Bereich und Nullraum:
- Der Rang der Matrix M kann aus SVD anhand der Anzahl der Singulärwerte ungleich Null berechnet werden.
- Der Bereich der Matrix M ist die linken Singulärvektoren von U, die den Singulärwerten ungleich Null entsprechen.
- Der Nullraum der Matrix M besteht aus den rechten Singulärvektoren von V, die den auf Null gesetzten Singulärwerten entsprechen.

$M = U W V^{T}$

Iterator-Java-Karte

Kurvenanpassungsproblem: Die Singulärwertzerlegung kann verwendet werden, um den kleinsten quadratischen Fehler zu minimieren. Es verwendet die Pseudoinverse, um es anzunähern.
Neben der oben genannten Anwendung können Singulärwertzerlegung und Pseudoinverse auch in der digitalen Signalverarbeitung und Bildverarbeitung verwendet werden

Implementierung:

In diesem Code werden wir versuchen, die Singularwertzerlegung mit Numpy und Scipy zu berechnen. Wir werden die SVD berechnen und auch eine Pseudoinverse durchführen. Am Ende können wir SVD zum Komprimieren des Bildes anwenden

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

Ausgabe:

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

Original vs. SVD-K-Image

TechCodeview

Beispiele

Anwendungen

Implementierung:

Python3