13.4 SVD como aproximación

Image Compression

Introducción

Una matriz de tamaño m × n es una cuadrícula de números reales que consta de m filas yn columnas. En álgebra lineal, una rama de las matemáticas, las matrices de tamaño m × n describen mapeos lineales desde el espacio n-dimensional al m-dimensional. La palabra lineal significa aproximadamente que las líneas rectas se asignan a las líneas rectas y el origen en el espacio de n dimensiones se asigna al origen en el espacio de m dimensiones. Cuando tenemos una matriz A (m × n) y una matriz B (n × k), podemos calcular el producto AB, que es una matriz (m × k). El mapeo correspondiente a AB es exactamente la com La descomposición de valores singulares (SVD) establece que cada (m × n) -matriz A se puede escribir como un producto donde U y V son matrices ortogonales y la matriz Σ consiste en valores no negativos descendentes en su diagonal y ceros en el resto. Las entradas σ1 ≥ σ2 ≥ σ3 ≥… ≥ 0 en la diagonal de Σ se denominan valores singulares (SV) de A. Geométricamente, Σ asigna el j-ésimo vector de coordenadas unitarias del espacio n-dimensional al j-ésimo vector de coordenadas del espacio m-dimensional, escalado por el factor σj. La ortogonalidad de U y V significa que corresponden a rotaciones (posiblemente seguidas de una reflexión) del espacio m-dimensional y n-dimensional respectivamente. Por lo tanto, solo Σ cambia la longitud de los vectores.

Usando SVD para la compresión de imágenes

Podemos descomponer una imagen dada en los tres canales de color rojo, verde y azul. Cada canal se puede representar como una matriz (m × n) con valores que van de 0 a 255. Ahora comprimiremos la matriz A que representa uno de los canales. Para hacer esto, calculamos una aproximación a la matriz A que toma solo una fracción del espacio para almacenar. Ahora bien, esto es lo mejor de la SVD: los datos en las matrices U, Σ y V se ordenan según cuánto contribuyen a la matriz A en el producto. Eso nos permite obtener una aproximación bastante buena simplemente usando solo las partes más importantes de las matrices. Ahora elegimos un número k de valores singulares que usaremos para la aproximación. Cuanto mayor sea este número, mejor será la calidad de la aproximación, pero también se necesitarán más datos para codificarla. Ahora tomamos solo las primeras k columnas de U y V y el cuadrado superior izquierdo (k × k) de Σ, que contiene los k valores singulares más grandes (y por lo tanto más importantes). Entonces tenemos La cantidad de datos necesarios para almacenar esta aproximación es proporcional al área coloreada: tamaño comprimido = m × k + k + k × n = k × (1 + m + n) (En realidad, se necesita un poco menos de espacio debido a la ortogonalidad de U y V.) Se puede probar que esta aproximación es óptima en cierto sentido
1. Completando Matrices Completas

Un demo en Internet

El siguiente demo le permite elegir el número de valores singulares k y ver cómo esta elección afecta la calidad de la aproximación y la tasa de compresión. Observe cómo para todas las fotografías, el gráfico que muestra los valores singulares parece una hipérbola: solo hay unos pocos SV realmente grandes y una larga cola de SV relativamente más pequeños. En contraste, para la imagen de ruido aleatorio, el gráfico de SV parece aproximadamente lineal. La SVD se utiliza habitualmente en estadísticas para el análisis de componentes principales y en simulaciones numéricas para reducir el orden de los modelos. Para la compresión de imágenes, los métodos más sofisticados como JPG que tienen en cuenta la percepción humana generalmente superan a la compresión con SVD.

Explicador Sin Centroide

Explicador con Centroide