Navegación

Contenidos

Tema anterior

Clase 8: SVD

Próximo tema

Clase 10: Factorización QR

Esta página

Clase 9: Más de SVD

Bibliografía de la Clase:

  • Numerical Linear Algebra.L.N. Trefethen. Chapter 1: Lecture 5 More on the SVD
  • Introduction to Linear Algebra. Gilbert Strang. Chapter 6 Eigenvalues and Eigenvectors
  • Guía profesor Luis Salinas

Visualización de la SVD

Cuando resolvemos el sistema Ax=y el efecto que produce A sobre el vector x puede explicarse usando la descomposición SVD Ax=U \Sigma V^* x. La siguiente figura explica gráficamente lo que sucede:

caption

Normas de A

Teorema

||A||_2=\sigma_1 y ||A||_F=\sqrt{\sigma_1^2 + \sigma_2^2 + \dots + \sigma_r^2}

Demostración

Las dos demostraciones se basan en que tanto la norma 2 como la de Frobenius son invariantes ante la multiplicación de matrices unitarias.

  1. ||A||_2=||U \Sigma V^*||_2=||\Sigma||_2 = max_{1\leq i \leq m} |d_i| = \sigma_1
  2. ||A||_F = ||U \Sigma V^*||_F=||\Sigma||_F = \sqrt{\sigma_1^2 + \sigma_2^2 + \dots + \sigma_r^2}

Bases de los espacios vectoriales de A

  1. \text{Row}(A)=<v_1 , \dots ,v_r > donde v_i \in \mathbb{R}^n \quad \forall i=1:r
  2. \text{Col}(A)=<u_1 , \dots ,u_r > donde u_i \in \mathbb{R}^m \quad \forall i=1:r
  3. \text{Null}(A)=<v_{r+1}, \dots ,v_n > donde v_i \in \mathbb{R}^n \quad \forall i=r+1:n
  4. \text{Null}(A^*)=<u_{r+1}, \dots ,u_m > donde u_i \in \mathbb{R}^m \quad \forall i=r+1:m

Lo anterior se resume en la siguiente imagen:

Subspaces

Ejercicio

  1. Demostrar que \text{Col}(A)=<u_1 , \dots ,u_r >.
  2. Demostrar que \text{Null}(A^*)=<u_{r+1}, \dots ,u_m >.

Ejercicio propuesto

  1. Demostrar que \text{Row}(A)=<v_1 , \dots ,v_r >.
  2. Demostrar que \text{Null}(A)=<v_{r+1}, \dots ,v_n >.

Descomposición de valores propios v/s Descomposición de valores singulares

La descomposición de valores propios la expresamos matricialmente como:

AX=X \Lambda.

Por otro lado, la descomposición de valores singulares (SVD) se expresa como:

AV= U \Sigma.

Las principales diferencias entre ambas descomposiciones son:

  1. La descomposición de valores propios sólo puede determinarse para matrices no singulares, en cambio toda matriz A tiene una SVD.
  2. Los vectores base de la SVD (u_i y v_i) son ortonormales, los vectores x_i no son necesariamente ortogonales.
  3. La descomposición de valores propios utiliza el mismo set de bases (los vectores propios), mientras que la SVD utiliza los vectores singulares izquierdos y derechos como base.

Nota

Los vectores x_i de una matriz simétrica son ortogonales.

Compresión de imágenes

La compresión de imágenes es una importante aplicación en álgebra lineal debido a la necesidad de minimizar la cantidad de información almacenada y transmitida. SVD es una técnica que permite minimizar el espacio requerido para almacenar una imagen conservando la calidad de ella.

Si tenemos una imagen de mxn pixeles la podemos representar matricialmente con su respectiva SVD:

A=U \Sigma V^*

Equivalentemente podemos expresar la imagen representada en A como:

A=\sum_{i=1}^n \sigma_i u_i v_i^*

Debido a que \sigma_1 \geq \sigma_2 \dots \sigma_n los términos de mayor impacto son los primeros términos de la expresión anterior.

Por lo tanto, es posible aproximar la imagen A usando sólo los primeros k términos de la serie.

Almacenamiento

Inicialmente la memoria requerida para almacenar una imagen era m \times n. Usando la SVD sólo se requiere de k(m+n+1), es decir, el crecimiento es lineal.

Para asegurar que la memoria usada no supere la original debe cumplirse:

k(m+n+1) < m n \\ k < \frac{mn}{m+n+1}

Un ejemplo de esta compresión se muestra en el siguiente código en Matlab:

Navegación

© Copyright 2012, CTI-HPC. Creado con Sphinx 1.1.3.