SVD Singular Value Decomposition
SVD Singular Value Decomposition
Historia Definicin Propiedades de SVD Ejemplo de SVD Aproximacin por Ak Mtodos para calcular SVD Aplicaciones de SVD
Historia
Intento de los geometras del siglo XIX para conseguir una reduccin de una forma cuadrtica a diagonal mediante cambios ortogonales. Eugene Beltrami - 1873
comienza forma bilineal: demuestra:
Camile Jordan -1874
max / Sol: Raiz del max valor propio
Historia
James Joseph Sylvester (1889) llega a la SVD de matrices cuadradas Reales. Independientemente de Beltrami y Jordan llama multiplicadores cannicos a los valores singulares. Erhard Schimdt 1907, teo gral de ecuaciones integrales reales. Introduce el concepto de valor propio y funcion propia de un K(x,y). Picard -1910, continua con el trabajo de Schimdt. Primero en nombrar los valores singulares.
Historia
Autonne 1915, SVD utilizando descomposicin polar. Eckart y Young 1936, SVD para matrices rectangulares complejas.
Definicion
Dada una matriz A mxn, una descomposicin SVD es una factorizacion:
Amxn= Umxm Smxn V*nxn
donde: - U y V son unitarias - S es diagonal de tamao mxn
Definicion
S es diagonal de tamao mxn
Tiene todos sus elementos = 0, menos los min(m,n) elementos de su diagonal principal. VALORES SINGULARES
min(m,n)
- Elementos reales > 0, ordenados de Mayor a Menor.
Definicion
U y V son bases unitarias u ortonormales (R)
Unitaria: si sus columnas forman una base ortonormal de vectores de Cm Ortonormal: es ortogonal y la norma de sus vectores es igual a 1 Ortogonal: si sus columnas forman una base ortogonal de vectores de Rm. => A-1=At UTU = Inxn VTV = Inxn
Repaso
x es ortogonal a y si el producto escalar entre ellos es = 0:
Producto Interno de vectores:
Definicion
A los vectores que forman las columnas de U y V se les llama: - vectores singulares de A por Izquierda - vectores singulares de A por Derecha
Teorema SVD
Toda matriz Amn admite una descomposicion en valores singulares. Ademas, los valores singulares estan determinados de forma unica.
Valores Singulares - Propiedades
rang(A) = numero de valores singulares de A distintos de cero
Si A =>
son sus valores singulares
Valores Singulares - Propiedades
Los valores singulares de A Cmn distintos de cero son las races cuadradas positivas de los valores propios distintos de cero de A*A y tambien de los de AA*.
Si A y valores singulares, entonces :
, p = mn{m, n}, son sus
Valores Singulares - Propiedades
Si es invertible y son sus valores singulares, los de A-1 seran:
Valores Singulares - Propiedades
Todo elemento de la diagonal cumple:
A=USVt es una descomposicion de A en valores singulares y rang(A) = r:
u y v son vectores col de U y V respectivamente
Valores Singulares - Observaciones
La descomposicion se puede representar como la suma de r matrices de rango 1 Al termino Dada se le llama tripleta singular podemos estimar cuantas
tripletas vamos a tener
Mas? => [Link]
Ejemplo
2 0 0 -3 = 0 0
A
0 1 0 -1 0 0 0 0 1 U
3 0 0 2 0 0 S
0 1 1 0
Vt
Ejemplo
2 0 0 -3 = 0 0
A
0 3 -1 0 u1 v1t 0 1 + 2
3 0 0 u2 v2t 1 0
Ejemplo
2 0 0 -3 = 0 0
A
0 0 3 0 -1 0 0 + 2
1 0 0 0 0 0
Aproximacion de A por Ak
Teorema: Dada A / rang(A) = r p = min (m,n) y r < p Sea: con k < r
=>
Aproximacion de A por Ak
SVD - Factorizacion
A = USVT
At.
ATA = (USVT)T (USVT) = VSTUT USVT ATA = V S2 VT
.V
ATA V = V S2
Para encontrar V y S necesitamos diagonalizar AtA buscando: Valores y Vectores Propios
Ejemplito 2x2
A = 2 -2 1 1 At A = 2 1 -2 1 2 -2 1 1 5 -3 -3 5
Valores Propios L1 = 8 L2 = 2
ATA = V S2 VT
Ejemplito 2x2 cont.
S2 = 8 0
0 2
S = 22 0
0 2
Buscamos los vectores propios de V Para L1=8 v1 = -1
1
HAY Q NORMALIZAR!
L2=2 v2 =
1 1
Ejemplito 2x2 cont.
v1 = - 2/2
2/2
v2 =
2/2 2/2
VT = - 2/2
2/2 2/2 2/2
SVD - Factorizacion
Para obtener U operamos de forma analoga:
AAT= (USVT) (USVT)T = USTVT VSUT AAT = U S2 UT
U = -1 0 0 1
Ejemplito 2x2 cont.
A = U S VT A=
-1
0 0 1
22 0 0 2
- 2/2 2/2 2/2 2/2
Calculo de SVD => Costoso! => Numericamente Inestable!
SVD - Factorizacion
GNU Scientific Library (GSL) includes gsl_linalg_SV_decomp ALGLIB includes a partial port of the LAPACK to C++, C#, Delphi, Visual Basic, etc. JAMA A Java matrix package provided by the NIST. LAPACK users manual gives details of subroutines to calculate the SVD PROPACK, computes the SVD of large and sparse or structured matrices. SVDPACK, a library in ANSI FORTRAN 77 implementing four iterative SVD methods. Includes C and C++ interfaces. SVDLIBC, re-writing of SVDPACK in C. SVD-Python, Pure Python SVD under GNU GPL. NumPy SVD part of the linalg module of the NumPy module for numerical computing in Python
Metodos para calculo SVD
Kogbetliantz 1954 Hestens 1958
Semejante al alg. de Jacobi para valores propios
Golub & Kahan 1965 1970 & Reinsch Metodo de Jacobi
Metodos para calculo SVD
Golub & Kahan
Basado en la iteracion QR Mediante transformaciones ortogonales de Householder, se intenta lleva A a una triangular superior bidiagonal
Gene Howard Golub ( 19322007)
Metodos para calculo SVD
Obtenida B se aplica un algoritmo para diagonalizarla utilizando matrices ortogonales
Se obtienen los valores singulares iterativamente aplicando:
Metodos para calculo SVD
Jacobi
Utiliza el mtodo de Jacobi para valores propios. Se aplica a matrices simtricas reales Utiliza transformaciones como rotaciones de Givens para generar pares (simtricos) de 0s en la matriz Se parte de A0 y se itera de la siguiente forma:
Donde J cumple:
Metodos para calculo SVD
Estos mtodos no son optimos para matrices dispersas especialmente de gran tamano. Aplican transformaciones ortogonales (householder o givens) directamente a la matriz A. Lo que provoca excesivo fill in. No solo implica costo de memoria sino de computacional ya q solo las tripletas mas grandes son las buscadas.
Metodos para calculo SVD
Mtodos para matrices dispersas
Metodos para calculo SVD
SISVD Subspace Iteration
Se resuelve a travs de valores propios Utiliza para ello un sub-espacio de iteracin linealmente independiente Con lo cual se puede resolver cada elemento por separado
Metodos para calculo SVD
LASVD Single Vector Lanczos
El mtodo genera una secuencia de matrices tridiagonales que intentaran mejorar progresivamente la estimacin de los valores propios extremos de AtA Se generan vectores de Lanczos quienes generan bases ortonormales en subespacios de Krylov.
Metodos para calculo SVD
BLSVD Block Lanczos
Explota la estructura de la matriz B = ATA La matriz B se transforma en una bidiagonal y de ella se obtienen la SVD
Metodos para calculo SVD
TRSVD Trace minimization
Dado el problema general de valores propios donde H = ATA y G = I Se intenta minimizar la traza de YtHY
Aplicaciones
Aproximacin de Matrices Una herramienta comn para resolver sistemas de ecuaciones homogneos. Una herramienta para diagonalizar matrices singulares o mal condicionadas Calculo rpido de la inversa de una matriz Calculo de mnimos cuadrados LSI Latent Semantic Indexing Compresin de Imgenes
Aplicaciones Matriz Inversa
Se calcula en forma rpida la inversa de una matriz A
A-1 = V S-1 UT A . A-1 = U S Vt . V S-1 Ut = I
Aplicaciones Mnimos cuadrados
Se quiere resolver Ax = b utilizando minimos cuadrados Minimizar la norma 2 de un vector / ||x||=1 Se multiplica por AT quedando ATA =ATb Se calcula la svd de A = USVT Es til y estable cuando la matriz A no es cuadrada (sera un sistema indeterminado)
Aplicaciones Latent Semantics Indexing
LSI agrega un paso importante en lo que es el proceso de indexado de documentos Adems de grabar las palabras claves que contiene cierto documento el mtodo examina la coleccin de documentos como un todo para ver que otros documentos contienen algunas de esas mismas palabras. LSI considera semnticamente parecidos a documentos que muchas de estas palabras en comn y distantes a los que no. El mtodo se puede correlacionar como lo hacen las personas, o sea, mirando el contenido podramos clasificar un conjunto de documentos. A pesar de que LSI NO entiende el significado de las palabras, el reconocimiento de patrones lo hace parecer inteligente.
Aplicaciones Latent Semantics Indexing
Algoritmo para LSI
Convertir cada documento en un vector de ocurrencias de palabras. La dimensin del vector ser igual al numero de palabras nicas en el documento. Es recomendado quitar palabras del estilo el, eso, etc. Escalar el vector de manera que cada termino refleje la frecuencia de su ocurrencia en el contexto. Se combinan estos vectores con los documentos. Donde las filas representan los trminos y las columnas los documentos. Se realiza SVD en la matriz termino-documento, obteniendo la correspondiente U,S,V. Considerar los valores mas altos de acuerdo al parmetro k. Recombinar los trminos para formar la matriz original Llevar esta matriz termino-documento de nuevo a vectores columna Se tiene un LSI
Aplicaciones Latent Semantics Indexing
Aplicaciones Latent Semantics Indexing
Aplicaciones Latent Semantics Indexing
Algunos usos puede ser para analizar similitudes entre textos asi como realizar bsquedas en documentos. Categorizar documentos: SPAM filtering! [Link]
Aplicaciones Compresion de imagenes
Usando el rang(A) se quita la informacin redundante cuando r < m o r < n (elimina el ruido)
Quitando los valores = 0 :
Los valores mas altos son los mas significativos
Aplicaciones Compresion de imagenes
Recordemos
Aplicaciones Compresion de imagenes
Utilizando Matlab >>A=randint(7,7,25,5)+25 Obtenemos una matriz de 7x7 (A) con valores [0,50] y rang(A) = 5
Aplicaciones Compresion de imagenes
>>[U,S,V] =svd(A)
Aplicaciones Compresion de imagenes
>> svdimage(A,U,S,V,1,gray); Vemos a A como una imagen utilizando un mapa de colores definido como gray donde cada numero se correspondera con un color. El 1 marca el comienzo utilizando la primera iteracin.
Aplicaciones Compresion de imagenes
Original
1 iteracin
Aplicaciones Compresion de imagenes
Original
1 iteracin
2 iteraciones
3 iteraciones
4 iteraciones
5 iteraciones
Aplicaciones Compresion de imagenes
Una imagen a color es una matriz de (n,m,y) nmeros, a cada pxel se le asigna un vector en R3, el vector representa la composicin RGB del color Por ej. el vector (0,0,1) representa el color azul. El pxel se ver
Escala de grises valores entre [0,63]
Aplicaciones Compresion de imagenes
function Msvd(imagen, k1, k2, k3, k4, k5) close all [A,map]=imread(imagen); B=im2double(A,'indexed'); figure; imshow(B,map) title('ORIGINAL'); %pause(); [u,s,v]=svd(B); iter=[k1,k2,k3,k4,k5]; C=zeros(size(B)); for t=1:5 k=iter(t) C=zeros(size(B)); for j=1:k C=C+s(j,j)*u(:,j)*v(:,j).'; end %C=floor(C); figure; imshow(C,map) title('ITERACION'); %pause();
end
Aplicaciones Compresion de imagenes
Original
5 iteraciones
10 iteraciones
20 iteraciones
60 iteraciones
100 iteraciones
Aplicaciones Compresion de imagenes
5 iteraciones 99.9% ahorro
60 iteraciones 84% ahorro
100 iteraciones 55% ahorro
Aplicaciones Compresion de imagenes
Una imagen de 480 x 640 pixels requiere almacenar 921600 elementos Esto es, aproximadamente, 0.9 Mbytes. Para almacenar Ak se necesita n x k para U, k x m VT, k para S
=> En total, (n + m+ 1 ) x k
Aplicaciones Compresion de imagenes
la relacin de compresin es
r = k * (n+m+1) / nm
Para la misma imagen n=480, m=640 Tenemos con k = 50 que la imagen comprimida slo requiere un 18% de la informacin original 50* (480+640+ 1) / (480*640) = 0.18
Aplicaciones Compresion de imagenes
Una imagen contiene informacin redundante, o sea, que puede ser eliminada sin que el efecto visual sea notable. La SVD nos sirve para descomponer la matriz de imagen y luego comprimir la informacin utilizando solo algunos valores singulares dependiendo de la calidad que deseamos obtener. Mientras mayor sea k mejor ser la calidad de imagen pero menor la compresin, y viceversa.