Tarea 3

Parte a)

Genere  matrices densas de distintos tamaños con valores propios conocidos. Luego obtenga los valores y vectores propios mediante el método QR y evalúe la velocidad de convergencia, el tiempo total, la precisión alcanzada, el uso de memoria, etc., con las mejoras incrementales:

a1) Iterando directamente sobre la matriz

a2) convirtiendo la matriz a forma de Hessenberg antes de la iteración QR

a3) desplazando la matriz usando un valor cualquiera de la diagonal

a4) desplazando la matriz usando el valor de la esquina inferior derecha (último elemento de la diagonal).

Explique los resultados de cada parte.

Parte b)

Obtenga los 10 valores propios de mayor magnitud de las matrices de la colección SuiteSparse (https://sparse.tamu.edu/) usadas para la Tarea 2 mediante el método más conveniente. Compare la precisión y el tiempo de ejecución del método elegido con la función eigs o una función de biblioteca similar en el lenguaje de programación que elija. 

Parte c)

Esta parte consiste en utilizar la SVD para clasificar imágenes de dígitos.

Descargue el dataset del eva. El dataset está separado en dos estructuras “train” y “test”. Cada una de estas contiene una matriz “data” que en cada columna tiene una imagen de 16x16 de un dígito expresada como un vector de 256 elementos, y “target”, que es un vector con el dígito que pertenece a cada columna de data.

El procedimiento para clasificar las imágenes es el siguiente:

1. Separar las columnas de train.data en 10 matrices D_i que contengan, respectivamente, las imágenes correspondientes a un único dígito.

2. Para clasificar cada dígito del conjunto test, la idea es comprobar con cuál de las 10 matrices podemos obtener una combinación lineal más cercana a la columna correspondiente de test.data. Para eso se debe resolver el problema de mínimos cuadrados min_y|| x - D_iy ||, donde x es la columna de test.data que se quiere clasificar y D_i es la matriz correspondiente al dígito i. Una vez obtenida la aproximación usando cada D_i, resta obtener el mínimo para saber cuál de las matrices D_i se obtuvo una mejor aproximación a x.
   

c1) Realice la clasificación de las imágenes pertenecientes al conjunto test mediante el procedimiento anterior resolviendo el problema de mínimos cuadrados usando las ecuaciones normales: y = (Di^TDi)^-1 Di^Tx

c2) Realice la clasificación de las imágenes pertenecientes al conjunto test mediante el procedimiento anterior resolviendo el problema de mínimos cuadrados usando la SVD. Recuerde que si A=USV^T , U es una base del subespacio de las columnas de A. Compare la precisión y el costo computacional respecto al método anterior.

c3) Estudie el uso de memoria, costo computacional del método y la precisión obtenida para las clasificaciones variando la cantidad de vectores singulares involucrados en la parte c2.