Descomposición de valores singulares (SVD) || ebooksonline.es

La descomposición en valores singulares (SVD) de una matriz es una factorización de esa matriz en tres matrices. Tiene algunas propiedades algebraicas interesantes y proporciona importantes conocimientos teóricos y geométricos sobre la transformación lineal. También tiene varias aplicaciones importantes en la ciencia de datos. En este artículo, intentaré explicar la intuición matemática detrás de SVD y su significado geométrico.

Tabla de contenidos

Matemáticas detrás de SVD

La SVD de una matriz A de mxn viene dada por la fórmula:

lugar:

tu: MXN matriz de autovectores ortonormales de $AA^{T}$ .
V^T: transponer un nxn matriz que contiene los vectores propios ortonormales de A^{T}A.
W: un nxn la matriz diagonal de los valores singulares que son las raíces cuadradas de los valores propios $A^{T}A$ .

Ejemplos

Encuentre el SVD para la matriz A = $begin{bmatriz} 3& 3 & 2 2& 3& -2 end{bmatriz}$
Para calcular el SVD, Primero, necesitamos calcular los valores singulares encontrando los valores propios de AA^{T}.

$A cdot A^{T} =begin{bmatrix} 3& 3 & 2 2& 3& -2 end{bmatrix} cdot begin{bmatrix} 3 & 2 3 & 3 2 & -2 end{bmatriz} = begin{bmatriz} 17 y 8 8 y 17 end{bmatriz}$

La ecuación característica de la matriz anterior es:

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

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

$= (lambda-25)(lambda-9)$

por lo que nuestros valores singulares son: $sigma_1 = 5 , ; sigma_2 = 3$

Ahora encontramos los vectores singulares correctos, es decir. un conjunto ortonormal de exponentes de A^TA. Valores propios A^TA es igual a 25, 9 y 0, y como A^TA es simétrico, sabemos que los vectores propios serán ortogonales.

Para $lamda =25,$

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

los excesos pueden reducirse a:

$begin{bmatriz} 1& -1& 0 0& 0& 1 0& 0& 0 end{bmatriz}$

Un vector unitario está en la dirección de:

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

De manera similar, para lambda = 9, el vector propio es:

$v_2 =begin{bmatriz} frac{1}{sqrt{18}} frac{-1}{sqrt{18}} frac{4}{sqrt{18}} end{ bmatriz}$

Para el tercer vector propio, podríamos usar la propiedad de que es perpendicular a v1 y v2 como:

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

Resuelva la ecuación anterior para generar el tercer vector propio

$v_3 = begin{bmatrix} a b c end{bmatrix} = begin{bmatrix} a -a -a/2 end{bmatrix} = begin{bmatrix} frac{ 2}{3} frac{-2}{3} frac{-1}{3} end{bmatriz}$

Ahora, calculamos U usando la fórmula u_i = frac{1}{sigma} A v_i y esto da U = $begin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1 }{sqrt{2}} end{bmatriz}$ . Por lo tanto, nuestra ecuación SVD final se convierte en:

$A =A = begin{bmatrix} frac{1}{sqrt{2}} &frac{1}{sqrt{2}} frac{1}{sqrt{2}}& frac{-1}{sqrt{2}} end{bmatrix} begin{bmatrix} 5 & 0& 0 0 & 3& 0 end{bmatrix} begin{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{bmatriz}$

Aplicaciones

Calcular pseudo-inverso: Una pseudo inversa o inversa de Moore-Penrose es una generalización de la matriz inversa que puede no ser invertible (como las matrices de bajo rango). Si la matriz es invertible su inversa será igual a Pseudo inversa pero existe una falsa inversa para la matriz que no es invertible. Se define por A⁺.

Supongamos que necesitamos calcular la falsa inversa de la matriz M:

Entonces, la SVD de M se puede dar como:

$M = UWV^{T}$

Multiplica ambos lados por M^{-1}.

$M^{-1} M = M^{-1} UWV^{T}$

$I= M^{-1} UWV^{T}$

Multiplica ambos lados por V:

$V = M^{-1} UWV^{T}V$

$V = M^{-1} UW$

Multiplica por W^{-1}. Como W es la matriz singular, existe una inversa de W $= dios(a_1, a_2, a_3, ... a_n)^{-1}$ sí $= dios(1/a_1, 1/a_2, 1/a_3, ... 1/a_n)$

$VW^{-1} = M^{-1} UWW^{-1}$

$VW^{-1} = M^{-1} U$

aumentarlo $U ^ T$

$VW^{-1} U^{T} = M^{-1} UU^{T}$

$VW^{-1} U^{T} = M^{-1} = M^{+}$

La ecuación anterior da la pseudo-inversa.

Solución de una Ecuación Lineal Homogénea (Mx = b): si b=0, calcule SVD y tome cualquier columna de V^T en relación con un valor singular (es decir, W) igual a 0.

Dos $b neq 0$ , $MX = b$

aumentarlo $M^{-1}$

$METRO^{-1} METRO x = METRO^{-1} segundo$

$x = M^{-1} segundo$

Por la Pseudo-inversa, sabemos que $M^{-1} = VW^{-1} U^{T}$

Desde allí,

$x = VW^{-1} U^{T}b$

Clase, rango y espacio nulo:
- El rango de la matriz M se puede calcular a partir de SVD por el número de valores singulares distintos de cero.
- La matriz de rango M son los vectores singulares izquierdos de U correspondientes a los valores singulares distintos de cero.
- El espacio nulo de la matriz M son los vectores singulares del lado derecho de V correspondientes a los valores cero singulares.

$M = UWV^{T}$

Problema de ajuste de curvas: La descomposición de valores singulares se puede utilizar para minimizar el error de mínimos cuadrados. Utiliza el pseudo inverso para aproximarlo.
Además de la aplicación anterior, la descomposición en valores singulares y la pseudoinversa también se pueden utilizar en el procesamiento de señales digitales y el procesamiento de imágenes.

Implementación

En este código, intentaremos calcular la descomposición automática de valores usando Numpy y Scipy. Calcularemos SVD y también realizaremos una pseudo-inversa. Finalmente, podemos aplicar SVD para comprimir la imagen

Python3

# Imports
import numpy as np
from scipy.linalg import svd
"""
Singular Value Decomposition
"""
# define a matrix
X = notario público.  editar ([[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",s)
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(A.shape)
s_inv[0][0]= inv_singular[0]
s_inv[1][1] =inv_singular[1]
# calculate pseudoinverse
M = np.dot(np.dot(V_transpose.T,s_inv.T),U.T)
print(M)
"""
SVD on image compression
"""
import numpy as np
import matplotlib.pyplot as plt
from skimage import data
from skimage.color import rgb2gray
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 =tu[:, :r] @S[0:r, :r] @VERMONT[:r, :]
  hacha[curr_fig][0].imshow(256-cat_approx)
  hacha[curr_fig][0].set_title("k = "+str(r))
  hacha[curr_fig,0].  espalda ('off')
  hacha[curr_fig][1].set_title("Original Image")
  hacha[curr_fig][1].imshow(gato_gris)
  hacha[curr_fig,1].  espalda ('off')
  curr_fig +=1
plt.show()

Producción:

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

Imagen original vs SVD k-imagen

Referencias:

ejemplo SVD

Recomendado

Resolviendo problemas de DSA en GfG Practice.

Resolviendo problemas

Mis notas personales