Algebra De Compresión

Álgebra de compresión

A= USV

T

σ1 ≥ σ2 ≥ ...
A =Σ σi ui vi
T

UADE / M. Martins – F. Acero / 2004

imagen color
Una matriz de n x m x 3 números
• A cada pixel se le asigna un vector de R3 • El vector indica la composición RGB (redgreen-blue). • Por ejemplo, un pixel marcado con el vector (1, 0, 0) se verá así:

imagen blanco y negro
Es una matriz de n x m números
• A cadapixel se le asigna un número • El número sólo puede ser 0 o 1 • Por ejemplo, un pixel marcado con el número 1 se verá así:

imagen blanco y negro

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

0 0 1 1⎞ ⎟ 1 1 0 1⎟ 1 0 1 1 0 ⎟ ⎟ 0 1 0 0 0⎟ 0 0 1 1 0⎟ ⎠ 0 0

imagen en tonos de gris
Es una matriz de n x m números
• A cada pixel se le asigna un número • El número es un natural entre 0 y 63 • Por ejemplo, un pixelmarcado con el número 30 se verá así:

imagen en tonos de gris

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

44 50 62 34 60 17 28 33 16 44 55 55 39 11 46

9 42 ⎞ ⎟ 1 18 ⎟ 56 30 ⎟ ⎟ 13 4 ⎟ 19 62 ⎟ ⎠

Un poco de álgebra lineal
Descomponer una matriz es escribirla como el producto de otras. Algunas descomposiciones famosas son la LU, LDU, la QR, la diagonalización A = LU A=LDU A=P D P-1 A = QR

lu, ldu, qr, pdp-1
LUy LDU se aplican intensivamente en la resolución de sistemas lineales. QR toda vez sea necesario mantener controlado el número de condición. PDP-1 y su descomposición espectral para desacoplar problemas (p.ej. EDOs)

limitación de

T pdp

A = PDP-1 puede reescribirse PDPT sii A es simétrica … y en tal caso los autovalores de D son reales (positivos, nulos o negativos) ¿puede hacerse algosimilar con una matriz A rectangular cualquiera?

la descomposición svd
La respuesta es sí, la descomposición svd, ¡¡¡ válida para TODA matriz A !!!

A= U S V

T

Siendo U, V ortogonales y S con elementos no negativos en la diagonal, nulos fuera de ella.

la matriz S de n x r

σ1 0 0 ... 0 0 σ2 0 ... 0 0 0 σ3 ... σ1 ≥ σ2 ≥ ... ≥ σr >0
r es el rango de A

la descomposición U S VTT ⎡σ1 0 0 0 ⎤⎧ v1 ⎢ 0 σ 0 0 ⎥⎪ T ⎪ v2 2 ⎥⎨ A = {u1 | u2 | K| ur }⎢ ⎢ 0 0 O 0 ⎥⎪ M ⎢ ⎥⎪ vT ⎣ 0 0 0 σ r ⎦⎩ r

⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭

σ1 ≥ σ2 ≥ ... ≥ σr >0

la suma U S VT
A1

A = σ1 u1 v1T

+ …
Ar

+ ... + σr ur vrT

A=US

T V

A=

T σ1 u1 v1

+ σ2 u2 v2

T

+ ... + σr ur vrT
... y como Ai = σi ui viT es ...

A = A1 + A2 +... Ar

σ1

un ejemplo

σ2

⎡ 2 0 ⎤ ⎡ 0 1 0⎤⎡3 0 ⎤ ⎢0 − 3⎥ = ⎢− 1 0 0⎥ ⋅ ⎢0 2⎥ ⋅ ⎡0 1⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1 0⎥ ⎣ ⎦ ⎢ ⎣ 0 0 ⎥ ⎢ 0 0 1 ⎥ ⎢0 0 ⎥ ⎦ ⎣ ⎦ ⎣ ⎦

A

=

U

S

VT

A = σ 1 u 1 v1 T + σ 2 u 2 v2 T
⎡2 0 ⎤ ⎡0⎤ ⎡1⎤ ⎢0 − 3⎥ = 3 ⎢− 1⎥ [0 1]+ 2 ⎢0⎥ [1 0] ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢0⎥ ⎢0 ⎥ ⎣0 0 ⎥ ⎦ ⎣ ⎦ ⎣ ⎦
A σ1 u1 v1T σ2 u2 v2T

A = A1 + A2
⎡2 0 ⎤ ⎢0 − 3⎥ = ⎢ ⎥ ⎢0 0 ⎥ ⎣ ⎦
A

⎡0 0 ⎤ ⎡ 2 0 ⎤ ⎢0 − 3⎥ + ⎢0 0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎣0 0 ⎥ ⎢ 0 0 ⎥ ⎦ ⎣ ⎦A1 A2

rg (A) = 2 ; rg(A1) = rg(A2) = 1

la aproximación Ak*

Ak* = A1 + A2 +... Ak
y el error al aproximar A por Ak* está dado por ê =║A - Ak* ║, y es el mínimo de todos los que se obtienen aproximando A por una matriz de rango k

la mejor aproximación
luego, en el sentido de los mínimos cuadrados Ak* es la mejor aproximación para un dado k

A

Ê = ⎢⎢A-A k*⎢⎢

Ak* Sk = gen { A1 ,A2 , ..., Ak }

el ejemplo
A=

⎛2 0 ⎞ ⎟ ⎜ ⎜ 0 − 3⎟ ⎜0 0 ⎟ ⎠ ⎝

A1*=

⎛0 0 ⎞ ⎜ ⎟ ⎜ 0 − 3⎟ ⎜0 0 ⎟ ⎝ ⎠

el error
A
Ê=2

A1*

en imágenes
A=

A5*=

error-imagen
La matriz de error E = A – Ak* tiene una imagen que es : Completamente negra si A =Ak*, pues en tal caso es E = 0 El error-imagen es tanto más negro cuanto mejor la aproximación

el error-imagen
A
Ê=

A5*las matrices
3 6 4 5 7 6 4 3 5 33 25

7 5 4 4 6 6 4 3 4 21 15
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

4 4 4 4 5 5 4 3 3 34 26

1 3 4 4 4 4 4 3 2 32 24

4 3 5 5 4 4 4 4 2 35 29

3 3 5 6 4 4 5 4 2 27 25

8 3 6 6 4 4 5 5 2 19 21

9 17 6 4 2 3 5 6 6 7 9 9 10 10 10 11 9 9 9 8 9 8 8 7 9 9 8 8 8 8 8 7 5 6 6 6 19 18 22 25 21 20 23 24

47 47 47 47 47 48 48 48 48 48 48 ⎞ ⎟ 46 47 47 48 48...