Descomposición de valores singulares (SVD)

La descomposición en valores singulares (SVD) de una array es una factorización de esa array en tres arrays. Tiene algunas propiedades algebraicas interesantes y transmite importantes ideas geométricas y teóricas sobre transformaciones lineales. También tiene algunas 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.

Matemáticas detrás de SVD

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

$A = UWV^{T}$

dónde:

U: array mxn de los autovectores ortonormales de $AA^{T}$ .
V ^T : transpuesta de una array nxn que contiene los vectores propios ortonormales de A^{T}A.
W: una array diagonal nxn de los valores singulares que son las raíces cuadradas de los valores propios de $A^{T}A$ .

Ejemplos

Encuentre el SVD para la array A = $\begin{bmatrix} 3& 3 & 2 \\ 2& 3& -2 \end{bmatrix}$
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{bmatrix} = \begin{bmatrix} 17 & 8\\ 8 & 17 \end{bmatrix}$

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

$W - \lambda I =0 \\ A A^{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 vectores propios de A ^T A. Los valores propios de A ^T A son 25, 9 y 0, y dado que A ^T A es simétrico, sabemos que los vectores propios serán ortogonales.

Para $\lambda =25,$

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

que puede ser fila-reduce a:

$\begin{bmatrix} 1& -1& 0 \\ 0& 0& 1\\ 0& 0& 0 \end{bmatrix}$

Un vector unitario en la dirección de la misma es:

$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{bmatrix} \frac{1}{\sqrt{18}}\\ \frac{-1}{\sqrt{18}}\\ \frac{4}{\sqrt{18}}\\ \end{bmatrix}$

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

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

Resolviendo 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{bmatrix}$

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{bmatrix}$ . 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{bmatrix}$

Aplicaciones

Cálculo de la pseudo-inversa: la pseudo-inversa o la inversa de Moore-Penrose es la generalización de la array inversa que puede no ser invertible (como las arrays de bajo rango). Si la array es invertible, su inversa será igual a Pseudo inversa, pero existe pseudo inversa para la array que no es invertible. Se denota por A ⁺ .

Supongamos que necesitamos calcular la pseudo-inversa de una array M:

Entonces, la SVD de M se puede dar como:

$M = U W V^{T}$

Multiplica ambos lados por M^{-1}.

$M^{-1} M = M^{-1} U W V^{T}$

$I= M^{-1} U W V^{T}$

Multiplica ambos lados por V:

$V = M^{-1} U W V^{T}V$

$V = M^{-1} U W$

Multiplica por W^{-1}. Dado que W es la array singular, la inversa de W $= diag(a_1, a_2, a_3, ... a_n)^{-1}$ es $= diag(1/a_1, 1/a_2, 1/a_3, ... 1/a_n)$

$V W^{-1} = M^{-1} U W W^{-1}$

$V W^{-1} = M^{-1} U$

Multiplicar por $U^T$

$V W^{-1} U^{T} = M^{-1} U U^{T}$

$V W^{-1} U^{T} = M^{-1} = M^{+}$

La ecuación anterior da la pseudo-inversa.

Resolviendo un conjunto de Ecuaciones Lineales Homogéneas (Mx =b): si b=0, calcular SVD y tomar cualquier columna de V ^T asociada a un valor singular (en W ) igual a 0.

si $b \neq 0$ , $Mx =b$

Multiplicar por $M^{-1}$

$M^{-1} M x = M^{-1} b$

$x = M^{-1} b$

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

Por eso,

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

Rango, rango y espacio nulo:
- El rango de la array M se puede calcular a partir de SVD por el número de valores singulares distintos de cero.
- El rango de la array M es Los vectores singulares izquierdos de U correspondientes a los valores singulares distintos de cero.
- El espacio nulo de la array M es Los vectores singulares rectos de V correspondientes a los valores singulares puestos a cero.

$M = U W V^{T}$

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

Implementación

En este código, intentaremos calcular la descomposición del valor Singular usando Numpy y Scipy. Estaremos calculando SVD, y también realizando pseudo-inversa. Al final, 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 = 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",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]= 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
"""
 
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 =U[:, :r] @  S[0:r, :r] @ V_T[:r, :]
  ax[curr_fig][0].imshow(256-cat_approx)
  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)
  ax[curr_fig,1].axis('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 k original frente a SVD

Referencias:

Ejemplo SVD

Publicación traducida automáticamente

Artículo escrito por pawangfg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA