Navegación

Contenidos

Tema anterior

Clase 7: Valores y vectores propios

Próximo tema

Clase 9: Más de SVD

Esta página

Clase 8: SVD

Bibliografía de la Clase:

  • Numerical Linear Algebra.L.N. Trefethen. Chapter 1: Lecture 4 The Singular Value Decomposition
  • Introduction to Linear Algebra. Gilbert Strang. Chapter 6 Eigenvalues and Eigenvectors
  • Guía profesor Luis Salinas

Visualización de valores y vectores singulares

En la siguiente figura se muestra el efecto de multiplicar la matriz A por los vectores unitarios (círculo verde). En particular A=\begin{bmatrix}1.4015 & -1.0480 \\ -0.4009 & 1.0133 \end{bmatrix}.

SVD de `A=\begin{bmatrix}1.4015 & -1.0480 \\ -0.4009 & 1.0133 \end{bmatrix}`

Hay ciertos vectores v_i que el efecto de ser multiplicados por A resultan ser los semiejes de la elipse de la figura. Tanto los vectores v_i y u_i son unitarios y los coeficientes \sigma_i corresponden a los largos de los semiejes. Por lo tanto, podemos resumir la imagen en las siguientes ecuaciones:

A v_i = \sigma_i u_i, \quad 1\leq i \leq n

SVD reducida

Si la matriz A \in Mat(m,n) y n \leq m entonces se encontrarán a lo más n valores de \sigma_i \neq 0 y por lo tanto la ecuación anterior sigue siendo válida aún si A no es cuadrada. La representación matricial correspondiente sería:

\begin{bmatrix} \quad & \quad & \quad\\ \quad & \quad & \quad\\ \quad & A & \quad \\ \quad & \quad & \quad \\ \quad & \quad & \quad \end{bmatrix} \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ v_1 & v_2 & \cdots & v_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right]= \left[ \begin{array}{c|c|c|c} \, & \, & \, & \, \\ \, & \, & \, & \, \\ u_1 & u_2 & \cdots & u_n \\ \, & \, & \, & \, \\ \, & \, & \, & \, \end{array} \right] \begin{bmatrix} \sigma_1 & \, & \, & \, \\ \, & \sigma_2 & \, & \, \\ \, & \, & \ddots & \, \\ \, & \, & \, & \sigma_n \end{bmatrix}

De manera más resumida la expresión anterior se puede escribir como:

AV=\hat{U}\hat{\Sigma}

A esta factorización se denomina SVD reducida. Donde \hat{U} \in Mat(m,n) es una matriz con n columnas ortonormales y \hat{\Sigma} \in Mat(n,n) es una matriz diagonal donde \sigma_1 \geq \sigma_2 \geq \dots \sigma_n. Dado que V es una matriz unitaria (i.e VV*=I) podemos reescribir la expresión anterior como:

A=\hat{U}\hat{\Sigma}V^*

Bajo esta representación, los vectores de la matriz U se les denomina los vectores singulares izquierdos de A y a los vectores de V los vectores singulares derechos de A.

Gráficamente la factorización SVD reducida se visualiza como sigue:

SVD reducida

SVD completa (Full SVD)

La versión completa de la SVD se obtiene extendiendo la matriz \hat{U} a una matriz unitaria U. Gráficamente la factorización SVD completa:

SVD completa

Al aumentar las columnas de U, también debemos extender \hat{\Sigma} obteniendo la matriz \Sigma. Para obtener U se agregaron m-n columnas ortonormales (si A es full rank) o m-r (si r es el rango de la matriz A). En el caso de que A no es full rank, deben también agregarse n-r columnas a V.

Cálculo de la SVD

Las matrices U, V y \Sigma pueden ser obtenidas mediante el siguiente procedimiento:

A^*A=(U \Sigma V^*)^*(U \Sigma V^*)=V \Sigma^* U^* U \Sigma V^* = V(\Sigma^* \Sigma) V^*

Donde \Sigma^* \Sigma corresponde a la matriz diagonal:

\begin{bmatrix} \sigma_1^2 & \, & \, & \, \\ \, & \sigma_2^2 & \, & \, \\ \, & \, & \ddots & \, \\ \, & \, & \, & \sigma_n^2 \end{bmatrix}

Es decir, los vectores propios de A^*A son los vectores singulares derechos de A,i.e {v_1,v_2,..,v_n} y los valores propios de A^*A corresponden a los cuadrados de los valores singulares (\sigma_i) de A.

Una vez obtenidas las matrices V y \Sigma el cálculo de U es directo.

Ejercicio

Encontrar la descomposición SVD de la siguiente matriz:

A=\begin{bmatrix} 3 & 2 \\ -1 & 2 \\ 2 & 0 \end{bmatrix}

  1. Determine los valores singulares de A y su matriz \Sigma.
  2. Determine los vectores singulares derechos de A.
  3. Determine los vectorres singulares izquierdos de A.
  4. Verificar que la SVD obtenida es correcta.

Ejercicio propuesto

Considerando la proyección de vectores vistas en la clase 4. Es posible obtener un vector ortogonal a un conjunto de vectores ortonormales q_i \; \forall i=1:n como:

r = v - \sum_{i=1}^n (q_i^*v)q_i = v - \sum_{i=1}^n q_i(q_i^*v) = v - \sum_{i=1}^n (q_i q_i^*)*v

Este procedimiento (conocido como ortogonalización de Gram-Schmidt) puede ser usado para agregar vectores ortonormales a la matriz \hat{U} para que encontrar la matriz unitaria U.

Utilizando esta información, obtenga la descomposición SVD completa de A.

Navegación

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