Decomposição Espectral e Valores Singulares

Prévia do material em texto

Decomposição espectral 
Marcos Augusto dos Santos 
marcos@dcc.ufmg.br 
Autovalores e Autovetores 
• Autovetores (para uma matriz S de ordem m) 
 
 
 
Só tem solução não trivial se 
 
 
autovalor autovetor 
Exemplo: 
 
Sec. 18.1 
Multiplicação matriz vetor 

S 
30 0 0
0 20 0
0 0 1










Tem autovalores 30, 20, 1 com 
os autovetores correspondentes: 











0
0
1
1v











0
1
0
2v











1
0
0
3v
Qualquer vetor (por exemplo, x= ) pode ser visto como uma combinação linear de 
autovetores: x = 2v1 + 4v2 + 6v3 










6
4
2
Sec. 18.1 
Multiplicação matrix vector 
• A multiplicação matriz-vetor, tal como Sx, 
pode ser reescrita em função de autovalores e 
autovetores: 
 
 
 
 
 
 

Sx  S(2v1  4v2  6v 3)
Sx  2Sv1  4Sv2  6Sv3 21v1  42v2  63v 3
Sx  60v1  80v2  6v 3
Sec. 18.1 
Autovalores & Autovetores 
0' e , 2121  vvvSv 
Para matrizes simétricas, autovetores para autovalores 
distintos são ortogonais 
Todos autovetores de uma matriz simétrica real são reais. 
 
 
0vSv se então ,0,  Swww Tn
Todos autovalores de uma matriz semidefinida positiva 
são positivos 
Sec. 18.1 
Polinômio característico 
Exemplo 
• Seja 
 
 
• Então 
 
Os autovalores são 1 and 3 (positivos). 
• Os autovetores são ortogonais : 







21
12
S
.01)2(||
21
12
2 













IS
IS






1
1






1
1
Real, simétrica. 
Sec. 18.1 
 
 Seja uma matriz quadrada com m 
autovetores distintos (matriz com posto completo) 
 Teorema: Existe uma decomposição espectral 
 
 
 As colunas de U são os autovetores de S 
 Os elementos de são os autovalores de 
 Decomposição espectral 
diagonal 
Sec. 18.1 
Decomposição espectral 










 nvvU ...1
U tem os autovetores como colunas: 











































n
nnnn vvvvvvSSU


 ............
1
1111
Então, SU pode ser escrita como 
 S=UU–1. 
Portanto, SU=U, ou 
Sec. 18.1 
Decomposição espectral - exemplo 
Seja 
.3,1;
21
12
21 





 S
 Os autovetores e formam: 






1
1






1
1 







11
11
U
Invertendo, temos 





 

2/12/1
2/12/1
1U
Então, S = UU–1 = 





 












 2/12/1
2/12/1
30
01
11
11
Relembre que 
UU–1 =I. 
Sec. 18.1 
Exemplo 
Divida U (e multique U–1) por 
2





 












 2/12/1
2/12/1
30
01
2/12/1
2/12/1
Então, S = 
Q (Q-1= QT )  
Sec. 18.1 
• Se é uma matriz simétrica: 
• Teorema: Existe uma (única) decomposição 
espectral 
• onde Q é ortogonal: 
– Q-1= QT 
– As colunas de Q são os autovetores normalizados 
 
 Decomposição espectral 
TQQS 
Sec. 18.1 
Para casa 
• Examine a decomposição espectral (se 
existente) de cada uma das seguintes 
matrizes: 
,
01
10







,
01
10






,
32
21






 




42
22
Sec. 18.1 
Decomposição por valores 
singulares 
TVUA 
mm mn V é nn 
Para uma matrix A m  n, de posto r, existe uma 
fatorização (decomposição por valores singulares = dvs) 
dada por: 
 
As colunas de U são os autovetores de AAT. 
As colunas de V são os autovetores de ATA. 
ii  
 rdiag  ...1
Valores singulares 
Os autovalores 1 … r de AA
T são autovalores de ATA. 
Sec. 18.2 
Decomposição por valores 
singulares 
• dimensões e esparsidade 
 
 
Sec. 18.2 
Exemplo de DVS 
Seja 









 

11
10
11
A
Sec. 18.2 
 DVS pode ser usada para computar aproximações 
ótimas da matriz fornecida. 
 Problema: Encontre Ak de posto k tal que 
 
 
 
 
Ak e X são matrizes mn. 
 
 
Aproximações de posto 
 norma de Frobenius 
F
kXpostoX
k XAA 

min
)(:
Sec. 18.3 
Erro na aproximação de posto 
 Quão boa é a aproximação? 
 É a melhor possível, medida pela norma de 
Frobenius : 
 
 
 
 
1
)(:
min 

 kFkF
kXpostoX
AAXA 
Sec. 18.3 
Utilização da redução de posto 
 Matrizes de termos-documentos podem ter 
m=50000, n=10 milhões (e posto próximo de 50000) 
 Pode-se construir uma aproximação A100 com posto 
100. 
 De todas as matrizes de posto 100, a aproximação de 
menor erro (norma de Frobenius) é dada pela DVS . 
 
C. Eckart, G. Young, The approximation of a matrix by another of lower rank. 
Psychometrika, 1, 211-218, 1936. 
Sec. 18.3 
Mineração de dados 
 Dada uma matriz A de termos-docs, 
compute a aproximação Ak. 
 Tem-se uma linha para cada termo e uma 
coluna para cada doc em Ak 
 Os docs estão em um espaço de dimensão 
k<<r. 
Sec. 18.4 
Para casa 
• Os alunos presentes ao final desta aula, 
poderão entregar, impreterivelmente , junto 
com a prova, o exercício distribuído. 
 
 
• Bônus: até 03 pontos a serem somados à nota 
auferida na prova. 
Sec. 18.1