[e115cc]: DIFF.tex Maximize Restore History

Download this file

DIFF.tex    1665 lines (1456 with data), 110.8 kB

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
%Esta técnica tem se tornado bastante útil para redução de dimensionalidade e clustering no caso não linear.
%A ideia chave é reorganizar os dados de acordo com sua geometria. O desafio é determinar uma estrutura de baixa dimensão que contenha os dados para que tenhamos uma parametrização significativa.
%A redução de dimensionalidade pode ser usada para melhorar uma clusterização dos dados.
\chapter{Aplicações de difusão}\label{ap_dif}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Decidir se vou ficar chamando a distância de difusão de pseudo-métrica. Eu falo aqui neste primeiro parágrafo novamente.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A aplicação ou mapa de difusão é uma das mais recentes técnicas de redução de dimensionalidade não-linear
que pode ser útil dentre outras tarefas para encontrar padrões em um conjunto de dados, agrupando-os em subconjuntos ou {\em clusters} para classificação\cite{Socher2008}.
A reorganização dos dados de acordo com sua geometria intrínseca permite determinar uma estrutura de baixa dimensão que contenha
os mesmos para que tenhamos uma parametrização significativa. Geometria intrínseca neste contexto é modelada através da conectividade entre
os dados num processo de difusão ~\cite{lafon2006diffusion}.
A aplicação de difusão define uma pseudo métrica que permite criar este processo de difusão dependente do tempo, esta cadeia de Markov.
Tudo é possível de ser feito através da teoria espectral dos grafos.
Procederemos agora a uma descrição crítica, minuciosa e inédita do processo todo finalizando com experimentos.
Na pr\'oxima se\cao\ apresentamos alguns aspectos da
nota\c{c}\~ao e na se\cao\ seguinte discutimos um pouco mais sobre a matriz dos pesos das arestas.
Na seção \ref{secmarkov} descreveremos detalhadamente a cadeia de Markov. A no\cao\
de dist\^ancia de difus\~ao \'e apresentada na se\cao\ \ref{difdis2} enquanto que na se\cao\ \ref{markovaut} s\~ao discutidas propriedades
espectrais da matriz de Markov, que ser\~ao \'uteis para a apresenta\cao\ da aplica\cao\ de difus\~ao na se\cao\ seguinte.
Finalizamos com uma se\cao\ de experimentos
na qual, em particular, comparamos o PCA, o m\'etodo das autofun\coes\ do laplaciano e a aplica\cao\ de difus\~ao.
\section{Considerações iniciais}
Resumindo, o nosso objetivo é mostrar como construir uma fun\cao\ chamada de aplicação de difusão, $\diff,$ sobre um conjunto de dados $E=\{X^1, X^2\dots, X^n\},$
$X^i \in \re^d,$ tomando valores em $\re^{n-1}$ (como ficar\'a claro mais adiante) e preservando determinadas propriedades.
Para tal será utilizada a matriz de afinidades $W$.
%
Quando os dados est\~ao descritos em $\re^d$, e $W$ \'e obtido
atrav\'es de uma fun\cao\ núcleo $K$, definida em $\re^d\times \re^d$
h\'a vantagens pois as afinidades podem ser calculadas mesmo para vetores que n\~ao estejam no conjunto
de treinamento (ou de sinais de entrada).
\begin{comment}
Para a aplicação %mais efetiva(?facilitada??)
do método é interessante considerarmos a hipótese da simetria da matriz \emph{W}, ou seja, $w_{ij}= w_{ji};$ a positividade dos seus elementos, ou seja, $(w_{ij} \geq 0),$ e melhor ainda se \emph{ W}
for positiva semidefinida $z^\top Wz \geq 0,\forall z,$ ~\cite{lafon2004diffusion} (neste caso os autovalores da matriz de Markov que consideraremos estarão entre 0 e 1).
\end{comment}
A partir da matriz de afinidades (pesos) \emph{W} construimos um processo de Markov que define uma `dist\^ancia' de difus\~ao,
a qual \'e an\'aloga a uma dist\^ancia geod\'esica, porém
mais robusta e definida no grafo.
Na seção~\ref{escova} discutiremos especificamente sobre a escolha desta matriz
(veja tamb\'em as se\coes~\ref{1consini} e \ref{vizLE}
no capítulo das autofunções do laplaciano).
%
Com a análise espectral da matriz de transição correspondente será possível calcular eficientemente a aplicação de difusão desejada e,
a partir dela, as `dist\^ancias' de difus\~ao. \'E precisamente esse ponto de vista que diferencia as aplica\coes\ de difus\~ao do m\'etodo das
autofun\coes\ do Laplaciano.
Para casos onde os dados de entrada são constituídos de
uma quantidade muito grande de medi\coes, ou seja, casos onde \emph{d} é muito grande,
%Nestas aplicações,
em geral, \emph{n} é muito menor do que \emph{d}. Este fato em si já possibilita uma redução de dimensionalidade de
$\re^d$ para $\re^{n-1}$. No entanto, para a escolha de grandes valores do parâmetro tempo no processo de Markov, é
comum utilizarmos apenas duas ou três componentes das imagens, reduzindo ainda mais a dimensão e, assim,
poderíamos proceder a um “data mining”
permitindo inclusive uma visualização das mesmas. \'E claro que isto s\'o \'e poss\'{\i}vel quando o conjunto de sinais, apesar de estar em $\re^d$, se apresentar
``parametriz\'avel''
por dois ou tr\^es par\^ametros.
% algum subespaço euclidiano de dimensão reduzida (muito menor que \emph{p}).\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Uma escolha para matriz peso das arestas}\label{escova}
Como já foi dito anteriormente, a posição $w_{ij}$ da matriz peso das arestas, $W,$ representa a afinidade entre dois elementos do conjunto original de dados, $X^i$ e $X^j.$
Para a aplicação %mais efetiva(?facilitada??)
do método é interessante, como explicado a seguir, considerarmos a hipótese da simetria da matriz \emph{W}, ou seja, $w_{ij}= w_{ji}$ (grafo n\~ao-direcionado);
a positividade dos seus elementos, ou seja, $(w_{ij} \geq 0),$ e melhor ainda se \emph{W} for positiva semidefinida $z^\top Wz \geq 0$, para todo
o $z$ ~\cite{lafon2004diffusion} (neste caso os autovalores da matriz de Markov adiante estarão entre 0 e 1).
%\todo{Como provar que o W a seguir é p.s.d.? Dai posso usar só autovalores entre 0 e 1. VER: Mercer kernels (positivo definido , a matriz de gram é positiva definida). Prova-se que o núcleo gaussiano é um núcleo de mercer (Schoelkopf e Smola 2002)//}
É uma boa ideia então expressar essa conectividade em termos do núcleo de difusão ou gaussiano, $K.$ Este núcleo é definido como
$ K(X^i,X^j)= exp(-\frac{\|X^i-X^j\|^2}{\varepsilon}),$ onde o parâmetro $\varepsilon$ é uma constante que deve ser escolhida de acordo com o problema, $\sqrt{\varepsilon}$ pode ser entendido como o tamanho da vizinhança e é baseado no conhecimento da estrutura e densidade dos dados.
Este núcleo representa alguma noção de afinidade ou similaridade entre os pontos $X^i$ e $X^j$ dentro de uma certa vizinhança
e portanto constitui uma primeira definição da geometria local do conjunto de dados.
Em nosso trabalho o parâmetro $\varepsilon$ foi escolhido em função do {\em di\^ametro} do conjunto de sinais (i.e. da maior distância euclidiana entre os dados de entrada).
Ver se\cao~\ref{vizLE}.
\todo{colocar aqui um ex do gráfico da hélice com peso das arestas para diferentes epsilon}
Coifman e Lafon \cite{coifman2006diffusion} apresentam três normalizações específicas para uma família de aplicações de difusão baseadas no núcleo
\begin{equation}\label{renormal}
(W^{\alpha})_{ij}= \frac{w_{ij}}{d_i^{\alpha}d_j^{\alpha}},
\end{equation}
onde $ d_i^{\alpha}= (\sum_{k=1}^n w_{ik})^{\alpha} $ é o grau do \textit{i}-ésimo vértice do grafo original elevado ao número $\alpha$ e $w_{ij}$ é calculado a partir do núcleo gaussiano. %A ideia deles é formar o processo de Markov para este grafo renormalizado.
%$d_r = (D)_{rr}=\sum _{s=1}^n w_{rs}$ e
Eles destacam como interessantes os valores de $\alpha = 0$ que corresponde ao clássico grafo laplaciano normalizado, $\alpha = 1/2$ ao operador de Fokker-Plank
e $\alpha = 1$ que conduz ao operador de Laplace-Beltrami.
Através deste último parâmetro,
$\alpha = 1,$ podemos ver que os autovetores de uma matriz de Markov que será construída na próxima seção aproximam os autovetores do
operador de Laplace Beltrami, $\Delta,$ sobre uma variedade subjacente $\mathcal{M}.$
Assim, é possível perceber que a aplicação de difusão não depende mais da densidade dos dados originais. Ou seja, este método
separa a geometria da densidade,
consegue capturar a geometria dos dados sem precisar se preocupar com sua densidade \cite{coifman2006diffusion}. Na presente tese utilizamos a normalização indicada na equação (\ref{renormal}). Ainda que não tenha sido necessário mencionar, o parâmetro $\alpha = 0$ foi utilizado implicitamente no capítulo anterior. No presente capítulo tratamos do caso $\alpha=1.$
%\todo{procurar as citações ou tirar a frase}
%Como o núcleo gaussiano é um núcleo de Mercer \cite{} e os núcleos de Mercer são psd \cite{} então seus autovalores são maiores que 0.
% que usaremos na nossa discussão a partir daqui estão entre 0 e 1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\item Considere um conjunto de números não negativos $q=\{q_1,\dots,q_N\}.$ Dado um vetor
$Y\in \re^N$ podemos associar cada um dos pesos $q_i$ a cada componente deste vetor, ou seja, podemos criar o vetor $(q_1 y_1,\dots,q_N y_N).$ Como\emph{W} é positiva semi definida $z^\top Wz \geq 0,\forall z$ em particular para $z=(q_1 y_1,\dots,q_N y_N)$ temos
$$\sum_{i=1}^N y_i q_i \sum_{j=1}^N y_j q_j W_{ij}\geq 0$$ ou ainda
$$\sum_{i=1}^N \sum_{j=1}^N W_{ij} y_i q_i y_j q_j\geq 0,\forall y=(y_1,\dots,y_N).$$
Como $K(X_i,X_j)=W_{ij}$ teremos
$$\int_X \int_X K(X_i,X_j)f(X_i)f(X_j) d\mu (X_i)d\mu (X_j)\geq 0,$$ para qualquer função limitada $f:X\rightarrow \mathbb {R},$ ou seja, \emph{K} pode ser definida como sendo uma função positiva semi definida, onde $\mu$ é uma medida de probabilidade sobre \emph{X}.
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%% FIM DO COMENTÁRIO ACIMA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Cadeias de Markov no grafo dos sinais}\label{secmarkov}
Queremos construir um processo de difusão ou, equivalentemente, no caso discreto de interesse, uma cadeia de Markov sobre o grafo dos sinais.
%Para tal basta normalizar a matriz dos pesos \emph{W}, como segue:\\
%Por isso vamos descrever uma Cadeia de Markov como foi descrita no %excelente
%livro \cite{Grinstead:Snell:20??}.\\
\begin{comment}
Para isso precisamos estudar fenômenos de evolução a tempo discreto de uma maneira genérica.\\ %Cadeia de Markov
\draftnote{trocar a def de Markov.}
Primeiramente consideremos uma população. Cada elemento desta população pode
encontrar-se em cada instante num determinado estado. Este conjunto de possíveis estados é chamado de \emph{espaço de estados}, $E=\{e_1,e_2, \dots, e_n\}.$ Um processo dinâmico começa em um destes estados e move-se sucessivamente para outro estado. Cada um destes movimentos é chamado um \emph{passo}.
A probabilidade de dar um passo do estado $e_i$ para o estado $e_j$ é denotada por $p_{ij}.$
A notação $P[X_{t+1} = e_j | X_t = e_i]$ representa a probabilidade da variável aleatória que representa a população no instante atual,
$X_t,$ sair do estado $e_i$ para chegar no futuro, $X_{t+1},$ ao estado $e_j.$~\cite{ver2009}\\
\begin{defi}\label{defmarkov}
\begin{em}
%Considere um espaço de estados $E=\{e_1,e_2, \dots, e_n\},$ associado a determinado fenômeno de evolução a tempo discreto.
Uma \emph{cadeia de Markov homogênea} com espaço de estados \emph{E}, é, por definição, uma sucessão
$(X_t)_{t\in \mathbb{N}}$ de variáveis aleatórias tais que se verificam as seguintes propriedades:
\begin{itemize}
\item Para quaisquer $e_i, e_j \in E,$ e $t \in \mathbb{N}$ verifica-se que:
$P[X_{t+1} = e_j | X_t = e_i] = p_{ij},$ probabilidade de dar um passo de $e_i$ para $e_j.$ \\
\item Para quaisquer $t \in \mathbb{N}$ e $i_0, i_1, i_2, \ldots , i_{t-1}, i_t, i_{t+1}$ uma sequência de índices obtidos de $E$ vale a condição:
\begin{equation*}
P[X_{t+1} = e_{i_{t+1}} | X_0 = e_{i_0},X_1 = e_{i_1}, \dots , X_{t-1} = e_{i_{t-1}}, X_t = e_{i_t}]= P[X_{t+1} = e_{i_{t+1}} | X_t = e_{i_t}].
\end{equation*}
\end{itemize}
%Se a cadeia atualmente se encontra no estado $e_i,$ então ela se moverá para o estado $e_j$ no próximo passo com uma probabilidade denotada por $p_{ij},$ e o interessante é que esta probabilidade depende apenas da posição atual e não de todas as anteriores. Estas probabilidades são chamadas \emph{probabilidades de transição}. O processo pode permanecer no estado atual com probabilidade $p_{ii}.$
\end{em}
\end{defi}
\noindent \textbf{Observação.} A segunda propriedade é o que caracteriza a falta de memória do sistema, ou seja, a probabilidade de passar do estado $e_{i_t}$ para $e_{i_{t+1}}$ depende apenas da posição atual representada por $X_t$ e não de todas as anteriores
$X_0, X_1, \ldots , X_{t-1}.$
A primeira propriedade na definição anterior é que garante a homogeneidade da cadeia de Markov. O fato da probabilidade não depender do tempo permite representar o tempo atual como $X_0$ e o tempo futuro como $X_1.$
%Uma \emph{cadeia de Markov homogênea de tempo discreto} é uma seqüência
Definição de Cadeia de Markov:\\
A $\{X_k \},k = 0, 1, 2, \dots,$ é chamada uma \emph{cadeia de Markov homogênea de tempo discreto}, com espaço de estados $J = \{0, 1, 2,\dots , n\},$ e matriz de probabilidades de transição, \emph{P} , se para todo $k = 0, 1, 2,\dots $ a condição
$$P(X_k=j| X_{k-1}=i)= P( X_1 = j| X_0 = i)= p_{ij}$$
é satisfeita para todo $(i, j) \in J \times J.$ \cite{www.inf.ufpr.br/ess07/Meus_Programas/PO/livro/05_Markov.pdf}\\
\begin{defi}
\begin{em}
A matriz \emph{P} de ordem $n \times n$ com entradas $p_{ij}= P[X_1=e_j/X_0=e_i]$ é chamada a \emph{ matriz de transição} da cadeia de Markov. Ou seja, esta matriz guarda em cada posição \emph{i,j} a probabilidade do processo sair do estado $e_i$ (estado atual representado pelo índice `zero', $X_0$), e passar para o estado $e_j$ (próximo estado representado pelo índice `um', $X_1).$
\end{em}
\end{defi}
%
\textbf{Observação.} Como cada $p_{ij}$ representa uma probabilidade vemos que todos os elementos da matriz de transição \emph{P} são não negativos.
Além disso a soma dos elementos em cada linha vale um, pois esta soma representa todas as probabilidades de movimento em um passo do estado $e_i$
para qualquer outro estado possível. Uma matriz que atende esta propriedade é chamada \emph{matriz estocástica} ou \emph{matriz de probabilidade}.
Portanto toda matriz de transição de Markov é uma matriz estocástica.\\
Agora podemos retornar ao problema de construir um processo de difusão sobre um grafo retomando à notação utilizada no decorrer do texto. Assim $X_i\in X$ voltará a ser um elemento do nosso conjunto de dados e não mais uma variável aleatória.
\end{comment}
\begin{defi}\label{defmarkov}
\begin{em}
Chamamos de \emph{matriz de Markov} (ou \emph{matriz de transição de uma cadeia de Markov}) uma matriz cujas entradas s\~ao não negativas
e cuja soma dos elementos de cada linha \'e \emph{um}. Uma matriz com esta propriedade também é chamada de \emph{matriz estocástica}
ou \emph{matriz de transição de probabilidade}.
\end{em}
\end{defi}
Vamos agora normalizar a matriz dos pesos \emph{W} como segue para daí obter uma matriz de Markov.
%
Considere $d_i = (D)_{ii}=\sum _{j=1}^n w_{ij}$ e $p_{ij}=\frac{w_{ij}}{d_i}$ (ver definição \ref{grau} para a matriz \emph{D}). Ao dividirmos por $d_i$ estamos
supondo que não existem linhas de \emph{W} que contenham somente zeros, em outras palavras, estamos supondo que o grafo dos dados não possui vértices isolados, ou ent\~ao pode-se
aumentar $\varepsilon$ de forma a conect\'a-los.
% Não sei se esta frase abaixo é muita besteira
Em geral esta hipótese não enfraquece o problema pois, caso existam tais pontos e, por alguma razão, não seja mais possível aumentar $\varepsilon,$ estes poderão ser estudados separadamente, afinal são isolados. Uma matriz cujas
entradas sejam estes $p_{ij}$ é uma matriz de Markov conforme pode ser visto no teorema a seguir. A matriz $W$ aqui considerada pode ser a matriz dos pesos das
arestas para o grafo originalmente considerado ou já pode incluir as normalizações citadas na seção anterior.
%Antes de prosseguir vamos recordar a definição de matriz de Markov.
\begin{comment}
\begin{defi}\label{markov2}
\begin{em}
Uma \emph{matriz é de Markov} se tiver todos os seus elementos não negativos e se a soma de suas linhas for sempre a unidade.
\end{em}
\end{defi}
\end{comment}
\begin{teo}\label{Pmarkov}
\begin{em}
Seja $W$ a matriz de pesos das arestas de um grafo e $D$ a matriz diagonal que guarda os graus de cada vértice na sua diagonal.
Então a matriz $P= D^{-1}W$ é uma matriz de Markov.
\end{em}
\end{teo}
%
\noindent\begin{demo} % Para fazer quadradinho no final da demonstração
Com as hipóteses do teorema, cada elemento $p_{ij}=\frac{w_{ij}}{d_i}$ pertencente à matriz
$P= D^{-1}W$ é não negativo. Além disso, pela observação após a de\-fi\-ni\-ção~\ref{grau} sabemos que $d_i =(D)_{ii}=\sum_{j=1}^n w_{ij}.$
Portanto, para cada linha $i$ da matriz $P,$ temos
\begin{equation}
\sum_{j=1}^n p_{ij}=\sum_{j=1}^n\frac{w_{ij}}{d_i}= \frac{d_i}{d_i}=1.
\end{equation}
Sendo assim, esta matriz $P= D^{-1}W$ representa uma matriz
%de transição de um processo homogêneo
de Markov definida sobre um grafo.
\end{demo}
%$0 \leq p_{ij} \leq 1$ e
\noindent \textbf{Observação.} A matriz $P= D^{-1}W$ representa um processo de Markov onde os `estados' são os vértices do grafo e a dinâmica consiste em poder sair de qualquer estado $X^i$ para outro $X^j$ com uma probabilidade dada pelos elementos da matriz \emph{P}, ou seja, por
$ p_{ij}=\frac{w_{ij}}{d_{i}}.$
Esquematicamente, a matriz de transição de probabilidade $P$ é dada por:
%
\begin{equation}\label{eqmarkov}
\left.
\begin{array}{c|cccc} % Este comando coloca uma linha vertical
& X^1 & X^2 & \dots & X^n \\ \hline % Este comando é para colocar uma linha aqui
X^1 & \frac{w_{11}}{d_1} & \frac{w_{12}}{d_1} & \dots & \frac{w_{1n}}{d_1} \\
X^2 & \frac{w_{21}}{d_2} & \frac{w_{22}}{d_2} & \dots & \frac{w_{2n}}{d_2} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
X^n & \frac{w_{n1}}{d_n} & \frac{w_{n2}}{d_n} & \dots & \frac{w_{nn}}{d_n} \\
\end{array}
\right.
\end{equation}
% matriz \ref{eqmarkov} % Este comando faz referencia a equação acima
Essa matriz estocástica pode ser interpretada como definindo um \emph{passeio aleatório} sobre o grafo ~\cite{nadler2005diffusion}. Ou seja, $p_{ij}$ é
a probabilidade de um caminhante aleatório ir de $X^i$ a $X^j$ em um passo, por isso chamada \emph{probabilidade de transição de $X^i$ para $X^j$ em um passo}.
Basicamente, essa probabilidade $p_{ij}$ define um novo grafo cuja matriz de adjac\^encia \'e $P$, de
forma que dois n\'os s\~ao conectados por um peso proporcinal \`a similaridade local de $X^i$ a $X^j$ {\em relativa} \`a similaridade de $X^i$ e $X^j$ a
outros $X^k$, $k\neq i,j$.
Se conhecermos um vetor $\beta$ onde cada componente representa a probabilidade do sistema (ou a fra\cao\ de alguma propriedade sua) estar, naquela observação, no \emph{i}-ésimo estado, $\beta_i,$ poderemos
calcular as probabilidades na próxima observação simplesmente fazendo o produto desta matriz por este vetor, $\beta^\top P.$
Com estas informações podemos escrever a \emph{matriz de transição do processo de Markov} criado, lembrando que a probabilidade de transição é dada por $p_{ij}.$
Na pr\'atica $\beta_i$ pode representar a fra\cao\ de alguma propriedade do sistema no n\'o $i$, naquela observa\cao ~ (por exemplo a chance
de cada n\'o de pertencer a uma dada classe). Se tomarmos $\beta$ como sendo
\beas
\beta_i & = & \left\{ \begin{array}{ll} 1, & \mbox{se } i=k, \\
0, & \mbox{caso contr\'ario}
\end{array}
\right.
\ ,
\eeas
ent\~ao representaria um pico de alguma propriedade no n\'o $k$; para estudarmos a geometria do grafo de similaridades
dos dados, podemos tomar essa propriedade como temperatura, ou a propriedade de cada n\'o ser similar ao n\'o $k$ em ordem zero. Fazendo-se
$\beta^{\top}P$, tem-se ent\~ao, um novo vetor representando o grau de cada n\'o de ser similar ao n\'o $k$ em ordem 1. Pode-se
multiplicar novamente por $P$ e obter a similaridade em ordem 2 (i.e., passando-se por duas arestas intermedi\'arias), e assim por diante.
Haver\'a uma distribui\cao\ estacion\'aria, como no caso do PageRank \cite{page1999pagerank} e GraphCuts \cite{belkin2003laplacian}, por\'em as aplica\coes\ de
difus\~ao utilizam resultados de ordem intermedi\'aria (tempos finitos) como recurso de modelagem.
Ao considerarmos potências da matriz acima, $P^t= (D^{-1}W)^t,$ estamos portanto aumentando o número de passos do caminho aleatório acima citado, ou ainda, podemos
dizer que estamos observando o conjunto de dados em diferentes escalas de tempo ou espa\c{c}o. Quanto maior o expoente \emph{t}, mais o processo de Markov vai incorporar a geometria intrínseca do conjunto de dados. Assim como $p_{ij}$ podia ser interpretada como a probabilidade de transição de $X^i$ para $X^j$ num único passo, podemos também interpretar cada elemento da matriz
$P^t= (D^{-1}W)^t, $ $p^{t}_{ij},$ como a probabilidade de transição de $X^i$ para $X^j$ em \emph{t} passos, ou seja, como a probabilidade associada ao conjunto de todos os caminhos de comprimento \emph{t} saindo de $X^i$ para $X^j$.
No nosso caso discreto este processo de difusão criado equivale a um caminho aleatório (um \emph{random walk}).
Observe que quanto maior a afinidade entre os vértices $X^i$ e $X^j,$ representada pelo peso da aresta $w_{ij},$ maior será a probabilidade de transição entre eles.
Isto se deve ao fato de que para calcularmos tal probabilidade dividimos o peso da aresta $w_{ij}$ pela soma das afinidades de $X^i$ com todos os outros vértices.
Note que a \emph{i}-ésima linha do produto da matriz \emph{P} dada na equa\cao~(\ref{eqmarkov}) acima por um vetor adequado \textbf{y}, nada mais é do que a média ponderada das componentes $y_j$ do vetor tendo como coeficientes os valores $\frac{w_{ij}}{d_i}$ que são todos positivos e cuja soma é 1. Esta afirmação é facilmente comprovada pela expressão:
%
\begin{equation}
(P\textbf{y})_i=\sum_{j=1}^n p_{ij}y_j=\sum_{j=1}^n \frac{w_{ij}}{d_i}y_j.
\end{equation}
Em particular, note que se $ \textbf{y} = \openone$ então $y_j = 1,$ para cada $j$ e
$(P\textbf{y})_i=1,$ para todo $i.$ Ou seja, $P\openone = \openone=1\cdot \openone$. Como vimos anteriormente, isto quer dizer
que o vetor constante é autovetor de \emph{P} associado ao autovalor 1.
Esse vetor \textbf{y} também
pode representar os valores de uma dada função \emph{f} sobre os vértices do grafo. Considere
$X^i \in \re^d$ como sendo um vértice do grafo. Então cada componente do vetor \textbf{y}, $y_l,$ pode
representar $f(X^l)$ com \emph{f} sendo uma função de $E \subset \re^d$ em $\re.$
Assim, a \emph{i}-ésima linha do produto acima, $(P\textbf{y})_i,$ vai representar a média ponderada das imagens dos vizinhos do \emph{i}-ésimo
vértice pela função \emph{f} considerada. A ponderação para o \emph{j}-ésimo vizinho do vértice \emph{i} será exatamente a probabilidade de
transição do vértice \emph{i} para o vértice \emph{j}. De fato, para um vértice $X^l$ que não seja vizinho do vértice \emph{i} a probabilidade $p_{il}$ será
praticamente nula e não contará efetivamente para a média. Portanto só contarão aqueles vértices que sejam vizinhos do vértice \emph{i}.
Podemos pensar na operação $Pf = P\textbf{y}$ como uma forma de codificar o valor esperado da função \emph{f} depois de um passo do passeio aleatório. Já $P^2f$ codifica o valor esperado da função \emph{f} depois de dois passos do passeio aleatório e assim sucessivamente ~\cite{Tibshirani:DataMining15_2009}.
Em outras palavras, a matriz de transição do processo de Markov criado pode prever o valor de uma dada função aplicada aos vértices do grafo.
%casos discretos um processo de difusão equivale a um random walk processo estocástico em tempo discreto.‏ .
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Ver se vou manter aspas ou não em distância de difusão.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Dist\^ancia de difus\~ao}\label{difdis2}
A este processo de difusão corresponde uma família de ``distâncias''
de difusão, $D_{t}(X^i,X^j).$ Tal família mede a taxa de conectividade dos pontos $X^i$ e $X^j$ por caminhos de comprimento \emph{t} nos dados.
%Esta distância pode ser definida pela expressão:
%\todo{Decidir: t é o comprimento do caminho ligando dois vértices do grafo ou t é o nº de caminhos ligando estes dois vértices? Ou as duas coisas dão no mesmo?}
%
\begin{defi}\label{distdiff}
\begin{em}
Chamamos de \emph{distância de difusão} entre os dados $X^i$ e $X^j,$ para cada \emph{t} fixo, o número
\begin{equation}\label{dist}
D_{t}(X^i,X^j)=\left(\sum_{X^r \in E}\frac{(p^{t}_{ir}-p^{t}_{jr})^2}{\sigma_r}\right)^{1/2},
\end{equation}
onde $\sigma_r=\frac{d_r}{\sum_{i=1}^n d_i}$.
\end{em}
\end{defi}
\noindent \textbf{Observa\c{c}\~oes} i) Note que $\sigma_r$ é o quociente entre o grau
do vértice $X^r$ e a soma de todos os graus dos vértices do grafo, ou seja, uma espécie de densidade de grau (ou import\^ancia relativa)
do \emph{r}-ésimo vértice \cite{lafon2006diffusion}.
\noindent ii) Esta ``distância'' pode ser vista como uma espécie de medida de acessibilidade entre dois vértices do grafo, uma ``for\c{c}a de conexidade''.
Ela será pequena se $p_{ir}^t$ for próximo a $p_{jr}^t,$ para todo $r,$ isto é, se para todo o vértice $r,$ a acessibilidade a partir do vértice $i$
(medida pela probabilidade de transição em $t$ passos, $p_{ir}^t)$ é aproximadamente igual à acessibilidade a partir de $j.$
%se existe um grande número de caminhos conectando $X^i$ e $X^j$ e grande caso contrário.
Outras medidas de acessibilidade em grafos tamb\'em
existem \cite{travenccolo2008accessibility}.
\noindent iii) Note que a ``distância'' acima também pode ser vista como uma distância euclidiana ponderada entre as linhas
$i,j$ de $P^t = (D^{-1}W)^t$ com pesos $1/\sigma_r.$ A princ\'{\i}pio, esta ``distância'' não é uma métrica porque podemos ter $D_t(x,y)=0$ com $x\neq y.$
%
\begin{exem}
\bem {\bf A dist\^ancia de difus\~ao n\~ao \'e uma m\'etrica nos v\'ertices do grafo}
Por exemplo, considere a matriz dos pesos
%"Se (tem muitos caminhos) então (dist pequena)", mas não vale a recíproca, ou sj, podemos ter dist pequena com poucos (ou nenhum) caminhos de comprimento um ligando estes dois pontos}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\begin{equation*}
W = \left[
\begin{array}{ccc}
0 & 0 & 1 \\
0 & 0 & 1 \\
1 & 1 & 0 \\
\end{array}
\right].
\end{equation*}
%
Neste caso temos três vértices e as arestas existentes têm peso $1$ conforme Figura \ref{grafo}. A matriz de transição da cadeia de Markov correspondente será
\begin{equation*}
P = D^{-1}W = \left[
\begin{array}{ccc}
0 & 0 & 1 \\
0 & 0 & 1 \\
1/2 & 1/2 & 0 \\
\end{array}
\right].
\end{equation*}
%
Usando a definição \ref{distdiff} vamos calcular a distância de difusão entre os vértices $X^1$ e $X^2$ para
$t = 1.$ Assim,
\begin{equation*}
D_{1}(X^1,X^2)=\left(\frac{(p_{11}-p_{21})^2}{\sigma_1}+\frac{(p_{12}-p_{22})^2}{\sigma_2}+\frac{(p_{13}-p_{23})^2}{\sigma_3}\right)^{1/2}
=\sqrt{0+0+0}=0,
\end{equation*}
portanto a distância de difus\~ao entre $X^1$ e $X^2$ do grafo é nula apesar de serem dois vértices diferentes do grafo,
logo n\~ao \'e uma m\'etrica no conjunto de v\'ertices do grafo.
\fem
\fim
\end{exem}
\noindent \textbf{Observa\c{c}\~oes} i) Este exemplo ilustra o fato de que embora a distância de difusão seja nula entre dois vértices diferentes,
as linhas correspondentes a estes vértices em $P=D^{-1}W$ são vetores iguais em $\re^3$ gerando portanto uma distância
euclidiana nula entre as linhas de $P$. Isto se deve ao fato de que os dois vértices considerados para a distância
de difusão estão simetricamente colocados no grafo no que diz respeito ao peso das arestas.
\noindent ii) Fixado $t$, em cada v\'ertice $i$ do grafo h\'a associada a linha $i$ da matriz $P^t$. Como os elementos de cada linha de $P^t$ somam um,
ent\~ao cada linha pode ser interpretada como uma distribui\cao\ de probabilidade, a probabilidade de transi\cao\ em $t$
passos do v\'ertice $i$ para cada um dos v\'ertices do grafo. Assim, a dist\^ancia de difus\~ao entre dois v\'ertices do grafo \'e nula se essas
distribui\coes\ de probabilidade se igualarem. Em outras palavras, se o {\em futuro} dos dois v\'ertices for id\^entico.
\noindent iii) Note, por\'em, que se $W$ representa uma medida de similaridade, ent\~ao $w_{ii}$ n\~ao pode ser zero, como no exemplo acima. Para o
n\'ucleo gaussiano, $w_{ii}=1$ e $0<w_{ij}<1$, para todo $i\neq j$. Isto garante que $D_t(X,Y)=0\Longrightarrow X=Y$. De fato,
\beas
w_{ij} & = & \left\{ \begin{array}{ll} 1, & \mbox{se } i=j \\
0<w_{ij}< 1 & \mbox{caso contr\'ario}
\end{array}
\right.
\ ,
\eeas
$D_{ii} = \sum_{k=1}^n w_{ik}$, $D_{ij}=0$, para $i\neq j$, ent\~ao,
\beas
(D^{-1})_{ij} & = & \left\{ \begin{array}{ll} (\sum_{k=1}^n w_{ik})^{-1}, & \mbox{se } i=j\\
0 & \mbox{caso contr\'ario}
\end{array}
\right.
\ ,
\eeas
donde, $(D^{-1}W)_{lc}=\frac{w_{lc}}{\sum_{k=1}^n w_{lk}}$. Logo, $D_1 (X^i,X^j)=0$ se, e somente se, as linhas $i$ e $j$ de $D^{-1}W$ forem
id\^enticas. Ou seja
\bea
\frac{w_{ic}}{\sum_{k=1}^n w_{ik}} & = & \frac{w_{jc}}{\sum_{k=1}^n w_{jk}} \ , \mbox{ para todo o }c. \label{4star}
\eea
Em particular, sabemos que $w_{ii}=1$. Logo
\beas
\frac{1}{\sum_{k=1}^n w_{ik}} = \frac{w_{ji}}{\sum_{k=1}^n w_{jk}} & \Longrightarrow & w_{ji} = \frac{\sum_{k=1}^n w_{jk}}{\sum_{k=1}^n w_{ik}} \ .
\eeas
Tamb\'em sabemos que $w_{jj}=1$, logo da equa\cao~(\ref{4star}) temos
\beas
\frac{w_{ij}}{\sum_{k=1}^n w_{ik}} = \frac{1}{\sum_{k=1}^n w_{jk}} & \Longrightarrow & w_{ij} = \frac{\sum_{k=1}^n w_{ik}}{\sum_{k=1}^n w_{jk}} \ .
\eeas
Como $W$ \'e sim\'etrica, $w_{ij}=w_{ji}$ donde
\beas
\frac{\sum_{k=1}^n w_{ik}}{\sum_{k=1}^n w_{jk}} = \frac{\sum_{k=1}^n w_{jk}}{\sum_{k=1}^n w_{ik}}
& \Longrightarrow & \sum_{k=1}^n w_{ik}= \sum_{k=1}^n w_{jk}\ ,
\eeas
o que em face da equa\cao~(\ref{4star}) implica $w_{ik}=w_{jk}$, para todo $ k$.
Logo demonstramos que $D_1(X^i, X^j)=0$ implica que $w_{ik}=w_{jk}$, para todo $k $. Mas duas linhas de $W$ n\~ao podem ser iguais pois se $i\neq j$ ent\~ao
$w_{ii}=1$ implica que $w_{ji}=1=w_{jj}$, o que n\~ao pode ocorrer com $W$ uma matriz de similaridade. Logo $D_1(X^i,X^j)=0$ implica que $i=j$.
\fim
%
\begin{figure}
\begin{center}
\includegraphics[scale=0.6]{grafo.jpg}
\caption[Grafo - distância de difusão]{Um exemplo de grafo onde a ``distância'' de difusão entre os vértices $X^1$ e $X^2$ é nula.}
\label{grafo}
\end{center}
\end{figure}
%Podemos dizer que a distância de difusão entre dois vértices do grafo mede a diferença entre a difusão dos mesmos com respeito a todos os outros vértices do grafo. Uma das vantagens de métodos de classificação ou clusterização baseados na métrica de difusão é que não estarão sujeitos a instabilidades relacionadas a uma realização particular de um conjunto de dados ~\cite{lafon2004diffusion}.\\
% Acho que este parágrafo é repeteco e devo tirar
%A distância de difusão também tem a vantagem de ser robusta à perturbação de ruídos nos dados. Isso se dá devido ao fato de que esta distância é calculada como uma soma sobre todos os caminhos ligando os dois vértices. Esta soma tem um efeito suavizante sobre pequenas perturbações no conjunto de dados ~\cite{lafon2004diffusion}.
%A distância de difusão é capaz de aproximar distâncias ao longo de uma estrutura geométrica não linear. Mas este cálculo é caro do ponto de vista computacional. Por isso é conveniente aplicar os dados num espaço euclidiano de acordo com a métrica de difusão. A distância de difusão no espaço de dados (onde está o grafo) se torna a distância euclidiana no espaço de difusão (onde está a imagem mergulhada).
% O parágrafo de cima ou o de baixo deverão sair, ou então ver como juntá-los pois estão repetecos
\section{Estrutura espectral da matriz de Markov}\label{markovaut}
A aplicação de difusão mapeia distâncias de forma conveniente, no sentido
que a distância de difusão entre dados no espaço de entrada
se iguala à distância euclidiana entre suas imagens por tal aplicação, como veremos adiante.
%Como acontece em outros métodos de redução de dimensionalidade, para atingir tal intento é necessário resolver um problema de minimização, que poderá ser convertido num problema de autovalores para a matriz de Markov acima citada.
% Aqui acho que eu deveria usar multiplicadores de Lagrange e chegar no problema de autovalor como eu fiz no caso do PCA para o seminário
%Obs: suponha \emph{n} dados distribuídos uniformemente em uma variedade \emph{M}. Minimizar $\sum W_{ij}(y_i - y_j)^2$ é calcular as autofunções de $D^{-1/2}W D^{1/2}$ \cite{coifman2005geometric}.\\
Revendo a construção do nosso processo desde o início percebemos que criamos uma função \emph{K} e a associamos
à matriz de pesos \emph{W} que é simétrica, mas não é, necessariamente, uma matriz de Markov.
%pois em alguns casos podemos ter $w_{ij}>1.$\\
Em seguida vimos que normalizando \emph{W}, ou seja, criando a matriz $P=D^{-1}W$ podemos
descrever um sistema din\^amico, já que $P$ é uma matriz de transição de Markov. Note que, embora \emph{P} seja uma matriz estocástica, tem a desvantagem de não ser simétrica. Para recuperar a simetria, que nos permitirá utilizar propriedades espectrais simples, vamos definir uma nova matriz simétrica $\widetilde{P}$ similar a \emph{P} conforme será descrito no teorema a seguir.
\begin{comment}
Considere
$$\widetilde{a}(X_i,X_j)=a(X_i,X_j)\frac{\sqrt{v(X_i)}}{\sqrt{v(X_j)}}.$$
Vamos verificar agora que $\widetilde{A}$ é simétrica. Já vimos que $K(X_i,X_j)=K(X_j,X_i)$ então podemos escrever
$$\frac{K(X_i,X_j)}{v(X_i)}=\frac{K(X_j,X_i)}{v(X_j)}.\frac{v(X_j)}{v(X_i)}$$ então
$$a(X_i,X_j)=a(X_j,X_i)\frac{v(X_j)}{v(X_i)}$$ multiplicando por $v(X_i)$
$$a(X_i,X_j)v(X_i)=a(X_j,X_i)v(X_j)\Rightarrow a(X_i,X_j)(\sqrt{v(X_i)})^2=a(X_j,X_i)(\sqrt{v(X_j)})^2$$
Daí $$a(X_i,X_j)(\sqrt{v(X_i)})(\sqrt{v(X_i)})=a(X_j,X_i)(\sqrt{v(X_j)})(\sqrt{v(X_j)})$$
Dividindo por $\sqrt{v(X_i)}\sqrt{v(X_j)}$ temos
$$a(X_i,X_j)\frac{\sqrt{v(X_i)}}{\sqrt{v(X_j)}}=a(X_j,X_i)\frac{\sqrt{v(X_j)}}{\sqrt{v(X_i)}}$$
portanto
$$\widetilde{a}(X_i,X_j)=\widetilde{a}(X_j,X_i)$$
mostrando que $\widetilde{a}$ é simétrica.
\end{comment}
%
\begin{teo}\label{ptil}
\begin{em}
Considere $\widetilde{P}=D^{1/2} PD^{-1/2},$ onde $D$ é a matriz grau, $W$ é a matriz de adjacência de um grafo e $P=D^{-1}W.$ Então\\
$(a)$ $\widetilde{P}$ é simétrica.\\
$(b)$ $\widetilde{P}$ e $P$ têm os mesmos autovalores.
\end{em}
\end{teo}
%
\noindent\begin{demo}
$(a)$ Para verificar a simetria de $\widetilde{P}$ basta substituir $P=D^{-1}W$ na definição de $\widetilde{P},$ assim $\widetilde{P}=D^{1/2} (D^{-1}W)D^{-1/2}=D^{-1/2} WD^{-1/2}.$ Como \emph{W} é simétrica e \emph{D} diagonal, verifica-se facilmente que $\widetilde{P}^\top = \widetilde{P}.$
\begin{comment}
Podemos pensar que $\widetilde{A}$ representa um outro operador de difusão cujo o núcleo é dado por $\widetilde{a}(X_i,X_j)$ que é equivalente a $\frac{W_{ij}}{\sqrt{(D)_i(D)_j}}$ desta forma podemos verificar que $\widetilde{A}$ nada mais é que $\widetilde{A}=D^{-1/2} WD^{-1/2}.$ Embora $\widetilde{A}$ seja simétrica a soma das linhas não é necessáriamente 1. Portanto $\widetilde{A}$ não representa um processo de Markov, mas tem a vantagem de ser similar a \emph{A} o que implica ter os mesmos autovalores de \emph{A} que são menores ou iguais a 1 já que \emph{A} representa uma cadeia de Markov como visto anteriormente.
\end{comment}
$(b)$ (Parte desta demonstração já foi feita no teorema \ref{equiv}, mas repetiremos aqui para melhor clareza de ideias.)
Se $\lambda$ for autovalor de \emph{P} associado ao autovetor à direita $\bmv$ ou seja, $P\bmv=\lambda\bmv$, então,
como $\widetilde{P}=D^{1/2} PD^{-1/2}$ podemos escrever
$P =D^{-1/2} \widetilde{P}D^{1/2}$ e substituindo em $P\bmv=\lambda\bmv$ nos levará a
$(D^{-1/2} \widetilde{P}D^{1/2})\bmv=\lambda \bmv$. Multiplicando ambos os lados
à esquerda por $D^{1/2}$ teremos $\widetilde{P}(D^{1/2}\bmv)=\lambda (D^{1/2}\bmv)$.
Portanto $\lambda$ também é autovalor de $\widetilde{P}$ mudando apenas o autovetor associado à direita para $D^{1/2}\bmv$.
O mesmo acontece para autovetores à esquerda de $\widetilde{P}.$
De fato, se $\lambda$ for autovalor de \emph{P} associado ao autovetor \textbf{u} à esquerda, ou seja, $\textbf{u}^\top P=\lambda \textbf{u}^\top,$
então substituindo $P =D^{-1/2} \widetilde{P}D^{1/2}$ em $\textbf{u}^\top P=\lambda \textbf{u}^\top,$ temos
$\textbf{u}^\top (D^{-1/2} \widetilde{P}D^{1/2})=\lambda \textbf{u}^\top.$ Multiplicando pela direita ambos os lados da igualdade por $D^{-1/2}$
temos $(\textbf{u}^\top D^{-1/2})\widetilde{P}=\lambda (\textbf{u}^\top D^{-1/2}).$
Portanto $\lambda$ também é autovalor de $\widetilde{P}$ mudando apenas o autovetor associado à esquerda para $D^{-1/2}\textbf{u}.$
\end{demo}
%\draftnote{ver se está igual no cap de grafos, última seção}
\noindent \textbf{Observação.} Podemos extrair da demonstração anterior a relação entre os autovetores de $P$ e $\widetilde{P}$ como segue:
\begin{itemize}
\item[i)] Se $P\textbf{v}=\lambda \textbf{v}$ e $\widetilde{P}\widetilde{\textbf{v}}=\lambda \widetilde{\textbf{v}}$ então
$\widetilde{\textbf{v}} = D^{1/2}\textbf{v}$ (ou $\textbf{v} = D^{-1/2}\widetilde{\textbf{v}})$ é um representante dos
autovetores à direita de $\widetilde{P}$ (ou de $P)$ associados ao autovalor $\lambda$.
\item[ii)] Para uma matriz qualquer, os autovalores pela esquerda são os mesmos que pela direita. Assim, se
$\textbf{u}^\top P=\lambda \textbf{u}^\top$ e $\widetilde{\textbf{u}}^\top\widetilde{P} = \lambda \widetilde{\textbf{u}}^\top$ então
$\widetilde{\textbf{u}}^\top = \textbf{u}^\top D^{-1/2}$ (ou $\textbf{u}^\top = \widetilde{\textbf{u}}^\top D^{1/2})$
é um representante dos autovetores à esquerda de $\widetilde{P}$ (ou de $P)$ associados a $\lambda$. Como $\widetilde{P}$ é simétrica os autovetores
à direita e à esquerda são os mesmos, ou seja, $\widetilde{\textbf{u}} = \widetilde{\textbf{v}}$ e portanto
$\textbf{u} = D\textbf{v}.$
% $\textbf{e}^\top = \widetilde{\textbf{v}}^\top D^{1/2}.$
%\item $\lambda$ também é autovalor de $\widetilde{P}$ associado ao autovetor à esquerda $v^TD^{-1/2}$
\fim
\end{itemize}
\begin{comment}
Se \emph{W} for positiva semi-definida podemos ver facilmente que $\widetilde{A}$ também o é. De fato, para qualquer vetor \emph{x} temos
$$ x^\top\widetilde{A}x = x^\top(D^{-1/2} WD^{-1/2})x = x^\top(D^{-1/2})^\top WD^{-1/2}x =$$
$$= (D^{-1/2}x)^\top W(D^{-1/2}x)= y^TWy \geq 0, \forall y = D^{-1/2}x, $$
pois estamos considerando \emph{W} como sendo positiva semi-definida. Portanto $x^\top\widetilde{A}x\geq 0, \forall x$ e
$\widetilde{A}$ é positiva semi-definida.
Esta observação nos permite concluir que os autovalores de $\widetilde{A}$ são reais e maiores ou iguais a zero.\\
\end{comment}
Por outro lado, como $P=D^{-1}W$ representa um Processo de Markov, o teorema a seguir nos diz que seus autovalores em módulo são menores ou iguais a um.
\begin{teo}\label{autmarkov}
\begin{em}
Sejam $D$ a matriz grau e $W$ a matriz de pesos de um grafo.
Se $P=D^{-1}W$ e $P\bmv= \lambda \bmv$, $\bmv\neq 0,$ então $\mid\lambda\mid \leq 1.$\\
\end{em}
\end{teo}
%
\noindent\begin{demo}
Suponha que $P\bmv= \lambda \bmv$,
$\lambda \in \mathbb{C}$ e $\bmv \in \mathbb{C}^n$ sejam autovalores e autovetores correspondentes da matriz $P$ de Markov.
Considere as componentes do vetor $\bmv$ como sendo $v_1,v_2, \ldots, v_n.$
Seja \emph{k} tal que $\mid v_j \mid \leq \mid v_k \mid, \forall j, 1 \leq j \leq n.$
Desenvolvendo a \emph{k}-ésima linha do produto $P\bmv= \lambda \bmv,$ temos:
\begin{equation*}
\sum_{j=1}^n p_{kj}v_j= \lambda v_k.
\end{equation*}
%
Então
\begin{equation*}
\mid \lambda v_k \mid = \mid \lambda \mid \mid v_k \mid =\mid \sum_{j=1}^n p_{kj}v_j \mid \leq
\sum_{j=1}^n p_{kj}\mid v_j \mid \leq \sum_{j=1}^n p_{kj}\mid v_k \mid = \mid v_k \mid \sum_{j=1}^np_{kj}.
\end{equation*}
%
Dai, $\mid \lambda \mid \mid v_k \mid \leq \mid v_k \mid$ então $\mid \lambda \mid \leq 1.$
\end{demo}
%Esta observação também se aplica aos autovalores de $\widetilde{A}$ já que são os mesmos de \emph{A}.
%Note que se $P\textbf{v}=\lambda \textbf{v}$ então $D^{-1}W\textbf{v}=\lambda \textbf{v},$ ou seja, $W\textbf{v}=\lambda D\textbf{v}.$ Portanto o mesmo $\lambda$ é autovalor generalizado de \emph{W} associado ao mesmo autovetor \textbf{v} de \emph{P}.
Como vimos no Teorema \ref{ptil} que os autovalores de \emph{P} são os mesmos de $ \widetilde{P}$
podemos concluir que os autovalores de \emph{P} e $\widetilde{P}$ são números reais entre menos um e um inclusive.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Seria muito bom se os autovalores estivessem entre 0 e 1. Será que não poderia falar aqui que W (ou $D^{-1}W$) é p. s. d. e por isso os autovalores estão entre 0 e 1? Mas tenho que mostrar estas coisas em algum lugar, não adianta só falar. VER seção 5.2 que criei para falar da escolha de W. Ainda não terminei, na verdade só comecei.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As relações entre \emph{P} e $\widetilde{P}$ serão utilizadas na demonstração do teorema a seguir que
apresenta um tipo de decomposição espectral de \emph{P} a partir da decomposição de $\widetilde{P}$ (e tamb\'em de $P^t$).
%\subsection*{Decomposição espectral de\emph{ P } a partir de $\widetilde{\textbf{P}}:$}
%
\begin{teo}\label{despectral}
\begin{em}
Seja $P^t=(D^{-1}W)^t$ para algum $t \in \mathbb{N},$ onde $D$ é a matriz grau e $W$ é a matriz de pesos de um grafo. Então
$$ P^t = \sum_{k=0}^{n-1}\lambda_k^t\textbf{v}_k\textbf{u}_k^\top$$
onde os $\textbf{v}_k = (v_k(1), \ldots, v_k(n))^\top$ são autovetores à direita de $P$ associados a
$\lambda_k$ e $\textbf{u}_k^\top = (u_k(1), \ldots, u_k(n))^\top$ são autovetores à esquerda de $P.$ Assim,
cada elemento de $P^t$ pode ser escrito como
$$ p^t_{ij}= \sum_{k=0}^{n-1}\lambda_k^t v_k(i)u_k(j),$$
\end{em}
\end{teo}
%
\noindent\begin{demo}
Considere
\begin{equation}\label{eq1}
\widetilde{P} = D^{1/2} PD^{-1/2}
\end{equation}
%
Como $\widetilde{P}$ é uma matriz simétrica real o teorema espectral
nos diz que existe uma base ortonormal de autovetores de $\widetilde{P}$ tal que
%
\begin{equation}\label{eq2}
\widetilde{P} = S \Lambda S^\top,
\end{equation}
onde \emph{S} é uma matriz cujas colunas são os autovetores ortonormais à direita de $\widetilde{P}$ e $\Lambda $
é uma matriz diagonal contendo os autovalores de $\widetilde{P}$.
Reescrevendo (\ref{eq1}) com $P$ em função de $\widetilde{P}$ e substituindo (\ref{eq2}) em (\ref{eq1}) temos
\begin{equation*}
P = D^{-1/2} (S \Lambda S^\top)D^{1/2}.
\end{equation*}
%
Dado que \emph{S} é matriz ortogonal sabemos que $S^\top = S^{-1}$ então
$P = D^{-1/2} S \Lambda S^{-1}D^{1/2},$ ou ainda,
%\begin{equation}\label{eq3}
$P = (D^{-1/2} S) \Lambda (D^{-1/2}S)^{-1}.$
%\end{equation}
%
Chamando $Q = D^{-1/2}S,$ podemos escrever
%
\begin{equation}\label{eq3}
P = Q \Lambda Q^{-1}.
\end{equation}
%
Como as colunas de \emph{S} são os autovetores à direita de $\widetilde{P}$ então, pela observação após o teorema \ref{ptil}, as colunas de \emph{Q} são
os autovetores à direita de $P,$ uma vez que $Q = D^{-1/2}S.$
Analogamente, como $ Q^{-1} = (D^{-1/2}S)^{-1} = S^{-1}D^{1/2} = S^\top D^{1/2} $ então as linhas de $Q^{-1}$ são os autovetores à esquerda de \emph{P}.
%
Considerando \textbf{v} como autovetores à direita e $\textbf{u}^\top$ como autovetores à esquerda de $P,$ a equação (\ref{eq3}) nos permite escrever:
\begin{equation*}
P =\left[
\begin{array}{ccc}
| & & | \\
\textbf{v}_0 & \cdots &\textbf{v}_{n-1} \\
| & & | \\
\end{array}
\right]
\left[
\begin{array}{ccc}
\lambda_0 & & \\
& \ddots & \\
& & \lambda_{n-1} \\
\end{array}
\right]
\left[
\begin{array}{ccc}
- & \textbf{u}_0^\top & - \\
& \vdots & \\
- & \textbf{u}_{n-1}^\top & - \\
\end{array}
\right]
\end{equation*}
%
Ou ainda, $P = \sum_{k=0}^{n-1}\lambda_k\textbf{v}_k\textbf{u}_k^\top,$
onde $\textbf{v}_k$ é um vetor coluna ou uma matriz $n \times 1$ e $\textbf{u}_k^\top$ é um vetor linha ou uma matriz $1 \times n.$
Note que uma posição $i,j$ desta matriz poderá ser escrita como
$ p_{ij}= \sum_{k=0}^{n-1}\lambda_k v_k(i) u_k(j).$
A partir da equação (\ref{eq3}) podemos facilmente verificar que $ P^t = Q\Lambda^tQ^{-1}.$ Daí podemos,
finalmente, escrever
$ p^t_{ij}= \sum_{k=0}^{n-1}\lambda_k^t v_k(i)u_k(j)$ como desejado.
\end{demo}
\begin{teo} \label{zero_um}
\bem
Quando $W$ for positiva semidefinida, os autovalores de $P=D^{-1}W$ est\~ao entre zero e um, inclusive.
\fem
\end{teo}
\begin{demo}
Sabemos que os autovalores de $P$ s\~ao reais. Seja $\bmv$ um autovetor de $P$ e $\lambda$ o correspondente autovalor. Ent\~ao $P\bmv=\lambda\bmv$, donde $D^{-1}W\bmv=\lambda\bmv$
e $W\bmv= \lambda D \bmv$. Multiplicando a \'ultima identidade \`a esquerda por $\bmv^{\top}$, obtemos
\beas
0 \leq \bmv^{\top} W \bmv& = & \lambda \bmv^{\top} D \bmv \ .
\eeas
Como $\bmv^{\top}D\bmv>0$, conclui-se que $\lambda\geq 0$ e, uma vez que j\'a sab\'{\i}amos que $\lambda\leq 1$, conclu\'{\i}mos a demonstra\cao.
\end{demo}
\noindent {\bf Observa\cao} Da demonstra\cao\ do teorema \ref{despectral} fazemos as seguintes considera\coes:
i) A matriz $Q=D^{-\frac{1}{2}}S$ contém, nas colunas, os autovetores \`a direita de P. Assim,
%
\beas
Q & = & \left( \begin{array}{ccc}
| & & | \\
\bmv_0 & \cdots & \bmv_{n-1}\\
| & & |
\end{array}
\right)
\eeas
onde $P\bmv_i = \lambda_i \bmv_i$, $i=0, \ldots, n-1$, ou, matricialmente, $PQ=Q\Lambda$.
\\
ii) A matriz $Q^{-1}=S^{\top}D^{\frac{1}{2}}$ contém, nas linhas, os autovetores \`a esquerda de P. Logo,
%
\beas
Q^{-1} & = & \left( \begin{array}{ccc}
\mbox{---} & \bmu_{0}^{\top} & \mbox{---} \\
& \vdots & \\
\mbox{---} & \bmu_{n-1}^{\top} & \mbox{---}
\end{array}
\right)
\eeas
onde $\bmu_{j}^{\top}P = \lambda_j \bmu_{j}^{\top}$, $j=0, \ldots, n-1$, ou, matricialmente, $Q^{-1}P=\Lambda Q^{-1}$.
\\
iii) De i) e ii) obtemos
\beas
{\cal I} & = & Q^{-1}Q
\\
& = &
\left( \begin{array}{ccc}
\mbox{---} & \bmu_{0}^{\top} & \mbox{---} \\
& \vdots & \\
\mbox{---} & \bmu_{n-1}^{\top} & \mbox{---}
\end{array}
\right)
\left( \begin{array}{ccc}
| & & | \\
\bmv_0 & \cdots & \bmv_{n-1}\\
| & & |
\end{array}
\right)
\\
& = &
\left( \begin{array}{ccc}
& \vdots & \\
\cdots & \langle \bmu_{i}, \, \bmv_{j}\rangle & \cdots\\
& \vdots &
\end{array}
\right)\ ,
\eeas
donde $\langle \bmu_{i}, \, \bmv_{j}\rangle= \delta_{ij}$, isto \' e, as bases $\{ \bmu_0, \ldots \bmu_{n-1}\}$ e
$\{ \bmv_0, \ldots \bmv_{n-1}\}$ s\~ao bi-ortogonais.
\\
iv) Note que
\beas
Q^{-1} D^{-1} (Q^{-1})^{\top} & = & S^{\top} D^{\frac{1}{2}}D^{-1} D^{\frac{1}{2}} S = I\ ,
\eeas
e como
\beas
(Q^{-1})^{\top} & = & \left( \begin{array}{ccc}
| & & | \\
\bmu_0 & \cdots & \bmu_{n-1}\\
| & & |
\end{array}
\right)
\ ,
\eeas
a entrada $ij$ da matriz $Q^{-1} D^{-1} (Q^{-1})^{\top}$ satisfaz
\bea
\label{5fato}
\delta_{ij} = \bmu_{i}^{\top} D^{-1} \bmu_j & =& \sum_{r=0}^{n-1} \frac{u_{i}(r)u_j(r)}{d_r}
\ .
\eea
\fim
%%%%%%%%%%%%PENSAR SE COLOCO ISSO DEPOIS
\begin{comment}
Se nos detivermos nos produtos dentro dos somatórios poderemos ver cada linha de \emph{P} como uma combinação linear da base formada pelos autovetores à esquerda de \emph{P}.
Desta forma o conjunto dos coeficientes da combinação linear da base para a \emph{i}-ésima linha de \emph{P} pode ser escrito como o vetor:
$$\Phi(i)= \left[
\begin{array}{c}
\lambda_1v_1(i) \\
\lambda_2v_2(i)\\
\vdots \\
\lambda_nv_n(i) \\
\end{array}
\right]
$$
\begin{center}
\textbf{VIAJANDO...}
\end{center}
Como $P=D^{-1}W$ não é simétrica a base não é ortonormal, ou seja, $e_i^Te_j \neq \delta_{ij}.$ Podemos tentar uma espécie
de normalização utilizando as relações entre os autovetores de \emph{P} e de $\widetilde{P}$ \cite{de2008introduction}.\\
Note que
$$e_i^TD^{-1}e_j = (e_i^TD^{-1/2})(D^{-1/2}e_j) = (e_i^TD^{-1/2})((D^{-1/2})^\top(e_j^\top)^\top) = $$
$$= (e_i^TD^{-1/2})(e_j^\top D^{-1/2})^\top = \widetilde{e}_i^\top(\widetilde{e}_j^\top)^\top = $$
$$(\widetilde{e}_i^\top\widetilde{e}_j) =\delta_{ij},$$
pois $\widetilde{P}$ é simétrica e portanto a base de autovetores à esquerda é ortonormal.\\
\end{comment}
\begin{comment}
"As autofunções têm a interpretação clássica de uma base ortonormal, e seu conteúdo de frequência pode ser relacionado ao espectro do operador \emph{A} no que se constitui um Princípio Generalizado de Heisenberg." \cite{coifman2005geometric}\\
\end{comment}
\begin{comment}
Da teoria espectral dos grafos sabemos que $L = D - W$ então é fácil fazer uma relação entre autovalores de todas estas matrizes envolvidas: \emph{A}, $\widetilde{A}$, \emph{W} e \emph{L}. Isto nos permitirá desenvolver a parte teórica do problema. \\
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A aplica\cao\ de difus\~ao}
Nesta se\cao\ apresentamos a aplica\cao\ de difus\~ao que transforma sinais do conjunto de treinamento em {\em features} em um espa\c{c}o de
caracter\'{\i}sticas intr\'{\i}nseco \`as observa\coes, provendo uma parametriza\cao\ dos dados e servindo para tarefas como clusteriza\cao\ e reconhecimento de sinais.
Essa aplica\cao\ tem um par\^ametro $t$ que funciona
como um tipo de escala, sendo uma das novidades em rela\cao\ \`as autofun\coes\ do Laplaciano. Quanto maior for o $t$ maior ser\'a a escala considerada na modelagem, fornecendo uma esp\'ecie de an\'alise
multi-escala dos dados. Os dados conectados localmente v\~ao, \`a medida que $t$ cresce, se conectando a outros atrav\'es da cadeia de
Markov, permitindo que evid\^encias existentes de afinidades long\'{\i}nquas entre sinais se estabele\c{c}am de forma robusta e intr\'{\i}nseca ao
conjunto de observa\coes. Inicialmente as evid\^encias de afinidade
s\~ao provenientes de uma vizinhan\c{c}a local, ou medidas de dist\^ancia extr\'{\i}nseca que fazem sentido apenas
localmente. Ao passo que o n\'umero de passos da cadeia de Markov aumenta, afinidades de $2^a$ ordem, de $3^a$ ordem, etc v\~ao
se estabelecendo, ampliando a escala considerada, relaxando a no\cao\ de afinidade, permitindo um caminho de proximidade ligando v\'ertices originalmente com pouca afinidade,
(para os quais a medida extr\'{\i}nseca de dist\^ancia faz pouco ou nenhum sentido) ampliando a escala considerada. Passamos ent\~ao \`a defini\cao\ de aplica\cao\ de difus\~ao.
\begin{defi}\label{defdiff}
\begin{em}
Sejam $\textbf{v}_0, \textbf{v}_1, \ldots, \textbf{v}_{n-1}$ autovetores à direita de $P=D^{-1}W$ associados a
$\lambda_0=1 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}\geq -1.$ Para cada $t$ fixo chamaremos de \emph{aplicação de difusão} a função
$\diff_t$ tal que
\begin{equation}\label{eqdiff}
\diff_t(X^i) = \left(
\begin{array}{c}
\lambda_1^t v_1(i) \\
\lambda_2^t v_2(i) \\
\vdots \\
\lambda_{n-1}^t v_{n-1}(i) \\
\end{array}
\right),
\end{equation}
para cada $X^i$ pertencente ao conjunto de dados\footnote{Note que $\lambda_0$ n\~ao \'e utilizado pois $\bmv_0$ \'e constante.} $E.$
\end{em}
\end{defi}
Com esta definição vemos que
a aplicação de difusão leva um dado
$X^i \in E \subset \re^{d}$ num vetor de características $Y^i \in F \subset \re^{n-1}.$ Se $n-1 < d$ já teremos realizado uma primeira redução de dimensionalidade, mas ainda assim vamos prosseguir na análise que nos conduzirá a uma maior eficiência da técnica.
Uma nova expressão para a distância de difusão ser\'a apresentada e ficar\'a mais fácil verificar que a aplicação de difusão
garante a igualdade entre a distância de difusão dos dados iniciais e a distância euclidiana entre suas caracter\'{\i}sticas ({\em features}).
Esta é a chave do método das aplicações de difusão.
Para isto vamos utilizar a decomposição espectral de $P^t= (D^{-1}W)^t$ que acabamos de obter associando os índices $i,j$
com dados de entrada $X^i,X^j.$ O expoente $t$ usado no Teorema \ref{despectral} será o parâmetro escolhido para o número de passos no processo estocástico de Markov.
%
%\todo{ Se tiver resolvido o psd pode usar autovalores entre 0 e 1. Bastava achar uma ref que diz que núcleo gaussiano é psd}
Daqui para frente é interessante ordenar os autovalores de $P=D^{-1}W$ de modo que
$\lambda_0=1 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}\geq -1.$ O teorema a seguir é baseado numa aula de Yuan Yao de 2011 \cite{Yao2011}.
\begin{comment}
permite escrever $P^t(x,y)=\sum \lambda_j^tv_j(x)e_j(y),$ onde \emph{x} e \emph{y} representam dados de entrada, $\lambda$ e \emph{v} são os autovalores e autovetores a direita da matriz de Markov acima citada e \emph{e} são autovetores à esquerda. O parâmetro escolhido para o tempo no processo estocástico de Markov é a letra \emph{t}.
Com algumas substituições podemos reescrever a distância de difusão entre \emph{x} e \emph{z} como
\begin{equation}
D_t(x,z)=\sqrt{\sum_{j=2}^{n} \lambda_j^{2t}(v_j(x)-v_j(z))^2}.
\end{equation}
\todo{demonstrar esta fórmula}
% Eu AINDA NÃO consegui chegar nesta conta abaixo
Com algumas substituições podemos reescrever a distância de difusão entre $X_i$ e $X_j$ como
\end{comment}
%
\begin{teo}\label{distespectral}
\begin{em}
Sejam $\textbf{v}_k$ autovetores à direita de $P$ associados a $\lambda_k.$ A distância de difusão entre $X^i$ e $X^j$ para cada $t$ fixo pode ser calculada como
%\begin{equation}\label{dist2}
\beas
D_t(X^i,X^j) & = &(\mbox{tr}\, (D))^{\frac{1}{2}} \left(\sum_{k=1}^{n-1} \left(\lambda_k^{t}v_k(i)-\lambda_k^{t}v_k(j)\right)^2\right)^{1/2}
\\
\lefteqn{=(\mbox{tr}\, (D))^{\frac{1}{2}} \left(\sum_{k=1}^{n-1} \lambda_k^{2t}(v_k(i)-v_k(j))^2\right)^{1/2} \ .}
\eeas
\end{em}
\end{teo}
%
\noindent\begin{demo}
Partindo da definição \ref{distdiff}, tem-se que
%$\sigma_r=(\mbox{tr}\, D)^{\frac{1}{2}} d_r$,
$\sigma_r=(\mbox{tr}\, D)^{-1} d_r$,
e utilizando a decomposição espectral do teorema \ref{despectral} obtemos que
%
\begin{equation*}
D_{t}^2(X^i,X^j)=\sum_{X^r \in E}\frac{(p^{t}_{ir}-p^{t}_{jr})^2}{\sigma_r}=
\mbox{tr}\,( D)\, \sum_{r=0}^{n-1}\frac{1}{d_r}\left(\sum_{k=0}^{n-1}\lambda_k^t v_k(i)u_k(r) - \sum_{k=0}^{n-1}\lambda_k^t v_k(j)u_k(r)\right)^2\ .
\end{equation*}
%
Juntando os somatórios dentro do quadrado e colocando os fatores repetidos em evidência,
%
\begin{equation*}
D_{t}^2(X^i,X^j)= \mbox{tr}\,( D)\, \sum_{r=0}^{n-1}\frac{1}{d_r}\left(\sum_{k=0}^{n-1}\lambda_k^t(v_k(i)-v_k(j))u_k(r)\right)^2\ .
\end{equation*}
%
Podemos reescrever o quadrado do somat\'orio como um produto de somat\'orios com \'{\i}ndices $k$ e $k'$,
\begin{equation*}
D_{t}^2(X^i,X^j)= \mbox{tr}\, (D)\,
\sum_{r=0}^{n-1}\frac{1}{d_r}\left(\sum_{k=0}^{n-1}\lambda_k^t(v_k(i)-v_k(j))u_k(r)\sum_{k'=0}^{n-1}\lambda_{k'}^t(v_{k'}(i)-v_{k'}(j))u_{k'}(r)\right)\ ,
\end{equation*}
%
e trocando a ordem do somat\'orios, obtemos
%
\begin{equation*}
D_{t}^2(X^i,X^j)= \mbox{tr}\,( D)\,
\left(\sum_{k=0}^{n-1}\sum_{k'=0}^{n-1}(\lambda_k^t(v_k(i)-v_k(j)))(\lambda_{k'}^t(v_{k'}(i)-v_{k'}(j)))\sum_{r=0}^{n-1}\frac{1}{d_r}u_k(r)u_{k'}(r)\right)\ .
\end{equation*}
%
Logo, usando a equa\cao\ \ref{5fato},
%\todo{Esta errada esta última frase, falta corrigir}
%Como $k = k'$ o último somatório dá um e podemos reescrever o que restou usando apenas um índice
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{justificar esta última frase} %?????????????????????????????? PQ DÁ UM???????????????????????
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation*}
D_{t}(X^i,X^j)=(\mbox{tr}\,( D))^{\frac{1}{2}} \left(\sum_{k=0}^{n-1}\lambda_k^{2t}(v_k(i)-v_k(j))^2\right)^{1/2} \ .
\end{equation*}
%
Como ao maior autovalor $\lambda_0 =1$ de $P$ corresponde o autovetor constante (ver observação após o teorema \ref{equiv}) vemos que a
primeira parcela no somatório anterior será nula, portanto podemos tirar o índice $k=0$ do somatório.
Finalmente a distância de difusão entre os dados $X^i$ e $X^j$ para $t$ fixo pode ser escrita como
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Se eu começar do $\lambda_0$ conforme sugeri acima, o somatório começaria do 1 e não do 2 e acho que ficaria mais coerente com a def $5.3$ de diff maps que começa com $\lambda_1$ e não $ \lambda_2. $ }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\bea
\label{dist2}
D_t(X^i,X^j)& = & (\mbox{tr}\, (D))^{\frac{1}{2}}\left(\sum_{k=1}^{n-1} \lambda_k^{2t}(v_k(i)-v_k(j))^2\right)^{1/2}.
\eea
\end{demo}\\ % FIM DA DEMONSTRAÇÃO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent \textbf{Observação.} Utilizando a equação (\ref{dist2}) e aplicando a definição de norma euclidiana às imagens de $X^i$ e $X^j$ pela aplicação de difusão (ver definição \ref{defdiff}) podemos ver que
\bea
\label{dist3}
D_t(X^i,X^j) & = & (\mbox{tr}\, (D))^{\frac{1}{2}} \left(\sum_{k=1}^{n-1} \lambda_k^{2t}(v_k(i)-v_k(j))^2\right)^{1/2} \nonumber
\\
\lefteqn{=\, (\mbox{tr}\, (D))^{\frac{1}{2}} \parallel\diff_t(X^i)-\diff_t(X^j)\parallel\ .}
\eea
%
Como os autovalores, em módulo, estão entre zero e 1, os valores crescentes de \emph{t} no processo estocástico permitirão considerarmos
poucas componentes da aplicação de difusão para análise dos dados. De fato, para $t$ suficientemente grande, teremos muitos $(\lambda_k)^t$ insignificantes fazendo com que
%as últimas %???????????????????????????????????????
% Mas quem disse que as últimas estão próximas de zero???? Elas podem estar próximas de -1!!!!
parcelas de $\parallel\diff_t(X^i)-\diff_t(X^j)\parallel$ que contribuem muito pouco para a distância entre $X^i$ e $X^j$ sejam desprezadas. Com isso, para $t$ grande, é possível considerar apenas algumas componentes da aplicação de difusão.
Em alguns casos a representação das {\em features} em duas ou três dimensões já é o suficiente para um bom resultado. Mas é claro que isso é
profundamente dependente da compreens\~ao do fen\^omeno que gerou os dados. Se os \emph{n} dados forem ``gordos'' dentro do espaço euclidiano de alta dimens\~ao
onde eles moram então
não haverá como reduzir a dimensionalidade, e duas ou três dimensões não serão suficientes para uma representa\cao\ sem perdas.
%%%%%Criei este parágrafo para resolver o problema acima
Se por acaso tivermos a hipótese adicional de $W$ ser \emph{positiva semi definida} então os autovalores de $P$ (veja Teorema \ref{zero_um}) estarão entre zero e um. Neste caso,
chamando de \emph{q(t)} a quantidade destas componentes escolhidas em função do parâmetro \emph{t}
podemos reescrever a igualdade (\ref{dist3}) de maneira aproximada utilizando menos parcelas no somatório. Assim,
%
\begin{equation}\label{dist4}
D_t(X^i,X^j)\, \cong\, (\mbox{tr}\, (D))^{\frac{1}{2}} \left(\sum_{k=1}^{q(t)} \lambda_k^{2t}(v_k(i)-v_k(j))^2\right)^{1/2}\, \cong\, (\mbox{tr}\, (D))^{\frac{1}{2}} \parallel\diff_t(X^i)-\diff_t(X^j)\parallel,
\end{equation}
%Com esta definição vemos facilmente que
\begin{comment}
\begin{equation}
D_t(x,z)\cong \sqrt{\sum_{j=1}^{q(t)} \lambda_j^{2t}(v_j(x)-v_j(z))^2}=\parallel\phi_t(x)-\phi_t(z)\parallel,
\end{equation}
\end{comment}
onde consideramos apenas as $q(t)$ primeiras componentes da aplicação de difusão, ou seja,
%
\begin{equation}\label{diff}
\diff_t(X^i) \cong \left(
\begin{array}{c}
\lambda_1^t v_1(i) \\
\lambda_2^t v_2(i) \\
\vdots \\
\lambda_{q(t)}^t v_{q(t)}(i) \\
\end{array}
\right)\ .
\end{equation}
%com $q(t)< n$ \cite{lafon2006diffusion}.
Portanto a distância de difusão entre os dados $X^i$ e $X^j$ é praticamente a mesma que a distância euclidiana entre as imagens no espaço $\re^{q(t)}$ que,
em muitas situações práticas, tem dimensão $q(t)\ll n$ \cite{lafon2006diffusion}.
Observa-se ainda que, conforme o par\^ametro de escala cresce, as caracter\'{\i}sticas percebidas dos dados, isto \'e, suas imagens pela aplica\cao\
de difus\~ao, tendem a se confundir uma vez que ${\cal D}_t(X^i) \rightarrow 0$, quando $t \rightarrow +\infty$, para todo o dado.
O quadro a seguir apresenta um pseudo código para o algoritmo das aplicações de difusão.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%% CAIXA com o DIFF MAPS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\fbox{\fbox{\parbox{14cm}{{\bf Entrada:} conjunto de dados $X^i, i=1, \ldots, n$ de dimensão alta em $\re^d.$ \\
\begin{itemize}
\item Construir um grafo onde os dados de entrada $X^i$ são os vértices, escolher um peso para as arestas em
função do núcleo adotado e criar a matriz $W_{ij}=K(X^i,X^j).$ \\
\item Calcular a matriz de difusão normalizando as linhas da matriz anterior $P=D^{-1}W.$ \\
\item Calcular os autovalores e autovetores desta matriz \emph{P}.\\
\item A imersão \'e dada por
\begin{equation*}
X^i \longrightarrow Y^i = (\lambda_1^t v_1(i),...,\lambda_k^t v_k(i)), \ \ Y^i \in \re^k,
\end{equation*}
onde $v_1(i)$ é a \emph{i}-ésima componente do autovetor não constante associado ao maior autovalor, $\lambda_1,$ abaixo de $\lambda_0=1.$
O autovetor \textbf{$v_2$} é o segundo maior nestas condições e assim sucessivamente.
\end{itemize}
{\bf Saída:} conjunto de dados $Y^i, i=1, \ldots, n$ de dimensão mais baixa em $\re^k.$
}}}
\end{center}
Podemos dizer que os $\textbf{v}_j$ são autovetores
da matriz de Markov $P^t=(D^{-1}W)^t,$ onde $t$ é o parâmetro de escala que dá o tempo de Markov do sistema estocástico.
(Lembre-se de que para o método das autofunções do laplaciano calculamos autovetores de $D^{-1}L=D^{-1}(D-W)=I-D^{-1}W= I - P$ que
são os mesmos deste método, apenas os autovalores correspondentes são uma translação dos atuais.)
%Mergulhar os dados no espaço de difusão de dimensão inferior \emph{k} usando os \emph{k} maiores autovalores com seus correspondentes autovetores.
Assim, quando $t=0$, a aplica\cao\ de difus\~ao e o m\'etodo das autofun\coes\ do laplaciano coincidem. Além disso, ao optarmos por utilizar a renormalização dada na equação (\ref{renormal}) teremos que fazer também $\alpha=0$ para obter esta coincidência.
% Resolvi comentar pq não entendo isso muito bem
%A distância de difusão entre dois vértices do grafo tem a vantagem de ser robusta à perturbação de ruídos nos dados. Isso se dá devido ao fato de que esta distância é calculada como uma soma sobre todos os caminhos ligando os dois vértices. Esta soma tem um efeito suavizante sobre pequenas perturbações no conjunto de dados ~\cite{lafon2004diffusion}.
\begin{comment}
Considere a imagem de $X_i$ por uma aplicação como sendo $$Y_i=\left(
\begin{array}{c}
p_t(X_i,X_1) \\
p_t(X_i,X_2) \\
\vdots \\
p_t(X_i,X_n) \\
\end{array}
\right)$$
que é o vetor formado pela \emph{i-ésima} linha da matriz de difusão.
Neste caso note que $\parallel Y_i-Y_j\|_E^2=D_t(X_i,X_j)^2.$
Até agora não reduzimos a dimensão!
Espera-se com a \emph{diffusion maps} que menos coordenadas sejam necessárias para representar os dados no novo espaço. Mas quais dimensões podem ser dispensadas?
Tome a matriz de difusão normalizada: $P=D^{-1}W$ , onde \emph{D} é a matriz diagonal consistindo da soma das linhas de \emph{W}. Devido a decomposição espectral da matriz de difusão \emph{P}, podemos reescrever os em $Y_i$ termos de autovalores e vetores de \emph{P} como:$Y_i^{'}=\left(
\begin{array}{c}
\lambda_1^t\Psi_1(i) \\
\lambda_2^t\Psi_2(i) \\
\vdots\\
\lambda_n^t\Psi_n(i)\\
\end{array}
\right),$
onde $\Psi_1(i)$ indica o \emph{i- ésimo} elemento do primeiro autovetor de \emph{P}.
Com a definição de $D_t(x,y)$ e a decomposição espectral de P mostra-se que a distância
euclidiana entre $Y_i^{'}$ e $Y_j^{'}$ é novamente a distância de difusão.
O conjunto dos autovetores ortogonais a esquerda de P forma uma base para o espaço de difusão
e os autovalores associados indicam a importância de cada dimensão. A redução é obtida retendo as m
dimensões associadas com os autovetores dominantes, que assegura que $\parallel Y^{'}_i-Y^{'}_j\parallel $ melhor aproxima a distância de difusão $D_t(X_i,X_j) $ . Logo a aplicação que melhor preserva a geometria intrínseca dos dados é aquela dada por $Y_i^{'}$ .
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%% FIM DO COMENTÁRIO ACIMA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{comment} % Tirei os exemplos velhos todos daqui para baixo
\section{Experimentos}\label{exdiff}
% Em 02/01/2014%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Diferentemente do capítulo anterior aqui temos mais possibilidades de variação de
parâmetros de modo que os resultados são mais ricos e passíveis de novas interpretações. Como vimos o método das
autofunções do laplaciano coincide com o método das aplicações de difusão se considerarmos o parâmetro $\alpha = 0$
da renormalização do núcleo gaussiano (ver equação (\ref{renormal})) e, $t = 0,$ para o parâmetro de Markov. Por isso o
tema considerado no
capítulo anterior
pode ser interpretado como
um caso particular do tema do presente capítulo. Assim como lá, fixamos o parâmetro $\varepsilon$ do núcleo
gaussiano como $\varepsilon = 0,1r^2$, $r^2$ e $10r^2,$ onde $r$ é o di\^ametro do conjunto dos dados de entrada, mas agora podemos
fazer variações no parâmetro $t$ do processo de Markov. Fixamos o parâmetro $\alpha = 1$ para todos os exemplos, ou seja,
usamos a normalização que conduz ao operador de Laplace-Beltrami, pois queremos atingir a geometria e não a densidade dos dados.
\subsubsection*{\textbf{Hélice}}
Com a intenção de analisar o comportamento do mapa de difusão para dados cuja estrutura geométrica intrínseca é conhecida aplicamos este método a um conjunto de pontos
formando uma hélice no espaço euclidiano tridimensional.
De início consideramos $189$ pontos em $\re^3$ formando uma variedade unidimensional que se assemelha a um trecho de uma mola, exatamente como fizemos na seção \ref{sec4lap}.
Depois da aplicação estes $189$ pontos s\~ao inclu\'{\i}dos em $\re^{188}$ e, finalmente, reduzimos a dimensão do $\re^{188}$ para o $\re^3$ ou $\re$.
%\todo{A referência às tabelas tinha dado certo e agora só sai interrogações. PQ?}
A Tabela ~\ref{tabeladiff1} a seguir apresenta os diferentes formatos da imagem da hélice após a aplicação
do método para $\varepsilon=0,1r^2,$ onde $r=353,442$ é o diâmetro do conjunto de entrada, ou seja, a maior distância entre os dados, e $\alpha=1.$ A coluna da esquerda apresenta as faixas numéricas de variação para o parâmetro $t$ do processo de Markov e a coluna
da direita apresenta o tipo de formato encontrado. Ao usar o símbolo $3D$ queremos dizer que a figura, apesar de
ter dimensionalidade intrínseca um, não consegue ser globalmente imersa num espaço menor que o espaço tridimensional.
Analogamente usamos $2D$ para bidimensional, $1D$ para unidimensional e $0D$ para dimensão nula. Os termos
entre aspas se referem apenas a uma tentativa de descrição do aspecto geral da curva e não a uma expressão matemática.
As linhas em branco da tabela se referem a trechos da variação de $t$ onde não foi possível descrever em palavras usuais o tipo de figura.
Conforme o $t$ cresce as escalas dos eixos das imagens vão se tornando extremamente pequenas. A partir de $ t = 3191$ a hélice será sempre transformada num ponto.
%
\begin{table}[!htpb]
\begin{center}
\caption{Descrição simplificada das imagens pela aplicação de difusão para o exemplo da hélice. Foram utilizados os parâmetros $\varepsilon=0,1r^2$ com $r=353,442$ e $\alpha=1$ na construção da matriz peso das arestas.}
\begin{tabular}{|l||c|}
\hline
%\multicolumn{2}{|c|}{\textbf{$\varepsilon = 0,1r$ e $\alpha = 1$}}\\
\hline
t (Markov) & Tipo \\
\hline\hline
0 - 370& 3D - ``pedaço de hélice'' \\
\hline
371 - 391& \\
\hline
392 - 730& 2D - ``parábola'' \\
\hline
731 - 771& \\
\hline
772 - 3019& 1D - reta \\
\hline
3020 - 3190& \\
\hline
3191- $+\infty$ & 0D - ponto\\
\hline
\end{tabular}% A ref só funcionou com este espaço
\label{tabeladiff1}
\end{center}
\end{table}
A Figura \ref{helc10T300etc} mostra os quatro tipos de formatos geométricos citados na Tabela \ref{tabeladiff1} %da página \pageref{tab1}
para quatro valores numéricos escolhidos do parâmetro de Markov $t$ nas faixas correspondentes.
Para a redução de dimensionalidade de $\re^{189}$ para $\re^3$ acontecer com $\varepsilon=0,1r^2$
e $\alpha = 1$ foram utilizados apenas três componentes da função $\diff_t$ correspondentes aos autovalores $\lambda_1=0,7923$ e $\lambda_2=0,3819$
e $\lambda_3 = 0,1499.$
%
\begin{figure} % Figura feita com ludiplota(TX19,10,t,1,1)
%sendo t=300 em (a); t=400 em (b);t=800 em (c); t=3200 em (d)
\begin{center}
\hspace{-0,4cm}
\subfigure[hel10t300][ $~t = 300$ ]{\includegraphics[scale=0.22]{helc10T300.png}}
\subfigure[hel10t400][ $~t = 400$ ]{\includegraphics[scale=0.22]{helc10T400.png}}
\\ \hspace{-0,4cm}
\subfigure[hel10t800][$~t = 800$ ]{\includegraphics[scale=0.22]{helc10T800.png}}
\subfigure[hel10t3200][$~t = 3200$ ]{\includegraphics[scale=0.22]{helc10T3200.png}}
\caption[Aplicação de difusão - $\varepsilon = 0,1r^2$ - hélice]{Imagens da hélice em $\re^3$ pela aplicação de difusão com $\varepsilon=0,1r^2,$ $\alpha=1$ e parâmetro de Markov (a) $t = 300,$ (b) $t = 400,$ (c) $t = 800$ e (d) $t = 3200.$}
\label{helc10T300etc}
\end{center}
\end{figure}
\begin{comment}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Vemos que as imagens %neste caso
são parecidas com parábolas que vão se tornando cada vez mais `esticadas' %(a derivada segunda em módulo vai tentendo a zero)
%\draftnote{ver se são parábolas mesmo com a ajuda de mínimos quadrados}
de modo que, para um número de passos suficientemente grande no processo de Markov, mais se assemelham a segmentos de reta mantendo a estrutura unidimensional intrínseca da variedade. \\
A figura \ref{diffhelice}(a) mostra a hélice no espaço tridimensional junto com imagens que utilizam apenas
duas componentes da função $\phi_t$ correspondentes aos autovalores $\lambda_2=0.7681$ e $\lambda_3=0.4905.$
A hélice foi plotada em conjunto com estas imagens para termos uma ideia de quanto o método reduz as distâncias
originais. Em \ref{diffhelice}(b) é apresentada apenas a família de imagens de forma ampliada para
melhor podermos analisar os resultados. As cinco `parábolas' representam a variação de $t = 1$ até $ t = 5.$ Note que
para $t = 5$ a `parábola' em azul é quase um segmento de reta quando observada na mesma escala daquela correspondente a
$t = 1.$ Espera-se que quanto maior o número de passos \emph{t} mais a imagem dos $189$ pontos se assemelhe a um segmento
de reta, ou seja, mais perto de zero seja a relação entre a variação do \emph{y} e do \emph{x} no trecho de `parábola'
considerado. %, com um comprimento euclidiano cada vez menor centralizado na origem do sistema.
Observe na figura \ref{parabhel}(a) um quadro ampliado utilizando apenas a imagem para $t = 5.$ Note que a relação entre a
variação do \emph{y} e do \emph{x} no trecho de `parábola' considerado é bem menor para $t = 5$ do que para $t = 1$ que se encontra em \ref{parabhel}(b).\\
\begin{figure}
\centering
\subfigure[refespdiffhel][A hélice no $\re^3$ e sua imagem no plano \emph{xy} ]{\includegraphics[scale=0.4]{diff_helice.png}}
\subfigure[refespampliahel][Apenas as imagens no plano \emph{xy} de forma ampliada]{\includegraphics[scale=0.4]{diff_helice2D.png}}
\caption{(a) A figura apresenta uma hélice em $\re^3$ e uma família de imagens pelo mapa de difusão na escala original. Conforme o parâmetro \emph{t} cresce, mais as imagens vão se assemelhando a segmentos de reta. (b) Ampliamos as imagens da hélice no plano \emph{xy} para ver melhor o processo de retificação. Para $t=5$ utilizamos a cor azul. Nesta figura os dados não foram normalizados.}
\label{diffhelice} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
\begin{figure}
\centering
\subfigure[parabt5][A imagem da hélice em $\re^2$ pela aplicação de difusão para $t = 5$ ]{\includegraphics[scale=0.4]{parab_azulT5.png}}
\subfigure[parabt1][A imagem da hélice em $\re^2$ pela aplicação de difusão para $t = 1$ ]{\includegraphics[scale=0.4]{parab_azulT1.png}}
\caption{Imagens da hélice em $\re^2$ pela aplicação de difusão para $t = 5$ e para $t=1.$ Comparando (a) e (b) observe que a redução nas escalas ocorre de modo diferenciado para cada um dos dois eixos.}
\label{parabhel} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
Considerando ainda os dados correspondentes à hélice, a figura \ref{dihelice3d} mostra uma redução de dimensão de $\re^{189}$ para o $\re^3.$ Aqui utilizamos três componentes da função $\phi_t$ correspondentes aos autovalores $\lambda_2=0.7681,$ $\lambda_3=0.4905$ e $\lambda_4=0.3173.$ As cinco imagens desta figura representam a variação de $t = 1$ até $t = 5.$ Para os primeiros valores de $t$ a imagem parece ser um pequeno trecho de hélice, mas no decorrer do tempo as imagens parecem estar se retificando próximas à origem. Para $t = 5$ a imagem em azul é quase um segmento de reta quando observada na mesma escala daquela correspondente a $t = 1.$
Espera-se que quanto maior o tempo \emph{t} mais a imagem dos $189$ pontos se assemelhe a um segmento de reta, ou seja, mais perto de zero esteja a relação entre os valores máximos dos três eixos no trecho da imagem considerado. %, com um comprimento euclidiano cada vez menor centralizado na origem do sistema.
Observe na figura \ref{helT5T1}(a) um quadro ampliado utilizando apenas a imagem para $t = 5.$ Neste caso a relação entre os máximos dos eixos é bem menor que para o caso $t = 1$ que se encontra em \ref{helT5T1}(b).
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{helice3dT5.png}
\caption{Família de imagens em $\re^3$ da hélice pela aplicação de difusão.}
\label{dihelice3d} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\begin{figure}
\centering
\subfigure[hel3dt5][A imagem da hélice em $\re^3$ pela aplicação de difusão para $t = 5$ ]{\includegraphics[scale=0.4]{hel3dT5azul.png}}
\subfigure[hel3dt1][A imagem da hélice em $\re^3$ pela aplicação de difusão para $t = 1$ ]{\includegraphics[scale=0.4]{hel3dT1azul.png}}
\caption{Imagens da hélice em $\re^3$ pela aplicação de difusão para $t = 5$ e para $t=1.$ Comparando (a) e (b) observe que a redução nas escalas ocorre de modo diferenciado para cada um dos três eixos.}
\label{helT5T1} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
\end{comment}
Como a queda dos autovalores para este exemplo da hélice é muito brusca (veja a Figura \ref{authelice}), vemos
que duas ou três componentes da função $\diff_t$ já são suficientes para se ter uma boa informação sobre a geometria
intrínseca dos dados de entrada. É bom lembrar que no algoritmo da aplicação de difusão estamos desconsiderando
o maior autovalor que é $\lambda_0 = 1,$ pois o mesmo é associado ao autovetor constante gerando contribuição
nula no somatório da equação (\ref{dist2}).
%Este exemplo da hélice para dados não normalizados pode estar indicando que o método da aplicação de difusão em alguns casos consegue representar de forma linear um conjunto de dados não lineares de dimensão intrínseca um (uma variedade diferenciável de dimensão um).\\
\begin{figure} % Fiz esta figura descomentando embaixo em ludiepis.m e colocando for j=1:20
\begin{center}
\includegraphics[scale=0.5]{autovhelc10t3200.png}
\caption[Aplicação de difusão - autovalores - $\varepsilon = 0,1r^2$ - hélice]{Queda dos $20$ primeiros autovalores da matriz de Markov para o caso da hélice na aplicação de difusão com $\varepsilon=0,1r^2$ e $\alpha=1.$ A partir do $18º$ até o $189º$ autovalor todos são nulos com $4$ casas decimais.}
\label{authelice}
\end{center}
\end{figure}
A título ilustrativo a Figura \ref{LEDIFF} a seguir apresenta num mesmo gráfico a hélice original, seguida da imagem dos seus $189$ pontos pelas autofunções do laplaciano e finalmente a imagem pela aplicação de difusão para $\varepsilon = 0,1r^2$ e $t=800.$ Para este valor escolhido de $t$ o método conseguiu transformar a hélice
num segmento de reta captando assim a dimensão intrínseca da mesma. Seria poss\'{\i}vel reduzir a $\re$ e sem perdas.
%
\begin{figure}
\begin{center}
\includegraphics[scale=0.55]{LE_DIFF_c10T800.png}
\caption[Autofunções do laplaciano e difusão - hélice]{Hélice original dos exemplos anteriores seguida de sua imagem pelas autofunções do laplaciano e pelas aplicações de difusão com $\varepsilon=0,1r^2$ e $\alpha=1.$}
\label{LEDIFF}
\end{center}
\end{figure}
A Tabela ~\ref{tabeladiff2} a seguir apresenta os resultados para a mesma hélice com $\varepsilon=r^2.$ A partir de $ t = 413$ a hélice será
indistingu\'{\i}vel de um ponto. Comparando com a tabela anterior vemos que aumentando %a vizinhança entre os pontos do grafo
o valor de $\varepsilon$ as imagens chegam a poder ser imersas num espaço unidimensional para menores valores de $t$, diminuindo a granularidade da an\'alise
para casos intermedi\'arios.
%
\begin{table}[!htpb]
\begin{center}
\caption{Descrição das imagens da hélice pela aplicação de difusão para uma vizinhança maior que na tabela anterior, $\varepsilon=r^2.$ A renormalização foi conseguida com $\alpha=1.$ Neste caso as imagens se colapsaram num ponto para menores valores de $t.$ }
\begin{tabular}{|l||c|}
\hline
%\multicolumn{2}{|c|}{\textbf{$\varepsilon = r$ e $\alpha = 1$}}\\
\hline
t (Markov) & Tipo \\
\hline\hline
0 - 119& 3D - ``pedaço de senóide circular'' \\
\hline
120 - 126& \\
\hline
127 - 156& 2D - ``parábola'' \\
\hline
157 - 165& \\
\hline
166 - 390& 1D - reta \\
\hline
391 - 412& \\
\hline
413 - $+\infty$ & 0D - ponto\\
\hline
\end{tabular}
\label{tabeladiff2}
\end{center}
\end{table}
A Figura \ref{helc100T100etc} mostra os formatos geométricos citados para o caso de $\varepsilon = r^2.$ Os autovalores utilizados foram $\lambda_1=0,1652$
e $\lambda_2=0,01121$ e $\lambda_3 = 0,002792.$
\begin{figure}% Figura feita com ludiplota(TX19,100,t,1,1)
%sendo t=100 em (a); t=130 em (b);t=200 em (c); t=340 em (d)
\centering
\hspace{-0,55cm}
\subfigure[hel100t100][ $~t = 100$ ]{\includegraphics[scale=0.21]{helc100T100.png}}
\subfigure[hel100t130][ $~t = 130$ ]{\includegraphics[scale=0.21]{helc100T130.png}}
\\ \hspace{-0,55cm}
\subfigure[hel100t200][$~t = 200$ ]{\includegraphics[scale=0.21]{helc100T200.png}}
\subfigure[hel100t420][$~t = 420$ ]{\includegraphics[scale=0.21]{helc100T420.png}}
\caption[Aplicação de difusão - $\varepsilon = r^2$ - hélice]{Imagens da hélice em $\re^3$ pela aplicação de difusão com $\varepsilon= r^2,$ $\alpha=1$ e parâmetro de Markov (a) $t = 100,$ (b) $t = 130,$ (c) $t = 200$ e (d) $t = 420.$}
\label{helc100T100etc} % Para referenciar esta figura mais a frente
\end{figure}
A queda dos autovalores para $ \varepsilon = r^2$ é ainda mais brusca que a anterior (veja a figura \ref{authelc100}).
%
\begin{figure}% Fiz esta figura descomentando embaixo em ludiepis.m e colocando for j=1:20
\begin{center}
\includegraphics[scale=0.5]{authelc100.png}
\caption[Aplicação de difusão - autovalores - $\varepsilon = r^2$ - hélice]{Queda dos $20$ primeiros autovalores da matriz de Markov para o caso da hélice na aplicação de difusão com $\varepsilon=r^2$ e $\alpha=1.$ A partir do $9º$ até o $189º$ autovalor todos são nulos com $4$ casas decimais.}
\label{authelc100} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
Para fechar o quadro de comparações a Tabela ~\ref{tabeladiff3} a seguir apresenta os resultados para a mesma hélice com $\varepsilon = 10r^2.$ A partir de $ t = 183 $ a hélice será sempre transformada num ponto. Para este valor de $\varepsilon$ as imagens já começam a poder ser imersas num espaço unidimensional para valores de $t$ a partir de $92.$
%
\begin{table}[!htpb]
\begin{center}
\caption{As imagens da hélice pela aplicação de difusão são descritas a seguir. Desta vez os parâmetros utilizados foram $\varepsilon = 10r^2$ e $\alpha=1.$}
\begin{tabular}{|l||c|}
\hline
%\multicolumn{2}{|c|}{\textbf{$\varepsilon = 10r$ por cento e $\alpha = 1$}}\\
\hline
t (Markov) & Tipo \\
\hline\hline
0 - 85& 3D - ``hélice com 3 voltas'' \\
\hline
86 - 91& \\
\hline
92 - 172& 1D - ``reta'' \\
\hline
173 - 182& \\
\hline
183- & 0D - ponto\\
\hline
\end{tabular}
\label{tabeladiff3}
\end{center}
\end{table}
A Figura \ref{helc1000T80etc} mostra os formatos geométricos citados para o caso de $\varepsilon =10r^2.$ Os autovalores utilizados foram
$\lambda_1=0,01686$ e $\lambda_2=0,0002862$ e $\lambda_3 = 0,000263.$
\begin{figure}% Figura feita com ludiplota(TX19,1000,t,1,1)
%sendo t=80 em (a); t=100 em (b);t=200 em (c);
\centering
\subfigure[hel1000t80][ $~t = 80$ ]{\includegraphics[scale=0.35]{helc1000T80.png}}
\subfigure[hel1000t100][ $~t = 100$ ]{\includegraphics[scale=0.35]{helc1000T100.png}}
\subfigure[hel1000t200][$~t = 200$ ]{\includegraphics[scale=0.35]{helc1000T200.png}}
\caption[Aplicação de difusão - $\varepsilon = 10r^2$ - hélice]{Imagens da hélice em $\re^3$ pela aplicação de difusão com $\varepsilon=10r^2,$ $\alpha=1$ e parâmetro de Markov (a) $t = 80,$ (b) $t = 100$ e (c) $t = 200$ }
\label{helc1000T80etc} % Para referenciar esta figura mais a frente
\end{figure}
A queda dos autovalores para $ \varepsilon = 10r^2$ é apresentada na figura \ref{authelc1000}.
%
\begin{figure}
\begin{center}
\includegraphics[width=0.9\textwidth]{authelc1000.png}
\caption[Aplicação de difusão - autovalores - $ \varepsilon = 10r^2$ - hélice]{Queda dos $20$ primeiros autovalores da matriz de Markov para o caso da hélice na aplicação de difusão com $\varepsilon=10r^2$ e $\alpha=1.$ A partir do $6º$ até o $189º$ autovalor todos são nulos com $4$ casas decimais.}
\label{authelc1000}
\end{center}
\end{figure}
A seguir apresentamos a Tabela ~\ref{autov} com os dez primeiros autovalores da matriz de Markov para o parâmetro $\alpha=1,$ fixo e $\varepsilon=0,1r^2,$ $\varepsilon=r^2$ e $\varepsilon=10r^2,$ onde $r$ é a maior distância entre os dados originais da hélice.
\begin{table}[!htpb]
\begin{center}
\caption{Primeiros dez autovalores da matriz de Markov para $\alpha=1$ no exemplo da hélice.}
\begin{tabular}{|c||c||c|}
\hline
%\multicolumn{3}{|p{18em}|}{\textbf{Autovalores de Markov para $\alpha=1$ }}\\
\hline
$\varepsilon=0,1r^2$ & $\varepsilon=r^2$ & $\varepsilon=10r^2$ \\
\hline\hline
1,0000 & 1,0000 & 1,0000 \\ \hline
0,7923& 0,1652& 0,0169 \\ \hline
0,3819& 0,0112 & 0,0003\\ \hline
0,1499& 0,0028& 0,0003\\ \hline
0,0571& 0,0027& 0,0001\\ \hline
0,0308& 0,0007& 0,0000\\ \hline
0,0275 & 0,0003 & 0,0000 \\ \hline
0,0245& 0,0002& 0,0000\\ \hline
0,0149& 0,0000& 0,0000\\ \hline
0,0068& 0,0000& 0,0000\\ \hline
\end{tabular}
\label{autov}
\end{center}
\end{table}
%Ao comparar a aplicação do método para os dados normalizados percebemos uma semelhança com a ideia de que para $t$ grande a imagem se torne algo parecido com um segmento de reta. A figura \ref{dihel123D} mostra a hélice original junto com as imagens pela aplicação de difusão no $\re,$ $\re^2$ e $\re^3.$ Foi usado $t=2$ para que conseguíssemos visualizar a diferença de escala entre $t=1$ e $t=2.$ Para $t=5$ preferimos apresentar a figura \ref{dihenorsot5} onde vemos claramente que a hélice mais parece um segmento de reta. Note que neste caso os três eixos estão na ordem de $10^{-6}.$ Já para este pequeno valor de $t$ parece que a hélice está desenrolando como se fosse um barbante de ioiô.
%Também é interessante comparar com a figura \ref{LEhelnor} resultado da aplicação das autofunções do laplaciano à mesma hélice. A vantagem de usar a dinâmica do processo de Markov permite que as imagens possam, com o aumento do $t,$ apresentar novas informações que não são possíveis de se obter apenas com o método do capítulo anterior.
\begin{comment}
\begin{figure}
\begin{center}
\includegraphics[scale=0.7]{difhelnort2.png}
\caption{A hélice com suas imagens pela aplicação de difusão em $\re,\re^2$ e $\re^3,$ com os dados normalizados. Em verde está a imagem para $t=1$ e em azul a imagem para o último $t$. Variamos as imagens entre $t=1$ e $t=2$ para que a última imagem ficasse visível.}
\label{dihel123D} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[scale=0.7]{difhelnorsot5.png}
\caption{A imagem da hélice pela aplicação de difusão em $\re^3$ com dados normalizados. Para esta figura utilizamos $t=5.$}
\label{dihenorsot5} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
A figura \ref{autdihelnor} apresenta a queda dos autovalores da matriz de Markov para este caso dos dados normalizados. É interessante comparar com a figura \ref{authelice} onde os dados não foram normalizados.
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{autdifhelnor.png}
\caption{Queda dos autovalores da matriz de Markov para a hélice com dados normalizados na aplicação de difusão.}
\label{autdihelnor} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FIM HÉLICE E COMEÇO DA CURVA EM S
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\subsubsection*{\emph{curva em forma de S}}
\draftnote{ver se vou aumentar este nº de pontos para 2222, o problema é que o programa leva duas horas para rodar.}
Querendo fazer o mesmo que foi feito acima para alguma estrutura geométrica de dimensão intrínseca dois (uma variedade diferenciável de dimensão dois) resolvemos aplicar o mapa da
difusão para um conjunto de pontos que se assemelha a uma superfície em forma de \emph{S} conforme figura \ref{superfbi}. Esta figura se constitui de $11$ curvas unidimensionais em forma de $S$ cada uma com $202$ pontos de modo que em $\re^3$ pode ser vista como uma faixa bidimensional em forma de $S$ com uma certa profundidade. No entanto, para nossa aplicação, achamos suficiente considerar $32 \times 11 = 352$ pontos em $\re^3$ formando tal estrutura. Depois da aplicação estes $352$ pontos foram jogados para $\re^{352}$ e, finalmente, reduzimos a dimensão do $\re^{352}$ para o $\re^3.$ Analisamos primeiramente os dados sem normalização. Neste caso vimos que as imagens parecem formar uma estrutura de superfície regrada parecida com pequeno trecho de um parabolóide hiperbólico, ou seja, pequeno trecho de uma `sela' que vai se tornando cada vez mais `esticada' com o passar do tempo.
Para um tempo suficientemente grande estas `selas' mais se assemelham a pedaços de planos mantendo a estrutura bidimensional intrínseca da variedade original. Aqui utilizamos três componentes da função $\phi_t$ correspondentes aos autovalores $\lambda_2=0.2500,$ $\lambda_3=0.2096$ e $\lambda_4=0.0833.$ \\
\begin{figure}
\begin{center}
%\includegraphics[scale=0.4]{curvaSscat.png} % Caso use N = 352
\includegraphics[scale=0.4]{S2222.png} % Caso use N = 2222
\caption{Nuvem de pontos em forma de \emph{S} em $\re^3$}
\label{superfbi} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
Na figura \ref{sela15} é apresentada uma imagem da `superfície' \emph{S} pelo mapa de difusão em $\re^3.$
%Nesta figura a quinta pequena `sela' está quase imperceptível representada pela cor verde próximo à origem.
Para visualizar melhor as mudanças com a variação do $t,$ a figura \ref{selarosazul}(a) apresenta as `selas' para $t = 1$ até $t = 4$ em cor rosa e destaca aquela correspondente a $t = 5$ em azul. Como não é possível visualizar a cor azul nesta escala a figura \ref{selarosazul}(b) mostra a figura de forma ampliada dando destaque à `sela' azul.
\draftnote{ver se vou aumentar este nº de pontos para 2222, o problema é que o programa leva duas horas para rodar.}
Espera-se que quanto maior o tempo \emph{t} mais a imagem dos $352$ pontos se assemelhe a um pedaço de plano de área cada vez menor centralizado próximo à origem do sistema.\\
\todo{conferir se as figuras correspondem ao $N=352$ ou $N=2222.$}
\begin{figure}
\begin{center}
%\includegraphics[scale=0.5]{selaT1a5.png} % Caso use N= 352
%\includegraphics[scale=0.5]{diSamplia.png}
\includegraphics[scale=0.5]{selaS2222.png} % Caso use N= 2222
\caption{Imagens da superfície em forma de \emph{S} pela aplicação de difusão em $\re^3$ para dados sem normalização.}
\label{sela15} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\begin{figure}
\centering
\subfigure[selarosa][As imagens em $\re^3$ da `superfície' em forma de $S$ para $t = 1$ até $t = 5$ ]{\includegraphics[scale=0.4]{selatrosa.png}}
\subfigure[selazul][A `sela' azul de forma ampliada]{\includegraphics[scale=0.4]{selatazul.png}}
\caption{(a) A figura apresenta uma família de imagens pelo mapa de difusão em $\re^3$ para a `superfície' em forma de $S$ para $t = 1$ até $t = 5.$ As imagens parecem `selas' que diminuem conforme o parâmetro \emph{t} cresce. (b) Ampliamos a figura em (a) dando destaque à `sela' azul correspondente ao maior \emph{t} considerado, $t=5.$ Com o aumento
do parâmetro \emph{t} mais as imagens vão se assemelhando a pedaços de planos.}
\label{selarosazul} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
A figura \ref{autS} mostra a queda dos autovalores para o exemplo da superfície em forma de \emph{S} com os dados sem normalização. Novamente podemos ver que duas ou três componentes das imagens já são suficientes para se ter uma boa informação sobre a geometria intrínseca dos dados de entrada já que os autovalores decrescem mais rapidamente até do que no caso da hélice, compare com a figura \ref{authelice}. \\
A tabela $5.1$ %\ref{tabelaut}
mostra os dez primeiros e os dez últimos autovalores da matriz de Markov para o caso da superfície em forma de $S$ com 352 pontos sem normalização.
\todo{ver se vou usar 352 pts mesmo ou 2222}
\end{comment}
\begin{comment} % Ele está confundindo o begin comment com o tabular
\begin{table}[!htb] \label{tabelaut}
\begin{center}
\caption{Os dez primeiros e os últimos autovalores da matriz de Markov para o caso da superfície em forma de $S$ com 352 pontos.}
%\begin{tabular}[r]{c|c|c|}
\begin{tabular} {||r|c|c|c||}
\hline % Este comando coloca uma linha aqui na horizontal
& primeiros & últimos \\ \hline % Este comando coloca uma linha aqui na horizontal
1 & 1,0000 & -0,0078 \\
2 & 0,2500 & -0,0078 \\
3 & 0,2096 & -0,0079 \\
4 & 0,0833 & -0,0079 \\
5 & 0,0737 & -0,0079 \\
6 & 0,0588 & -0,0079 \\
7 & 0,0432 & -0,0080 \\
8 & 0,0323 & -0,0080 \\
9 & 0,0275 & -0,0080 \\
10 & 0,0267 & -0,0080 \\ \hline % Este comando coloca uma linha aqui na horizontal
\end{tabular}
\end{center}
\end{table}
Este exemplo também pode estar indicando que o método da aplicação de difusão consegue representar um conjunto de dados não lineares de forma linear numa escala bem reduzida. %\draftnote{Falta aumentar o tamanho dos marcadores nos autovalores da curva S}\\
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{autS.png} % Caso use N= 352
%\includegraphics[scale=0.4]{autS2222.png} % Caso use N= 2222
\caption{Queda dos autovalores para o caso da superfície em forma de \emph{S} com dados sem normalização.}
\label{autS} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%% FALO OU NÃO DA NORMAÇIZAÇÃO ??????????????????%%%%%%%%%%%%%%%%%%%%%
% Ver se coloco estas coisas para a superf S
Depois desta análise aplicamos o método para os dados normalizados a título de comparação.
A figura \ref{diSnor} mostra a superfície original junto com as imagens pela aplicação de difusão em $\re,$ $\re^2$ e $\re^3.$ Foi utilizado $t=5$ como último valor do tempo.
Podemos visualizar que a superfície formada no espaço tridimensional para $t=1$ se assemelha a uma espécie de `cuia' com base em forma de $S.$ Para o valor de $t=3$ plotamos o gráfico separadamente na figura \ref{diSt3}. Neste caso os três eixos estão na ordem de $10^{-3}.$ Já para este pequeno valor de $t$ parece que a `cuia' está `esticada' na direção do eixo $x.$ Para $t=5$ a imagem parece um segmento de reta paralelo ao eixo $x$ (Ver figura \ref{diSt5}).
\begin{figure}
\begin{center}
\includegraphics[scale=0.7]{diffS123dnor.png} % Caso use N= 352
%\includegraphics[scale=0.4]{.png} % Caso use N= 2222
\caption{Superfície em forma de \emph{S} junto com suas imagens pela aplicação de difusão em $\re,$ $\re^2$ e $\re^3.$ Neste caso os dados foram normalizados.}
\label{diSnor} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[scale=0.6]{diSsot3n352.png} % Caso use N= 352
%\includegraphics[scale=0.4]{.png} % Caso use N= 2222
\caption{Imagem em $\re^3$ da superfície em forma de \emph{S} pela aplicação de difusão para $t=3.$ Neste caso os dados foram normalizados.}
\label{diSt3} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[scale=0.6]{diSsot5n352.png} % Caso use N= 352
%\includegraphics[scale=0.4]{.png} % Caso use N= 2222
\caption{Imagem em $\re^3$ da superfície em forma de \emph{S} pela aplicação de difusão para $t=5.$ Neste caso os dados foram normalizados.}
\label{diSt5} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
A figura \ref{autSnor} apresenta a queda dos autovalores da matriz de Markov para este caso dos dados normalizados. É interessante comparar com a figura \ref{autS} onde os dados não foram normalizados.
\begin{figure}
\begin{center}
\includegraphics[scale=0.4]{autShoje.png}
\caption{Queda dos autovalores da matriz de Markov para a superfície em forma de $S$ com dados normalizados na aplicação de difusão.}
\label{autSnor} % Para referenciar esta figura mais a frente caso sj necessário
\end{center}
\end{figure}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FIM CURVA S
\subsection*{Com imagens (fotografias digitais)}
%Pela figura \ref{pcafoto} a seguir vemos que 9 triângulos estão rosa indicando um reconhecimento de todas as 9 fotos de determinada pessoa. Os 5 círculos rosa indicam que o algoritmo confundiu uma segunda pessoa com esta primeira e portanto acertou apenas os 4 círculos verdes. Finalmente a coincidência de 5 quadrados amarelos indica que ele acertou ao reconhecer 5 fotos de uma terceira pessoa, mas confundiu 4 fotos desta com a segunda pessoa.\\
%São apresentadas uma foto de cada pessoa do banco de imagens para que se possa ter uma ideia da semelhança existente entre as mesmas.\\
%%%%%%%%%%%%%%%%%555
Assim como foi feito no terceiro capítulo aplicamos o algoritmo de difusão a um problema de reconhecimento envolvendo clusteriza\cao.
Consideremos um conjunto de 27 fotos de
rostos de um banco de imagens de 3 pessoas, onde cada uma delas tem 9 fotos diferentes. Essas 27 fotos do
banco foram ordenadas de 9 em 9 fotos de acordo com a pessoa para que ao final do algoritmo fosse possível avaliar como foi feita a clusterização.
No nosso caso consideramos $q(t) = 3$ componentes no espaço da aplicação de difusão. Com isso reduzimos ainda mais a dimensão desta vez do $\re^{26}$ para o $\re^3$ de modo a podermos conferir visualmente num gráfico a forma como o algoritmo reagrupou automaticamente as imagens.
%Esta redução já foi o suficiente para que o algoritmo conseguisse agrupá-las em 3 {\em clusters} que correspondem, com alguma faixa de erro, a cada uma das 3 pessoas. Aplicamos o algoritmo do \emph{k-means} nos resultados do mapa de difusão para visualizarmos melhor os três diferentes grupos.\\
Com a ajuda do algoritmo \emph{k-means} aplicado nestas imagens (no espaço de características) separamos melhor os três clusters que correspondem, com alguma faixa de erro, a cada uma das três pessoas.
\begin{comment}
A matriz dos pesos \emph{W} foi construída a partir do banco de dados que chamamos de \emph{X}: cada
$X_i \in X$ é uma matriz $p \times 1$ que representa uma das 27 fotos. Utilizamos para isso o núcleo gaussiando da equação do calor calculado como
%
\begin{equation}\label{peso}
W_{ij}=exp(-\parallel X_i - X_j \parallel^2/\varepsilon),
\end{equation}
onde o denominador $\varepsilon$ foi escolhido como sendo o número de linhas da matriz dos dados. Isto corresponderia à dimensão do espaço que contém os dados do problema, na teoria acima seria $\varepsilon= p = 10000,$
pois estamos trabalhando com fotos de $100 \times 100$ pixels.\\
\end{comment}
A matriz dos pesos \emph{W} foi construída a partir do banco das $27$ fotos onde cada foto é representada por um vetor $10000 \times 1,$ pois estamos trabalhando
com fotos de $100 \times 100$ píxeis. As fotos das pessoas envolvidas já foram apresentadas no capítulo 3 (figura \ref{fotos}).
Utilizamos o núcleo gaussiando da equação do calor com normalização a partir do parâmetro $\alpha = 1$ e onde o denominador $\varepsilon$ foi escolhido como sendo $\varepsilon=r^2,$ com $r= 2153,6.$ % Chutei este valor, não consigo mais reproduzir esta foto.
%\todo{Tentei com $\varepsilon=0,1r,$ com $\varepsilon=r$ e com $\varepsilon=10r.$ Variei $t=2, 20$ e $t=200.$ Não consegui achar estas figuras antigas, de antes da quali. Eu mudei tanto os programas que agora os resultados são outros.}
%Nas imagens a seguir consideramos $\varepsilon$ como
%\todo{Quero tirar este ex. Até agora o melhor que consegui foi acertar 8 de uma pessoa, 5 de outra e 2 da última com $c=465, T=1, \alpha=1.$ Qdo aumentei o T para 5, 10, 100 a situação piorou para 6,5 e 2 acertos. }
Na Figura~\ref{diffoto} são apresentados dois gráficos. O primeiro corresponde ao algoritmo aplicado no tempo $t=1$ e o outro para o tempo $t=20.$ A ideia é que variando-se o parâmetro \emph{t} pode-se encontrar a escala ótima para o agrupamento. %Estão sobrepostos os gráficos da aplicação de difusão e do \emph{k}-means.
O \emph{k-means} foi aplicado ao conjunto das imagens pelo mapa de difusão (no conjunto das características, $\re^3).$ As imagens de cada uma das pessoas foram distinguidas pelos pequenos círculos, quadrados e triângulos. Os clusters formados automaticamente pelo \emph{k}-means estão separados pelas cores amarela, verde e rosa.
% na figura \ref{fig:figura1} % Caso eu queira fazer referência a alguma figura
%\newpage % Ver se vai precisar, depende da posição das figuras
Para $t=1$, a Figura \ref{diffoto}(a) a seguir mostra $9$ círculos rosa indicando um reconhecimento de $100\%$ das 9 fotos de determinada pessoa. Os 4 triângulos rosa indicam que o algoritmo confundiu uma segunda pessoa com esta primeira e portanto acertou apenas os 5 triângulos amarelos. Finalmente a coincidência de 5 quadrados verdes indica que ele acertou ao reconhecer 5 fotos de uma terceira pessoa, mas confundiu 4 fotos desta com a segunda pessoa.
Para $t=20$ a situação teve uma melhora substancial. O algoritmo acertou as 9 fotos de uma pessoa (9 círculos amarelos), 5 de outra (5 triângulos rosa) e 8 de uma terceira pessoa (8 quadrados verdes) como pode ser visto pela Figura \ref{diffoto}(b).
%
\begin{figure}
\centering
\subfigure[refim1][$~t=1$]{\includegraphics[width=\textwidth]{t1b.png}}
\subfigure[refim2][$~t=20$]{\includegraphics[width=\textwidth]{di27_958b.png}}
\caption[Aplicação de difusão - fotos]{Nuvens dos dados de imagens (fotos de faces) agrupadas após aplicação do mapa de difusão. As imagens de cada pessoa foram distinguidas pelos círculos, quadrados e triângulos. Os clusters formados pelo \emph{k-means} estão separados pelas cores amarela, verde e rosa. Foi utilizado $\varepsilon=r^2$ onde $r=2153,6.$}
\label{diffoto}
\end{figure}
\begin{comment}
Para avaliar o resultado numericamente, construímos a matriz de confusão deste exemplo
onde cada linha indica uma pessoa e as colunas indicam cada um dos 3 agrupamentos. Espera-se que o maior
número possível de fotos da i-ésima pessoa encontre-se no i-ésimo cluster. Portanto na diagonal principal
vemos a quantidade de reconhecimentos corretos por pessoa. Fora desta diagonal encontram-se o número de fotos
classificadas erradamente da pessoa \emph{i} em clusters $j \neq i.$ Abaixo encontra-se a matriz de confusão e
uma taxa de acertos por pessoa. Para \emph{t=1} o algoritmo acertou 9 fotos da primeira pessoa portanto a taxa é 1,
já para a segunda e terceira ele reconheceu apenas 5 dentre 9 então a taxa foi de 0.5556.\\
Para \emph{t=1}:\\
%Matriz de confusão
\begin{equation*}
C = \left(
\begin{array}{c|ccc} % Este comando | coloca uma linha vertical entre as colunas marcadas
& cluster1 & cluster2 & cluster3 \\ \hline % Este comando coloca uma linha aqui na horizontal
pessoa1 & 9 & 0 & 0 \\
pessoa2 & 4 & 5 & 0 \\
pessoa3 & 0 & 4 & 5 \\
\end{array}
\right)
\end{equation*}
\begin{equation*}
Taxa =\left(
\begin{array}{ccc}
1.0000 & 0.5556 & 0.5556 \\
\end{array}
\right)
\end{equation*}
Para \emph{t=20}:\\
%Matriz de confusão
\begin{equation*}
C =\left(
\begin{array}{c|ccc} % Este comando | coloca uma linha vertical entre as colunas marcadas
& cluster1 & cluster2 & cluster3 \\ \hline % Este comando coloca uma linha aqui na horizontal
pessoa1 & 9 & 0 & 0 \\
pessoa2 & 4 & 5 & 0 \\
pessoa3 & 0 & 1 & 8 \\
\end{array}
\right)
\end{equation*}
\begin{equation*}
Taxa = \left(
\begin{array}{ccc}
1.0000 & 0.5556 & 0.8889 \\
\end{array}
\right)
\end{equation*}
Acreditamos que quanto maior o tempo melhor será o resultado. Para \emph{t=20} já houve uma melhora grande para a
terceira pessoa e não decaiu a taxa de acertos da segunda pessoa. Comparando com este mesmo exemplo que foi feito
no capítulo 3 com PCA vemos que o algoritmo da aplicação de difusão teve melhor desempenho neste caso. (Compare figuras \ref{pcafoto} com \ref{diffoto}.)\\
Outra observação sobre os gráficos é a escala. Note que para \emph{t=20} os eixos estão na ordem de $10^{-29}$
enquanto para \emph{t=1} a ordem é de $10^{-4}.$ Com o aumento do tempo o algoritmo da aplicação de difusão tende
a aglomerar as imagens em conjuntos cada vez menores pois a distância de difusão entre os dados de entrada diminuem
com o tempo e consequentemente as distâncias euclidianas das respectivas imagens também diminuem.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%COPIEI DO APENDICE1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Algoritmo da aplicação de difusão}
Entrada: conjunto de dados $X_i$ de dimensão alta $\re^p.$ \\
\begin{itemize}
\item Construir um grafo onde os dados de entrada $X_i$ são os vértices, escolher um peso para as arestas em função do núcleo adotado e criar a matriz $W_{ij}=k(X_i,X_j).$ \\
\item Calcular a matriz de difusão normalizando as linhas da matriz anterior $P=D^{-1}W.$ \\
\item Calcular os autovetores desta matriz \emph{P}.\\
O mergulho será dado por $ X_i \longrightarrow Y_i = (\lambda_1^t\overrightarrow{f_1}(i),...,\lambda_k^t\overrightarrow{f_k}(i)),$
$Y_i \in \re^k, $ onde $\overrightarrow{f_1}(i)$ é a \emph{i}-ésima componente do autovetor não constante associado ao maior autovalor $\lambda_1,$ abaixo de $\lambda_0=1$ do problema. O autovetor $\overrightarrow{f_2}$ é o segundo maior nestas condições e assim sucessivamente. Podemos dizer que os $\overrightarrow{f_j}$ são autovetores da matriz de Markov
$P^t=(D^{-1}W)^t,$ onde $t$ é o parâmetro de escala que dá o tempo de Markov do sistema estocástico.
(Lembre-se de que para o método das autofunções do laplaciano calculamos autovetores de $D^{-1}L=D^{-1}(D-W)=I-D^{-1}W= I - P$ que são os mesmos deste método, apenas os autovalores correspondentes são uma translação dos atuais.)
%Mergulhar os dados no espaço de difusão de dimensão inferior \emph{k} usando os \emph{k} maiores autovalores com seus correspondentes autovetores. \\
\end{itemize}
Saída: conjunto de dados $Y_i$ de dimensão mais baixa $\re^k.$
%\bibliographystyle{xiiiemc}
%\bibliography{biblio}
\end{comment}
%\todo{ver onde isso vai entrar
%Veremos que a aplicação de difusão só se diferencia das autofunções do laplaciano pelo fato de suavizar os autovetores
% multiplicando-os por potências de autovalores correspondentes. Ao considerarmos tais potências com expoente zero passamos a
% obter o caso particular das autofunções do laplaciano. Os autovalores considerados serão os anteriores transladados de uma
% unidade já que serão computados pela matriz $P = D^{-1}W$ (ver Teorema \ref{equiv}). Estas e outras pequenas alterações permitem
%uma riqueza de interpretação que será melhor explorada no próximo capítulo.}