[d9dc89]: LE_sem.tex  Maximize  Restore  History

Download this file

1214 lines (1106 with data), 65.1 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
\chapter{Autofunções do laplaciano}\label{autolap}
Um método recente para reduzir a dimensionalidade de dados, de forma não-linear, utiliza os autovetores
do laplaciano de um grafo com pesos definidos a partir das similaridades locais entre os dados \cite{belkin2003laplacian}.
Apresentamos essas ideias neste capítulo já que possui o mérito de ter unificado diversas outras abordagens recentes,
tendo desvendado e explorado conexões íntimas entre o discreto (grafo) e o contínuo (variedade). Na seção \ref{1consini}
discorremos mais sobre a metodologia. A seção \ref{sec2lap} emprega esse conjunto de ideias para reduzir a dimensionalidade à
dimensão um. A seção \ref{sec3lap} apresenta a redução a uma dimensão maior que um e finalmente um experimento elucidativo é
apresentado e discutido na seção \ref{sec4lap}. Nota-se que a exposição não é uma mera transcrição de outras referências, mas
tem por objetivo reunir e elucidar conceitos e demonstrações dispersos e pouco claros na literatura.
%
\section{Considerações iniciais}\label{1consini}
Dados \emph{n} pontos de $\re^d,$ $E=\{ X^1,X^2, \ldots X^n\}$, queremos achar $F=\{Y^1,Y^2,\ldots , Y^n\}$ (\emph{n}
pontos de $\re^k$) tal que cada $Y^j$ `represente' o correspondente $X^j,$ onde nos casos de interesse \emph{k} é
menor que a dimensão do espaço original \emph{d} (Queremos reduzir a dimensionalidade!) e, veremos, $k$ é também menor
que o número de dados \emph{n}. O processo deve ser realizado de tal forma a preservar propriedades locais e estruturas de interesse presentes nos dados.
Iremos construir uma matriz de afinidades, $W$, referente ao conjunto de dados ${E\subset \re^d.}$
Sejam $J=\{1,2,\dots,n\}$ um conjunto de índices e \emph{S} uma função que associa a cada índice de\emph{ J} um dado de $\re^d,$
%
\begin{equation*}
\left.
\begin{array}{c}
S: \\
\\
\end{array}
\right.
\left.
\begin{array}{ccl}
J & \rightarrow & E \subset \re^d \\
i & \mapsto & S(i) = X^i \\
\end{array}
\right. \ .
\end{equation*}
Defina a função produto, $S\times S,$ a partir de \emph{S} como
%
\begin{equation*}
\left.
\begin{array}{c}
S\times S: \\
\\
\end{array}
\right.
\left.
\begin{array}{ccl}% Este l é para alinhar a última coluna a esquerda
J\times J & \rightarrow & E\times E \subset \re^d \times \re^d \\
(i,j) & \mapsto & (S\times S)(i,j)=(X^i, X^j) \\
\end{array}
\right. \ .
\end{equation*}
Vamos considerar agora uma função $K$ que associa a cada par de dados um número real não negativo.
Este número representará a afinidade ou similaridade entre esses dados. Esta função pode ser chamada de {\em fun\cao\ afinidade, n\'ucleo ou peso} e será dada por
%
\begin{equation*}
\left.
\begin{array}{c}
K: \\
\\
\end{array}
\right.
\left.
\begin{array}{ccl}
E\times E & \rightarrow & \re \\
(X^i,X^j) & \mapsto & K(X^i,X^j) \\
\end{array}
\right. \ .
\end{equation*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Aqui eu apresentava o núcleo gaussiano, mas resolvi comentar. Queria escrever em outro lugar, mas até agora nada.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%
(Talvez coloque o exemplo gaussiano mais a frente.)
Usando o núcleo gaussiano como medida de similaridade local a função K poderá ser dada por:
K(X_i,X_j)= exp(-\frac{\parallel X_i-X_j \parallel ^2}{\epsilon})
OBS.: Falta falar sobre o \epsilon
%%%%%%%%%%%%%%%%%%%%%%%%%
\end{comment}
Com as informações acima podemos construir uma função composta, $W,$ que associa a cada par de índices um número real dado pela função \emph{K}:
%
\begin{equation*}
\left.
\begin{array}{c}
W: \\
\\
\end{array}
\right.
\left.
\begin{array}{ccl}
J\times J & \longrightarrow & \re \\
(i,j) & \mapsto & W(i,j)= K(X^i, X^j) \\
\end{array}
\right.
\end{equation*}
%
ou seja,
\begin{equation*}
W(i,j)= (K\circ(S\times S))(i,j)= K( (S\times S)(i,j))= K(X^i, X^j).
\end{equation*}
Na verdade queremos associar a cada par de índices $(i,j)$ o número real que representa a afinidade local entre os dados $X^i$ e $X^j,$ o que coincide
com a posição $(i,j)$ da matriz de pesos de um grafo (ver definição \ref{adjacencia}), onde os vértices são os dados $\{X^1,\dots,X^n\},$ chamado de grafo de similaridades.
Propositalmente chamamos a função anterior com o mesmo nome desta matriz de pesos
de modo que, por um abuso de notação, cada número real $K(X^i,X^j)$ será tratado como $(W)_{ij}=w_{ij}$ que é a notação
mais usual para o peso da aresta ligando o \emph{i}-ésimo e \emph{j}-ésimo vértices do grafo. Isto justifica toda esta
formalização com as funções acima. Assim procedendo já não estamos mais preocupados em qual espaço euclidiano os dados se encontram,
mas sim na quantidade de dados disponíveis e na afinidade existente entre os mesmos.
A técnica das autofun\coes\ do Laplaciano, e tamb\'em a metodologia da aplicação de difusão (a ser considerada no pr\'oximo cap\'{\i}tulo),
podem ser usadas até quando o conjunto é abstrato, formado de dados que não se encontram, necessariamente, em
$\re^d.$ Com isso vemos a importância de se escolher bem a matriz dos pesos \emph{W} na modelagem de problemas práticos pois de acordo com esta
escolha teremos uma melhor ou pior utilização dos dados de entrada.
%\todo{ex de grafo, ex do isomap paper}
\begin{comment}
É uma boa ideia expressar esta conectividade em termos do núcleo de difusão $k(x, y).$ Este núcleo representa alguma noção de afinidade ou similaridade entre os pontos \emph{x} e \emph{y} dentro de uma certa vizinhança e portanto constitui uma primeira definição da geometria local do conjunto de dados.
O núcleo Gaussiano é definido como
$ k(x,y)= exp(-\frac{\|x-y\|^2}{\varepsilon}),$ variando o parâmetro $\varepsilon$ escolhemos o tamanho da vizinhança baseado no conhecimento da estrutura e densidade dos dados.\\
\end{comment}
Belkin e Niyogi \cite{belkin2003laplacian} assumem que os dados do conjunto de treinamento
$E=\{X^1,X^2,\ldots,\\ X^n\}\allowbreak$ estão distribuídos de maneira aproximadamente uniforme numa variedade $\mathcal{M}$ de dimensão \emph{k} imersa em $\re^d.$
%No 2º parágrafo de Belkin/Nyogi pág.9 ele diz que a variedade é m-dimensional e no final da pág.10 ele fala do mergulho m-dimensional ótimo.
%
O algoritmo proposto, para incluir as imagens dos \emph{n} dados de $\re^d$ no espaço $\re^k,$ se baseia em construir um grafo onde cada dado $X^j$
corresponde a um vértice, criar a matriz dos pesos das arestas, \emph{W}, a partir de similaridades locais, e calcular as autofunções (autovetores)
do laplaciano generalizado
$(L\textbf{f}= \lambda D\textbf{f})$ para daí criar uma aplicação que representa os \emph{n} dados $X^j \in \re^d$ por \emph{n} vetores $Y^j \in \re^k$.
A justificativa vem do papel do operador de Laplace-Beltrami $(\Delta u = -div(\nabla u))$ na equação do calor $(u_t=\Delta u),$ para $u$ definida em $\mathcal{M}$ que nos permite usar o núcleo do calor para escolher a função de decaimento do peso. A variedade $\mathcal{M}$ é aproximada pelo grafo cujos vértices são os dados $X^1,X^2, \ldots , X^n$ e o operador de Laplace-Beltrami é aproximado pelo laplaciano do grafo, $L = A^\top CA = D - W,$ ver definição \ref{laplaciana}, teorema \ref{ATADW} e seção \ref{secgrafopeso}. Os pesos das arestas são aproximações do núcleo do calor
%Como o operador de Laplace-Beltrami sobre funções diferenciáveis numa variedade $M$ está intimamente relacionado ao fluxo de calor,
$$ H_t(x,y)\approx (4\pi t)^{-k/2}e^{-\frac{\|x-y\|^2}{4t}}$$
para \emph{x} próximo de \emph{y} e \emph{t} pequeno, sendo \emph{k} a dimensão da variedade. O núcleo do calor, por sua vez, pode ser interpretado com o auxílio da função de densidade gaussiana. De fato, fixados $y$ e $t,$
%
\begin{equation*}
\rho(x) = (4\pi t)^{-k/2}e^{-\frac{\|x-y\|^2}{4t}}
\end{equation*}
é a função de densidade de um vetor aleatório com distribuição normal multivariada com média $\textbf{y} \in \re^k$ e matriz de covariância $(2t)\mathcal{I}$ em $\re^k.$ (Veja capítulo $3$ e use $Q=(2t)^{-1}\mathcal{I}.$) A variância de cada uma das componentes $x_i$ é $2t,$ donde o desvio padrão é $\sqrt{2t}.$
%Assim, a aplicação de imersão para os dados aproxima as autofunções do operador de Laplace-Beltrami as quais são funções intrinsecamente definidas na variedade como um todo.
“Usar estas conexões permite interpretar algoritmos de redução de dimensionalidade de uma maneira geométrica” \cite{belkin2003laplacian}.
Em sua tese \cite{Belkin2003PLM979062} Belkin mostrou que o laplaciano de um grafo de pontos uniformemente amostrados reconstrói (aproxima) o operador de Laplace-Beltrami sobre uma variedade e que as autofunções deste operador podem ser usadas para redução de dimensionalidade. Mais tarde Lafon \cite{lafon2004diffusion} mostra que isso não pode ser estendido para densidades não uniformes e melhora este resultado descrevendo um algoritmo que lida com densidades mais gerais. O método das autofunções do laplaciano pode ser visto como um caso particular deste mais geral e também do método dos mapas de difusão.
%que é o método de maior interesse no nosso trabalho.
Voltaremos a falar sobre isso no capítulo \ref{ap_dif}.
Como já foi dito, a aplicação de imersão definida pela técnica das autofunções do laplaciano utiliza-se da teoria espectral dos grafos. Para tanto os vértices $X^i$ e $X^j$ são fortemente conectados, por exemplo, os pesos das arestas podem ser iguais à constante $1,$ quando estão próximos. Um possível critério de proximidade seria usar a norma euclidiana em $\re^d: \|X^i - X^j \|^2 < \delta,$ sendo $\delta$ uma tolerância escolhida. Quando não satisfaz este critério, os pesos das arestas seriam colocados iguais a zero (isto é, não haveria aresta ligando $X^i$ a $X^j).$
Os pesos das arestas podem ser escolhidos de várias outras formas. Por exemplo podem ser iguais a $\exp{(-\frac{\|X^i - X^j \|^2}{\varepsilon})},$ com
$\varepsilon \in \re$
para $X^i$ e $X^j$ próximos.
O parâmetro $\sqrt{\varepsilon}$ pode ser interpretado como um parâmetro de escala (confrontar com a interpretação proveniente da noção de desvio-padrão). A ideia de usar a exponencial para o peso é baseada no núcleo do calor e seu decaimento e será a escolha aqui adotada.
Finalmente, a função de imersão com as características desejadas será dada por
\begin{equation}\label{imLE}
X^i\mapsto Y^i = (f_1(i),f_2(i),\dots, f_k(i))^\top, \forall i \in \{1, \dots, n\}
\end{equation}
\begin{comment}
$$\left(
\begin{array}{c}
X_1 \\
X_2 \\
\vdots \\
X_n \\
\end{array}
\right)\mapsto
\left(
\begin{array}{c}
Y_1 \\
Y_2 \\
\vdots \\
Y_n \\
\end{array}
\right)=
\left(
\begin{array}{c}
(f_1(1),f_2(1),\ldots, f_k(1)) \\
(f_1(2),f_2(2),\ldots, f_k(2)) \\
\vdots \\
(f_1(n),f_2(n),\ldots, f_k(n)) \\
\end{array}
\right)^\top
$$
\end{comment}
onde $\textbf{f}_j:\{1, \ldots, n\}\rightarrow \re,$ para cada $j \in \{1, \ldots,k \}$ (onde $k \leq n - 1),$ é uma autofunção do laplaciano generalizado $(L\textbf{f}= \lambda D\textbf{f})$ excluindo-se a autofunção associada ao autovalor $\lambda_0 = 0,$ a qual já sabemos (ver observação $5$ na seção \ref{secgrafopeso}) ser a função constante
$\textbf{f}_0 = \frac{1}{\sqrt{n}}\cdot\openone,$ ou seja o vetor unitário onde cada componente $i \in \{1, \dots, n\},$ é dada por $f_0(i) = \frac{1}{\sqrt{n}}.$
\begin{comment}
$\textbf{f}_0 = \left(
\begin{array}{c}
\textbf{f}_0(1) \\
\textbf{f}_0(2) \\
\vdots \\
\textbf{f}_0(n) \\
\end{array}
\right)=
c.\left(
\begin{array}{c}
1 \\
1 \\
\vdots \\
1 \\
\end{array}
\right),$
\end{comment}
\section{Reduzindo de $\re^d$ para $\re$}\label{sec2lap}
Para iniciar vamos considerar o caso particular de transformar um grafo conexo \emph{G} num subconjunto de $\re$ (imersão em $\re$) de modo que as imagens de pontos próximos se mantenham próximas e as imagens de pontos distantes se mantenham distantes. Neste caso estaremos considerando $k=1$ na notação anterior e cada $Y^i$ será um número real $f_1(i),$ (não mais um vetor com várias componentes).
Para encontrar uma função que preserve distâncias como queremos um critério razoável é procurar valores para $\textbf{Y}=(Y^1,\dots, Y^n)$ que minimizem a soma $\sum_{i,j=1}^n (Y^i - Y^j)^2 W_{ij}$ sujeita a duas restrições, $\textbf{Y}D\textbf{Y}^\top=1$ e $\textbf{Y}D\openone=0,$ onde $D$ é a matriz grau do grafo com pesos $W.$ Note que para pontos $X^i$ e $X^j$ extremamente próximos, temos $W_{ij}\thickapprox 1$ e portanto minimizar o somatório anterior realmente significa procurar números reais $Y^i$ e $Y^j$ tão próximos quanto possível. Já quando $X^i$ e $X^j$ não forem próximos,
$W_{ij} \approx 0,$ donde $Y^i$ e $Y^j$ podem não ser próximos e ainda assim não prejudicar a minimização.
As restrições surgem naturalmente pela necessidade de eliminar o caso onde este mínimo seria zero. Vamos analisar as possibilidades deste mínimo trivial (igual a zero) ser atingido:
\begin{itemize}
\item [ (i)] $W$ é matriz nula, ou seja, $W_{ij}=0,\forall i, j$
\item [ (ii)] $\textbf{Y}$ é vetor nulo, ou seja, $Y^{i}=0,\forall i$
\item [ (iii)] $\textbf{Y}$ é vetor constante não nulo, ou seja, $Y_{i}=c\neq 0,\forall i$
%\item [ (iv)] Quando $Y^{i}\neq Y^{j}$ então $W_{ij}=0$ para cada $i,j %\in \{1, 2, \dots, n\}$
\end{itemize}
Note que o item (i) implicaria num grafo sem arestas e portanto é facilmente descartado, uma vez que não seria conexo. Além disso com a escolha da exponencial para a matriz dos pesos não poderíamos ter $W$ como matriz nula.
A restrição $\textbf{Y} D\textbf{Y}^\top=1$ servirá para descartarmos (i) e (ii).
A restrição $\textbf{Y} D\openone =0$ é incompatível com o item (iii). De fato, suponha por absurdo que $Y^1=Y^2= \dots =Y^n= c\neq 0.$ Assim,
%e todos os pontos teriam uma única imagem com $Y_i$ igual a $Y_j$ para todo $i,j.$ Este caso trivial
$$\textbf{Y} D\openone =d_1Y^1+d_2Y^2+ \dots +d_nY^n=0$$
implica em
%Neste caso podemos colocar em evidência este valor no somatório anterior. Assim,
$$\textbf{Y} D\openone = (d_1 + d_2 + \dots +d_n)c=0.$$
Mas isto é uma contradição pois $c\neq 0$ e $\sum_i d_i>0$ para qualquer grafo com pelo menos uma aresta! Portanto a restrição $\textbf{Y} D\openone =0$ impede que (iii) aconteça.
%
%O item $(iv)$ é descartado pelo fato do grafo ser conexo.
%não foi preciso levar em conta o fato de que poderíamos ter alguns $W_{ij}=0$ quando $Y_i$ fosse diferente de $Y_j$ para atender ao caso trivial.\\
%Uma outra restrição que funcionará como o análogo de estar na hiperesfera unitária para aplicação do teorema de Rayleigh-Ritz é $Y^\top DY=1,$ que será vista mais adiante.
%Note que para pontos $X_i$ e $X_j$ extremamente próximos, temos $W_{ij}\thickapprox 1$ e portanto minimizar o somatório anterior realmente significa procurar valores $Y_i$ e $Y_j$ tão próximos quanto possível.\draftnote{Mas qdo eles estão longe minimizar este somatório não quer dizer nada! E ai??}\\
\begin{teo}\label{minimo}
\begin{em}
Sejam $W$ a matriz de adjacência positiva semidefinida de um grafo com $n$ vértices, $D$ a matriz grau deste grafo e $L=D-W$ a matriz laplaciana. Considerando $k=1$ na equação (\ref{imLE}) e o vetor de números reais, $\textbf{Y}= (Y^1,Y^2,\ldots, Y^n),$ temos
\begin{equation}
\frac{1}{2}\sum_{i,j=1}^n(Y^i - Y^j)^2 W_{ij} = \textbf{Y} L\textbf{Y}^\top.
\end{equation}
\end{em}
\end{teo}
%Lembrando que $L = D - W,$ desenvolvendo o produto notável e mostrar que\\
Para uma demonstração refira-se ao apêndice. $\fim$
%
\begin{comment}
\noindent\begin{demo} % Para fazer quadradinho no final da demonstração
Como $k=1$ vemos que $Y^i=\textbf{f}_1(i)$ são números reais para cada
$i \in \{1, \dots, n\}.$ Portanto, desenvolvendo o produto notável e utilizando propriedades de somatórios podemos escrever:
\begin{equation*}
\sum_{i,j=1}^n(Y^i - Y^j)^2 W_{ij} = \sum_{i,j=1}^n((Y^i)^2 - 2Y^iY^j + (Y^j)^2)W_{ij} =
\end{equation*}
\begin{equation*}
=\sum_{i=1}^n(Y^i)^2(\sum_{j=1}^nW_{ij}) - 2 \sum_{i,j=1}^nY^iY^jW_{ij} + \sum_{j=1}^n(Y^j)^2(\sum_{i=1}^nW_{ij}),
\end{equation*}
lembrando que $d_{i}=\sum_{j=1}^n W_{ij}$ a soma anterior pode ser escrita como:
\begin{equation*}
\sum_{i=1}^n(Y^i)^2d_i + \sum_{j=1}^n(Y^j)^2d_j- 2 \sum_{i,j=1}^nY^iY^jW_{ij} =
\end{equation*}
\begin{equation*}
2\left( d_1(Y^1)^2+d_2(Y^2)^2+ \ldots + d_n(Y^n)^2\right) - 2\left(\sum_{i=1}^nY^i\sum_{j=1}^nW_{ij}Y^j\right)=
\end{equation*}
\begin{equation*}
=2\left[
\begin{array}{cccc}
Y^1 & Y^2 & \ldots & Y^n \\
\end{array}
\right]
\left[
\begin{array}{c}
d_1Y^1 \\
d_2Y^2 \\
\vdots \\
d_nY^n \\
\end{array}
\right] -2\left( Y^1\sum_{j=1}^nW_{1j}Y^j + Y^2\sum_{j=1}^nW_{2j}Y^j + \ldots + Y^n\sum_{j=1}^nW_{nj}Y^j\right)=
\end{equation*}
\begin{equation*}
=2Y^\top DY - 2\left[
\begin{array}{cccc}
Y^1 & Y^2 & \ldots & Y^n \\
\end{array}
\right]
\left[
\begin{array}{c}
\sum_{j=1}^nW_{1j}Y^j \\
\sum_{j=1}^nW_{2j}Y^j \\
\vdots \\
\sum_{j=1}^nW_{nj}Y^j \\
\end{array}
\right] = 2Y^\top DY - 2Y^\top WY =
\end{equation*}
$$= 2Y^\top(D-W)Y = 2Y^\top LY.$$
Portanto $\frac{1}{2}\sum_{i,j=1}^n(Y^i - Y^j)^2 W_{ij} = Y^\top LY$ como queríamos demonstrar.
\end{demo}\\
\end{comment}
\begin{teo}\label{minautL}
\begin{em}
Com a mesma notação do teorema anterior, se $\textbf{Y} D\textbf{Y}^\top =1$ então o vetor $\textbf{Y}$ que minimiza a forma quadrática
$\textbf{Y} L\textbf{Y}^\top$ é o autovetor associado ao menor autovalor solução do problema $L\textbf{Y}^\top= \lambda D\textbf{Y}^\top.$
\end{em}
\end{teo}
%
\noindent\begin{demo} % Para fazer quadradinho no final da demonstração
% Comentei minha demonstração e copiei a do Francisco
O problema que se quer considerar é determinar o mínimo e o ponto de mínimo da forma quadrática $\textbf{Y} L\textbf{Y}^\top$ sujeito à restrição $\textbf{Y} D\textbf{Y}^\top =1.$
Considere a mudança de variável
$\textbf{Z} = \textbf{Y}D^{\frac{1}{2}} .$
Então $\textbf{Y}=\textbf{Z}D^{-\frac{1}{2}},$ a forma quadrática é escrita como
$\textbf{Z}D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\textbf{Z}^{\top}$ e a restrição como $\textbf{Z} \textbf{Z}^\top=1.$ Em outras palavras
%
\begin{equation*}
\min_{Y,\ Y DY^\top =1} \textbf{Y} L\textbf{Y}^\top = \min_{Z,\ ZZ^\top=1}\textbf{Z}D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\textbf{Z}^{\top}.
\end{equation*}
%
Ora, $D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$ é uma matriz simétrica real. Logo, pelo teorema espectral, seus autovalores são reais. Denotemo-los por $\lambda_{0} \leqslant \lambda_{1} \leqslant \ldots \leqslant \lambda_{n-1}.$ Pelo Teorema de Rayleigh-Ritz (ver, por exemplo, \cite{franklin2000matrix}), o problema de minimização
$\min_{Z,\ ZZ^\top=1} \textbf{Z}D^{-\frac{1}{2}}LD^{-\frac{1}{2}} \textbf{Z}^{\top}$
tem por solução o menor autovalor da matriz
$D^{-\frac{1}{2}}LD^{-\frac{1}{2}},\lambda_0,$ e o ponto de mínimo é um autovetor associado, $\textbf{Z}_0,$ tal que
%
\begin{equation*}
D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\textbf{Z}_0^\top = \lambda_0 \textbf{Z}_0^\top, \ \ \ \textbf{Z}_0 \textbf{Z}_0^\top=1.
\end{equation*}
%
Defina agora $\textbf{Y}_0= \textbf{Z}_0 D^{-\frac{1}{2}}.$ Substituindo
$\textbf{Z}_0 = \textbf{Y}_0 D^{\frac{1}{2}}$ nas equações acima obtemos
\begin{equation*}
L\textbf{Y}_0^\top=\lambda_0D\textbf{Y}_0^\top,\ \ \
\textbf{Y}_0 D \textbf{Y}_0^{\top} = 1.
\end{equation*}
\end{demo}
%%%%%%%%%%%%%%
%%%%%%%%%%%%%%
\begin{comment}
O teorema de Rayleigh-Ritz (ver, por exemplo, \cite{franklin2000matrix}) nos diz que
$$\lambda_0\leqslant Y^\top LY \leqslant \lambda_{n-1}$$
para todo \emph{Y} na hiperesfera unitária uma vez que \emph{L} é simétrica, onde
$\lambda_0\leqslant \lambda_1 \leqslant \ldots \leqslant \lambda_{n-1}$
são os \emph{n} autovalores de \emph{L}. % O análogo da restrição de estar na hiperesfera unitária é a restrição $Y^\top DY=d_1Y_1^2+d_2Y_2^2+ \dots + d_nY_n^2=1$ (elipsóide), portanto o teorema de Rayleigh-Ritz pode ser aplicado ao nosso caso.\\
Utilizando a restrição $Y^\top DY=1,$ acima citada, podemos aplicar este teorema.\\
Seja $Y$ autovetor generalizado de $L$ associado ao autovalor $\lambda.$ Então,
\begin{equation}\label{YTLY}
Y^\top LY = Y^\top(LY) = Y^\top(\lambda DY) = \lambda(Y^\top DY) = \lambda . 1 = \lambda.
\end{equation}
Portanto, como $ \lambda_0\leqslant Y^\top LY \leqslant \lambda_{n-1},$ o mínimo de $Y^\top LY$ será $\lambda_0$ e será atingido quando \emph{Y} for solução de $L\textbf{Y}= \lambda D\textbf{Y}$ com a hipótese de que a restrição $Y^\top DY=1$ seja atendida.
\end{comment}
%
\noindent \textbf{Observação.} Já vimos (ver observação $5$ na seção \ref{secgrafopeso}) que o menor autovalor de \emph{L} é $\lambda_0 = 0$ cujo autovetor associado é $\openone.$ Para fugir desta solução trivial temos que acrescentar uma nova restrição de ortogonalidade que será $\textbf{Y} D\openone=0$ , ou seja, $D\textbf{Y}^\top \bot \openone.$ O teorema a seguir mostra que esta restrição junto com $\textbf{Y} D\textbf{Y}^\top=1$ acarreta em contradição se fizermos $\textbf{Y} = c\openone^\top, c \neq 0.$
\begin{teo}\label{restringe}
\begin{em}
Considerando as notações anteriores, o vetor $\textbf{Y} =c\openone^\top, c \neq 0, $ não pode atender simultaneamente as restrições $\textbf{Y} D\textbf{Y}^\top=1$ e $\textbf{Y} D\openone=0.$
\end{em}
\end{teo}
\noindent\begin{demo}
Suponha por absurdo que $\textbf{Y} = c\openone^\top, c \neq 0.$
Como $\textbf{Y} D\textbf{Y}^\top = \sum_{i=1}^n (Y^i)^2d_{i} = 1$ temos $\sum_{i=1}^n d_{i}=\dfrac{1}{c^2}, c \neq 0.$
E como $\textbf{Y} D\openone = \sum_{i=1}^n Y^id_{i} = 0$ temos $\sum_{i=1}^nd_{i}=0,$ o que é absurdo. Logo $\textbf{Y}\neq c\openone^\top.$
\end{demo}
Sendo assim, se acrescentarmos a restrição $\textbf{Y} D\openone=0$ ao teorema \ref{minautL} já não poderemos ter o vetor $\textbf{Y} =c \openone^\top$ como aquele que minimiza a forma quadrática $\textbf{Y}
L\textbf{Y}^\top.$ Gostaríamos de dizer que, neste caso, o próximo autovetor, associado ao autovalor $\lambda_1,$ seria o vetor procurado. %Mas para isto precisamos ter certeza que não existem outros vetores que façam a forma quadrática $\textbf{Y} L\textbf{Y}^\top$ ficar entre os dois menores autovalores de $L.$
O teorema a seguir vai tratar disso.
%
\begin{teo}\label{restri}
\begin{em}
Considere as restrições $\textbf{Y} D\textbf{Y}^\top=1$ e $\textbf{Y} D\openone=0$ com as notações e hipóteses do teorema \ref{minautL}.
Afirmamos o m\'{\i}nimo de $\textbf{Y} L\textbf{Y}^\top$ sujeito \`as restri\coes\
\'e o menor autovalor maior que zero e o ponto de m\'{\i}nimo
\'e o autovetor correspondente.
\end{em}
\end{teo}
%
\begin{comment}
\begin{teo}\label{restri}
\begin{em}
Considere as restrições $\textbf{Y} D\textbf{Y}^\top=1$ e $\textbf{Y} D\openone=0$ com as notações e hipóteses do teorema \ref{minautL}. Afirmamos que não existem vetores $\textbf{Y}$ satisfazendo as restrições tais que a forma quadrática $\textbf{Y} L\textbf{Y}^\top$ fique entre os dois menores autovalores de $L.$
\end{em}
\end{teo}
\end{comment}
%
Para uma demonstração refira-se ao apêndice.$\fim$
\begin{comment}
\noindent\begin{demo}
Suponha por absurdo que existe um vetor $Y$ tal que $Y^\top LY=\alpha,$ onde $\lambda_0< \alpha <\lambda_1$ com $\lambda_0$ e $\lambda_1$ sendo os dois menores autovalores de $L=D-W,$ com $D$ e $W$ nas hipóteses do teorema \ref{minautL}.\\
Podemos escrever
\begin{equation}
\alpha = Y^\top LY= Y^\top (D-W)Y=Y^\top DY - Y^\top WY.
\end{equation}
Como $Y^\top DY = 1,$ então
\begin{equation}\label{alfa}
\alpha = 1 - Y^\top WY.
\end{equation}\\
Dai
\begin{equation}
Y^\top WY = Y^\top W^\top Y = (WY)^\top Y = (\sum_{j=1}^nw_{1j}Y^j)Y^1 + (\sum_{j=1}^nw_{2j}Y^j)Y^2 + \dots + (\sum_{j=1}^nw_{nj}Y^j)Y^n.
\end{equation}
Considere $Y^s$ a maior das componentes do vetor $Y.$ Sendo assim podemos escrever a desigualdade
\begin{equation}\label{desYTWY}
Y^\top WY \leq [(\sum_{j=1}^nw_{1j}Y^j) + (\sum_{j=1}^nw_{2j}Y^j) + \dots + (\sum_{j=1}^nw_{nj}Y^j)]Y^s.
\end{equation}
Por outro lado, a restrição $Y^\top D\openone=0$ pode ser reescrita como
\begin{equation}
Y^\top D\openone = d_1Y^1 + d_2Y^2 + \dots d_nY^n = (\sum_{j=1}^n w_{1j})Y^1 + (\sum_{j=1}^n w_{2j})Y^2 + \dots + (\sum_{j=1}^n w_{nj})Y^n = 0.
\end{equation}
Como $W$ é simétrica isto equivale %a soma das colunas de $(WY)^\top$ e portanto
ao termo entre colchetes em \ref{desYTWY}, um simples cálculo com somatórios conduz a esta afirmação.
Logo $Y^\top WY \leq 0.$ Dai, pela equação \ref{alfa} vemos que
$\alpha \geq 1.$ \\
Mas isto é uma contradição, pois como $W$ é positiva semidefinida por hipótese, os autovalores de $W$ são maiores ou iguais a zero e portanto os autovalores de $L$ são menores ou iguais a um (ver Teorema \ref{equiv}(iv)). Portanto dizer que $\alpha \geq 1$ é incompatível com o fato de $\alpha$ estar estritamente entre os dois menores autovalores de $L.$ Portanto não existem vetores $Y$ tais que a forma quadrática $Y^\top LY$ fique entre os dois menores autovalores de $L,$ como queríamos demonstrar.
\end{demo}
\end{comment}
%
Sendo assim podemos dizer que o mínimo da forma quadrática $\textbf{Y}
L\textbf{Y}^\top,$ excluindo-se o autovalor $\lambda_0,$ é o autovalor $\lambda_1$ de $L$ que é atingido para $\textbf{Y}$ sendo o autovetor correspondente.% (confira em \ref{YTLY}).
Voltando ao início do nosso problema, a solução de
\begin{equation*}
\mbox{argmin\,}_{Y,\ Y DY^\top= 1, \,Y D1\!\!1= 0}\left(\frac{1}{2}\sum_{i,j=1}^n(Y^i - Y^j)^2 W_{ij}\right)
\end{equation*}
%
\begin{equation}
= \mbox{argmin\,}_{Y,\ Y DY^\top= 1, \,Y D1\!\!1= 0}\left(\textbf{Y} L\textbf{Y}^\top\right)
\end{equation}
\begin{comment}
\begin{equation}
\mbox{argmin\,}_{Y,\ Y DY^\top= 1, \,Y D1\!\!1= 0}\left(\frac{1}{2}\sum_{i,j=1}^n(Y^i - Y^j)^2 W_{ij}\right) =\mbox{argmin\,}_{\textbf{Y},\left\{{_{\textbf{Y} D\textbf{Y}^\top= 1}^{\textbf{Y} D1\!\!1= 0}}\right.}(\textbf{Y} L\textbf{Y}^\top)
\end{equation}
\end{comment}
será o autovetor $\textbf{Y}$ correspondente ao menor autovalor não nulo de \emph{L}, conhecido na literatura como o primeiro autovetor de Fiedler %\cite{Strang2007}, \cite{higham2007spectral}
\cite{Strang2007,higham2007spectral}.
Portanto as \emph{n} componentes do autovetor de Fiedler, números reais, são as imagens dos pontos $\textbf{X}^1,\textbf{X}^2, \ldots , \textbf{X}^n \in \mathcal{M} \subset \re^d$ quando a aplicação for de $\re^d$ para $\re.$ % A variedade M foi citada nas considerações iniciais.
Este caso particular pode ser generalizado utilizando-se tantos autovetores de \emph{L} quanto for a dimensão do espaço reduzido. Por exemplo, para a imersão em $\re$ usamos apenas o primeiro autovetor de Fiedler que é o autovetor associado ao menor autovalor não nulo $\lambda_1.$ Se a imersão for em $\re^2$ além do autovetor de Fiedler precisaremos também do autovetor associado ao próximo autovalor $\lambda_2,$ e assim sucessivamente. O caso mais geral será visto na seção seguinte.
\section{Problema mais geral}\label{sec3lap}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Ver se esta notação de linhas de X é compatível com o cap de diff maps.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
O problema agora consiste em mapear o grafo num espaço euclidiano
$k$–dimensional. A imagem da aplicação pode ser armazenada em uma matriz $\mathcal{Y}$ de tamanho $k \times n,$ onde, relembramos, a imagem do \emph{i}-ésimo vértice do grafo é levado na \emph{i}-ésima coluna de $\mathcal{Y}$ em $\re^k.$
Para maior clareza da notação representamos pictoricamente a matriz $\mathcal{Y}$ de três formas possíveis, por colunas $Y^j,$ por linhas $Y_i$ e por elementos $Y_i^j,$
%
\begin{equation}\label{y3}
\mathcal{Y} =\left[ \begin{array}{ccc}
\begin{array}{c}
\mid \\
Y^1 \\
\mid
\end{array}
& \ldots & \begin{array}{c}
\mid \\
Y^n \\
\mid
\end{array}
\end{array}
\right]
= \left[
\begin{array}{c}
- Y_1 - \\
\vdots \\
- Y_k -
\end{array}\right]
= \left[ \begin{array}{ccc}
\begin{array}{c}
Y_1^1 \\
\vdots\\
Y_k^1
\end{array}
& \begin{array}{c}
\ldots \\
\ddots\\
\ldots
\end{array}
& \begin{array}{c}
Y_1^n\\
\vdots \\
Y_k^n
\end{array}
\end{array}
\right].
\end{equation}
%
\begin{comment}
$$ Y=\left(
\begin{array}{cccc}
\mid & \mid & & \mid \\
y_1 & y_2 & \ldots & y_k \\
\mid & \mid & & \mid \\
\end{array}
\right)
.$$
\end{comment}
Novamente para encontrar a função imersão desejada precisamos minimizar
\begin{equation*}
\sum_{i,j=1}^n \|Y^{i} - Y^{j}\|^2 W_{ij},
\end{equation*}
sendo que agora $Y^i$ não é mais um número real, mas uma coluna da matriz $\mathcal{Y},$ ou seja, um vetor em $\re^k.$
%
\begin{teo}\label{minimogeral}
\begin{em}
Seja $W$ a matriz de adjacência de um grafo com $n$ vértices e $L$ a matriz laplaciana correspondente. Considere $\mathcal{Y}$ uma matriz $k \times n$ onde cada coluna $Y^i$ é dada como \ref{y3}. Então
\begin{equation}\label{traco}
\frac{1}{2}\sum_{i,j=1}^n \parallel Y^i - Y^j\parallel^2 W_{ij} = \mbox{tr}(\mathcal{Y} L\mathcal{Y}^\top),
\end{equation}
onde $\mbox{tr}(A)$ denota o traço da matriz $A.$
\end{em}
\end{teo}
%
Para uma demonstração refira-se ao apêndice.$\fim$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Ver se vale a pena jogar esta demonstração p apendice para não ficar muito carregada a escrita.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\noindent\begin{demo} % Para fazer quadradinho no final da demonstração
Como cada linha $Y^i$ de $Y$ é um vetor em $\re^k$ podemos desenvolver a definição de norma como produto interno para escrever:
\begin{equation}
\parallel Y^i - Y^j\parallel^2= < Y^i - Y^j, Y^i - Y^j> = \parallel Y^i \parallel^2 -2<Y^i,Y^j> + \parallel Y^j\parallel^2.
\end{equation}
Utilizando propriedades de somatórios temos
\begin{equation*}
\sum_{i,j=1}^n\parallel Y^i - Y^j\parallel^2 W_{ij}= \sum_{i,j=1}^n[\parallel Y^i \parallel^2 -2<Y^i,Y^j> + \parallel Y^j\parallel^2]W_{ij}=
\end{equation*}
\begin{equation*}
=\sum_{i=1}^n\parallel Y^i \parallel^2 \sum_{j=1}^nW_{ij} + \sum_{j=1}^n\parallel Y^j \parallel^2 \sum_{i=1}^nW_{ij} - 2\sum_{i,j=1}^n< Y^i, Y^j>W_{ij},
\end{equation*}
o que nos leva à expressão
\begin{equation}\label{eqLEmin}
\sum_{i,j=1}^n\parallel Y^i - Y^j\parallel^2 W_{ij}=2\sum_{i=1}^n\parallel Y^i \parallel^2d_i - 2 \sum_{i,j=1}^n (Y^i)^\top Y^jW_{ij}
\end{equation}
Por outro lado podemos notar que
\begin{equation*}
Y^\top DY=\left[
\begin{array}{cccc}
\textbf{f}_1(1) & \textbf{f}_1(2) & \cdots & \textbf{f}_1(n) \\
\textbf{f}_2(1) & \textbf{f}_2(2) & \cdots & \textbf{f}_2(n) \\
\vdots & \vdots & \ddots & \vdots \\
\textbf{f}_k(1) & \textbf{f}_k(2) & \cdots & \textbf{f}_k(n) \\
\end{array}
\right]
\left[
\begin{array}{cccc}
d_1\textbf{f}_1(1) & d_1\textbf{f}_2(1) & \cdots & d_1\textbf{f}_k(1) \\
d_2\textbf{f}_1(2) & d_2\textbf{f}_2(2) & \cdots & d_2\textbf{f}_k(2) \\
\vdots & \vdots & \ddots & \vdots \\
d_n\textbf{f}_1(n) & d_n\textbf{f}_2(n) & \cdots & d_n\textbf{f}_k(n) \\
\end{array}
\right]
\end{equation*}
\begin{equation}\label{eqLEmatrizYDY}
=\left[
\begin{array}{cccc}
\sum_{i=1}^nd_i\textbf{f}_1(i)^2 & \sum_{i=1}^nd_i\textbf{f}_1(i)\textbf{f}_2(i) & \cdots & \sum_{i=1}^nd_i\textbf{f}_1(i)\textbf{f}_k(i) \\
\sum_{i=1}^nd_i\textbf{f}_2(i)\textbf{f}_1(i) & \sum_{i=1}^nd_i\textbf{f}_2(i)^2 & \cdots & \sum_{i=1}^nd_i\textbf{f}_2(i)\textbf{f}_k(i) \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{i=1}^nd_i\textbf{f}_k(i)\textbf{f}_1(i) & \sum_{i=1}^nd_i\textbf{f}_k(i)\textbf{f}_2(i) & \cdots & \sum_{i=1}^nd_i\textbf{f}_k(i)^2 \\
\end{array}
\right]
\end{equation}
Portanto temos que
\begin{equation*}
tr(Y^\top DY)= \sum_{j=1}^k(\sum_{i=1}^nd_i\textbf{f}_j(i)^2)=
\end{equation*}
\begin{equation*}
=d_1\textbf{f}_1(1)^2+d_2\textbf{f}_1(2)^2+\cdots+d_n\textbf{f}_1(n)^2+
\end{equation*}
\begin{equation*}
+d_1\textbf{f}_2(1)^2+d_2\textbf{f}_2(2)^2+\cdots+d_n\textbf{f}_2(n)^2+\cdots+
\end{equation*}
\begin{equation*}
+d_1\textbf{f}_k(1)^2+d_2\textbf{f}_k(2)^2+\cdots+d_n\textbf{f}_k(n)^2=
\end{equation*}
\begin{equation*}
=d_1[\textbf{f}_1(1)^2+\textbf{f}_2(1)^2+\cdots+\textbf{f}_k(1)^2]+
\end{equation*}
\begin{equation*}
+d_2[\textbf{f}_1(2)^2+\textbf{f}_2(2)^2+\cdots+\textbf{f}_k(2)^2]+\cdots+
\end{equation*}
\begin{equation*}
+d_n[\textbf{f}_1(n)^2+\textbf{f}_2(n)^2+\cdots+\textbf{f}_k(n)^2].
\end{equation}
Logo
\begin{equation}\label{eqLEYDY}
tr(Y^\top DY)= \sum_{i}^n\parallel Y^i \parallel^2d_i.
\end{equation}
Com o mesmo exercício de matrizes e propriedades de somatórios podemos escrever
\begin{equation*}
Y^\top WY=\left[
\begin{array}{cccc}
\textbf{f}_1(1) & \textbf{f}_1(2) & \cdots & \textbf{f}_1(n) \\
\textbf{f}_2(1) & \textbf{f}_2(2) & \cdots & \textbf{f}_2(n) \\
\vdots & \vdots & \ddots & \vdots \\
\textbf{f}_k(1) & \textbf{f}_k(2) & \cdots & \textbf{f}_k(n) \\
\end{array}
\right]\left[
\begin{array}{cccc}
\sum_{i=1}^nw_{1i}\textbf{f}_1(i) & \sum_{i=1}^nw_{1i}\textbf{f}_2(i) & \cdots & \sum_{i=1}^nw_{1i}\textbf{f}_k(i) \\
\sum_{i=1}^nw_{2i}\textbf{f}_1(i) & \sum_{i=1}^nw_{2i}\textbf{f}_2(i) & \cdots & \sum_{i=1}^nw_{2i}\textbf{f}_k(i) \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{i=1}^nw_{ni}\textbf{f}_1(i) & \sum_{i=1}^nw_{ni}\textbf{f}_2(i) & \cdots & \sum_{i=1}^nw_{ni}\textbf{f}_k(i) \\
\end{array}
\right]=
\end{equation*}
\begin{equation*}
=\left[
\begin{array}{cccc}
\sum_{j=1}^n\textbf{f}_1(j)\sum_{i=1}^nw_{ji}\textbf{f}_1(i) & \sum_{j=1}^n\textbf{f}_1(j)\sum_{i=1}^nw_{ji}\textbf{f}_2(i) & \cdots & \sum_{j=1}^n\textbf{f}_1(j)\sum_{i=1}^nw_{ji}\textbf{f}_k(i) \\
\sum_{j=1}^n\textbf{f}_2(j)\sum_{i=1}^nw_{ji}\textbf{f}_1(i) & \sum_{j=1}^n\textbf{f}_2(j)\sum_{i=1}^nw_{ji}\textbf{f}_2(i) & \cdots & \sum_{j=1}^n\textbf{f}_2(j)\sum_{i=1}^nw_{ji}\textbf{f}_k(i) \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{j=1}^n\textbf{f}_k(j)\sum_{i=1}^nw_{ji}\textbf{f}_1(i) & \sum_{j=1}^n\textbf{f}_k(j)\sum_{i=1}^nw_{ji}\textbf{f}_2(i) & \cdots & \sum_{j=1}^n\textbf{f}_k(j)\sum_{i=1}^nw_{ji}\textbf{f}_k(i) \\
\end{array}
\right]
\end{equation*}
Portanto o traço desta matriz será
\begin{equation*}
tr(Y^\top WY)= \sum_{j=1}^n\textbf{f}_1(j)\sum_{i=1}^nw_{ji}\textbf{f}_1(i)+\sum_{j=1}^n\textbf{f}_2(j)\sum_{i=1}^nw_{ji}\textbf{f}_2(i)+\cdots+\sum_{j=1}^n\textbf{f}_k(j)\sum_{i=1}^nw_{ji}\textbf{f}_k(i).
\end{equation*}
Juntando os somatórios podemos escrever ainda
\begin{equation*}
tr(Y^\top WY) = \sum_{i,j=1}^n\textbf{f}_1(j)\textbf{f}_1(i)w_{ji}+\sum_{i,j=1}^n\textbf{f}_2(j)\textbf{f}_2(i)w_{ji}+\cdots+\sum_{i,j=1}^n\textbf{f}_k(j)\textbf{f}_k(i)w_{ji}=\sum_{r=1}^k\sum_{i,j=1}^n\textbf{f}_r(j)\textbf{f}_r(i)w_{ij}
\end{equation*}
e como $W$ é simétrica podemos inverter a ordem do somatório
\begin{equation*}
tr(Y^\top WY) =\sum_{i,j=1}^n[\sum_{r=1}^k\textbf{f}_r(i)\textbf{f}_r(j)]w_{ij}.
\end{equation*}
Finalmente chegamos à expressão
\begin{equation}\label{eqLEYWY}
tr(Y^\top WY)= \sum_{i,j=1}^n(Y^i)^\top Y^jw_{ij}
\end{equation}
Substituindo \ref{eqLEYDY} e \ref{eqLEYWY} em \ref{eqLEmin}
\begin{equation*}
\sum_{i,j=1}^n \parallel Y^i - Y^j\parallel^2 W_{ij} = 2tr(Y^\top DY)- 2tr(Y^\top WY)=
\end{equation*}
\begin{equation*}
=2tr(Y^\top DY- Y^\top WY)=2tr(Y^\top (D-W)Y)=2tr(Y^\top LY).
\end{equation*}
Portanto
\begin{equation*}
\frac{1}{2}\sum_{ij}^n\|Y^i - Y^j\|^2 W_{ij} = tr(Y^\top LY)
\end{equation*}
como queríamos demonstrar.
\end{demo}\\
\end{comment}
Assim o nosso problema pode se resumir a minimizar
$\mbox{tr}(\mathcal{Y} L\mathcal{Y}^\top),$ o traço de $\mathcal{Y}^\top L\mathcal{Y},$ com $\mathcal{Y}$ variando e $L$ fixo.
Como cada elemento de $W$ é não negativo e analogamente para a norma euclidiana vemos pela Equação (\ref{traco}) que o traço,
$\mbox{tr}(\mathcal{Y} L\mathcal{Y}^\top),$ é maior ou igual a zero. Logo, escolhendo $\mathcal{Y} = 0,$ o mínimo procurado seria o número zero. Novamente teremos uma restrição a fim de eliminar este caso trivial. Vamos analisar algumas possibilidades deste mínimo ser atingido conforme fizemos na seção anterior:
\begin{itemize}
\item [$ (i)$] $W_{n \times n}$ é a matriz nula
\item [$(ii)$] $\mathcal{Y}_{k \times n}$ é a matriz nula
\item [$(iii)$] As colunas da matriz $\mathcal{Y}$ são iguais, ou seja, $Y^{i}=Y^{j},\forall i,j$
%\item [$(iv)$] Quando as linhas $Y_{i}$ e $Y_{j}$ forem diferentes então $W_{ij}=0$ %para cada $i,j \in \{1, 2, \dots, n\}$
\end{itemize}
O item $(i)$ é descartado analogamente à seção anterior.\\
%Note que o item $(i)$ implicaria num grafo sem arestas e portanto é facilmente descartado.\\
Considerando a restrição $\mathcal{Y} D\mathcal{Y}^\top=\mathcal{I}_k,$ onde $\mathcal{I}_k$ é a identidade $k \times k$, poderemos descartar também $(ii).$\\
A restrição $\mathcal{Y} D\mathcal{Y}^\top =\mathcal{I}_k$ também é incompatível com o item $(iii).$ De fato, suponha por absurdo que todas as colunas de $\mathcal{Y}$ sejam iguais. Para facilitar o entendimento podemos escrever esta matriz como
\begin{equation*}
\mathcal{Y}=\left[
\begin{array}{ccc}
- & c_1\openone^\top & - \\
- & c_2\openone^\top & - \\
& \vdots & \\
- & c_k\openone^\top & - \\
\end{array}
\right],
\end{equation*}
com $\openone \in \re^n.$
Podemos escrever o produto referente à restrição anterior como
\begin{equation*}
\mathcal{Y} D\mathcal{Y}^\top=\left[
\begin{array}{ccc}
- & c_1\openone^\top & - \\
- & c_2\openone^\top & - \\
& \vdots & \\
- & c_k\openone^\top & - \\
\end{array}
\right]
\left[
\begin{array}{cccc}
d_1 & & & \\
& d_2 & & \\
& & \ddots & \\
& & & d_n \\
\end{array}
\right]
\left[
\begin{array}{cccc}
\mid & \mid & & \mid \\
c_1\openone & c_2\openone & \cdots & c_k\openone \\
\mid & \mid & & \mid \\
\end{array}
\right]
\end{equation*}
%
\begin{equation*}
=\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\left[
\begin{array}{ccc}
- & \openone^\top & - \\
- & \openone^\top & - \\
& \vdots & \\
- & \openone^\top & - \\
\end{array}
\right]
\left[
\begin{array}{cccc}
d_1 & & & \\
& d_2 & & \\
& & \ddots & \\
& & & d_n \\
\end{array}
\right]
\left[
\begin{array}{cccc}
\mid & \mid & & \mid \\
\openone & \openone & \cdots & \openone \\
\mid & \mid & & \mid \\
\end{array}
\right]
\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right].
\end{equation*}
%
Mas, para uma matriz $k \times n,$ cujas entradas são todas iguais a $1$ vale
\begin{equation*}
\left[
\begin{array}{ccc}
- & \openone^\top & - \\
- & \openone^\top & - \\
& \vdots & \\
- & \openone^\top & - \\
\end{array}
\right]=
\left[
\begin{array}{cccc}
\mid & \mid & & \mid \\
\openone & \openone & \cdots & \openone \\
\mid & \mid & & \mid \\
\end{array}
\right],
\end{equation*}
onde, na matriz da esquerda $\openone \in \re^n$ e na da direita $\openone \in \re^k.$
Assim, $\mathcal{Y} D\mathcal{Y}^\top$ pode ser escrito como o produto
%\begin{equation*}
%Y^\top DY=
%\end{equation*}
%
\begin{equation*}
\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\left[
\begin{array}{cccc}
\mid & \mid & & \mid \\
\openone & \openone & \cdots & \openone \\
\mid & \mid & & \mid \\
\end{array}
\right]
\left[
\begin{array}{cccc}
d_1 & & & \\
& d_2 & & \\
& & \ddots & \\
& & & d_n \\
\end{array}
\right]
\left[
\begin{array}{ccc}
- & \openone^\top & - \\
- & \openone^\top & - \\
& \vdots & \\
- & \openone^\top & - \\
\end{array}
\right]
\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\end{equation*}
%
\begin{equation*}
=\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\left[
\begin{array}{cccc}
\mid & \mid & & \mid \\
d_1\openone & d_2\openone & \cdots & d_n\openone \\
\mid & \mid & & \mid \\
\end{array}
\right]
\left[
\begin{array}{ccc}
- & \openone^\top & - \\
- & \openone^\top & - \\
& \vdots & \\
- & \openone^\top & - \\
\end{array}
\right]
\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\end{equation*}
%
\begin{equation*}
=\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
(d_1\openone\openone^\top + d_2\openone\openone^\top + \cdots + d_n\openone\openone^\top)
\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\end{equation*}
%
\begin{equation*}
=\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
(d_1 + d_2+ \cdots + d_n)\openone\openone^\top
\left[
\begin{array}{cccc}
c_1 & & & \\
& c_2 & & \\
& & \ddots & \\
& & & c_k \\
\end{array}
\right]
\end{equation*}
%
\begin{equation*}
= \mbox{tr}(D)\left[
\begin{array}{c}
c_1 \\
c_2 \\
\vdots\\
c_k \\
\end{array}
\right]
\left[
\begin{array}{cccc}
c_1 & c_2 & \ldots & c_k \\
\end{array}
\right]
\end{equation*}
%
Ou seja,
\begin{equation*}
\mathcal{Y} D\mathcal{Y}^\top = \mbox{tr}(D)\left[
\begin{array}{cccc}
c_1^2 & c_1c_2 & \ldots & c_1c_k \\
c_2c_1 & c_2^2 & \ldots & c_2c_k \\
\vdots & \vdots & \ddots & \vdots \\
c_kc_1 & c_kc_2 & \ldots & c_kc_2 \\
\end{array}
\right]
\end{equation*}
%
\begin{comment}
\begin{equation}\label{yTD}
=\left[
\begin{array}{cccc}
c_1^2\sum_{i=1}^nd_i & c_1c_2\sum_{i=1}^nd_i & \cdots & c_1c_k\sum_{i=1}^nd_i \\
c_2c_1\sum_{i=1}^nd_i & c_2^2\sum_{i=1}^nd_i & \cdots & c_2c_k\sum_{i=1}^nd_i \\
\vdots & \vdots & \ddots & \vdots \\
c_kc_1\sum_{i=1}^nd_i & c_kc_2\sum_{i=1}^nd_i & \cdots & c_k^2\sum_{i=1}^nd_i \\
\end{array}
\right]
\end{equation}
\end{comment}
Como a restrição pede que $\mathcal{Y} D\mathcal{Y}^\top=\mathcal{I}_k,$ vemos que
%\begin{equation*}
%c_1^2\sum_{i=1}^nd_i=c_2^2\sum_{i=1}^nd_i=\cdots=c_k^2\sum_{i=1}^nd_i=1
%\end{equation*}
%
\begin{equation*}
c_1^2\mbox{\,tr\,}(D)=c_2^2\mbox{\,tr\,}(D)=\cdots=c_k^2\mbox{\,tr\,}(D)=1
\end{equation*}
%
deve ser atendido ao mesmo tempo que %e portanto $c_i\neq 0, \forall i$ e $\sum_{i=1}^nd_i\neq 0.$ Contraditoriamente a equação \ref{yTD} junto com a mesma restrição nos conduz a
%\begin{equation*}
%c_rc_s\sum_{i=1}^nd_i=0, \forall r,s.
%\end{equation*}
%
\begin{equation*}
c_rc_s\mbox{\,tr\,}(D)=0, \forall r,s.
\end{equation*}
Mas como estas duas exigências são contraditórias vemos que a restrição considerada descarta a possibilidade de acontecer o item $(iii). \fim$
%Portanto a restrição citada previne de colapsar todos os dados num subespaço de dimensão menor que $k-1$ (ou \emph{k} se exigirmos ortogonalidade com o vetor $\openone).$
Em suma, nosso problema neste caso mais geral se restringe a encontrar
\begin{equation*}
\mbox{argmin\,}(\mbox{\,tr\,}(\mathcal{Y} L\mathcal{Y}^\top))
\end{equation*}
sujeito à restrição $\mathcal{Y} D\mathcal{Y}^\top=\mathcal{I}.$ De maneira análoga à anterior os métodos padrão mostram que a solução para este argumento mínimo é conseguida pela matriz de autovetores correspondentes aos autovalores não triviais do problema de autovalores generalizado $L\mathcal{Y}^\top= \lambda D\mathcal{Y}^\top.$ Na verdade este último problema é decomposto em $k$ subproblemas do tipo apresentado na seção anterior e portanto as soluções são análogas.
\begin{comment}
\section{Resumo do algoritmo}
\begin{itemize}
\item \emph{Passo} 1) Construir um grafo onde os dados de entrada $X_i$ são os vértices e estão conectados quando estiverem próximos,
$$||X_i-X_j||^2<\delta,$$
para esta proximidade podemos usar norma euclidiana em $\re^n.$
\item \emph{Passo} 2) Se os vértices $X_i$ e $X_j$ estiverem conectados faça $w_{ij}=e^{-(||X_i-X_j||^2)/\varepsilon},$ onde $\varepsilon$ é um parâmetro dado, de difícil escolha, que deve ser pesquisado de acordo com o problema. Se os vértices não estiverem conectados faça $w_{ij}=0.$
\item \emph{Passo} 3) Encontrar os autovalores e autovetores do problema de autovetor generalizado $L\overrightarrow{f}=\lambda D\overrightarrow{f}$ onde $L=D-W $ (grafo laplaciano) e $D_{ii}=\sum_j w_{ij} $. O mergulho será dado por $ X_i \longrightarrow Y_i = (\overrightarrow{f_1}(i),...,\overrightarrow{f_k}(i)),$
$Y_i \in \re^k, $ onde $\overrightarrow{f_1}(i)$ é a \emph{i}-ésima componente do autovetor associado ao menor autovalor não nulo do problema.O autovetor $\overrightarrow{f_2}$ é o segundo menor não nulo e assim sucessivamente. Podemos dizer que os $\overrightarrow{f_j}$ são autovetores da matriz $D^{-1}L=D^{-1}(D-W)=I-D^{-1}W.$
\end{itemize}
Um resumo do algoritmo é apresentado no apêndice.
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%% FIM DO COMENTÁRIO ACIMA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
O quadro a seguir apresenta um pseudo código das autofunções do laplaciano.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Algoritmo dentro de uma caixinha
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\fbox{\fbox{
\parbox{14cm}{\textbf{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).$
%e estão conectados pela matriz peso das arestas dada por $W_{ij}=e^{-(||X^i-X^j||^2)/\varepsilon},$ onde $\varepsilon$ é um parâmetro dado.
\item Calcular os autovalores e autovetores de $L\textbf{f}=\lambda D\textbf{f}$ onde $L=D-W $ e $(D)_{ii}=\sum_{j=1}^n w_{ij} $.
\item A imersão é dada por
\begin{equation*}
X^i \longrightarrow Y^i = (f_1(i),...,f_k(i))^\top, \ \ Y^i \in \re^k,
\end{equation*}
onde $f_1(i)$ é a \emph{i}-ésima componente do autovetor associado ao menor autovalor não nulo do problema. O autovetor \textbf{f}$_2$ é associado ao segundo menor autovalor não nulo e assim sucessivamente. Podemos dizer que os \textbf{f}$_j$ são autovetores da matriz $D^{-1}L=D^{-1}(D-W)=I-D^{-1}W.$
\end{itemize}
\textbf{Saída}: conjunto de dados $Y^i, i= 1, \ldots, n$ de dimensão mais baixa em $\re^k.$
}}}
\end{center}
\subsection*{Escolha do tamanho de vizinhança}\label{vizLE}
Vamos discutir o tamanho da vizinhança considerada, para os vértices serem ou não conectados, no
caso em que a matriz peso das arestas é dada por $W_{ij}=e^{-(||X^i-X^j||^2)/\varepsilon}.$
O parâmetro $\varepsilon$ neste caso é de difícil escolha e deve ser pesquisado de acordo com o problema. De fato, não há atualmente uma solução satisfatória para a escolha do parâmetro $\varepsilon.$ Em nossos experimentos utilizamos $\varepsilon$ igual
ao quadrado da
maior distância entre todos os dados de entrada (isto é, o quadrado do \textit{diâmetro} $r$ do conjunto de dados), ou então algum múltiplo ou submúltiplo desta maior distância.
Alguns autores defendem informalmente a escolha de um $\varepsilon$ bastante pequeno, tanto por eficiência (já que o grafo será esparso), como por questões de aproximação à situação contínua subjacente. Uma ideia é fazer uma busca pelo menor $\varepsilon$ tal que o grafo permaneça conexo, e testar vários $\varepsilon$ próximos a isso em subproblemas representativos.
Note, no entanto, que quanto menor $\varepsilon$ mais densa a base de dados (maior \emph{n}) terá de ser para manter o grafo conectado. E com $\varepsilon \rightarrow 0$ e $n \rightarrow \infty$ Belkin e Niyogi mostraram que nos aproximamos dos fenômenos contínuos de difusão de calor na variedade para, assim, fazer uma redução de dimensionalidade próxima ao ideal de mínima distorção.
De qualquer forma, $\varepsilon^{1/2}$ pode ser pensado como a escala padrão para a medição dos dados, uma vez que os pesos são dados por função proporcional à gaussiana.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Pensar em novos exemplos pois tirei os velhos.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{comment} % Terminina este comentário em 739
\section{Experimento}\label{sec4lap}
%\todo{ver se consigo colocar algum exemplo das fotos ou rotação de vogais}
Aplicamos o algoritmo das autofunções do Laplaciano a uma hélice no espaço euclidiano tridimensional com o intuito de ilustrar e discutir aspectos do seu funcionamento na prática como, por exemplo, a escolha do $\varepsilon,$ tamanho da vizinhança. Utilizamos $189$ pontos em $\re^3$ formando uma hélice de três voltas com o parâmetro angular variando de zero a $6\pi.$ O parâmetro $\varepsilon$ do peso gaussiano foi experimentado utilizando-se múltiplos do quadrado do diâmetro do conjunto de dados de entrada (denotado aqui por $r).$
A Figura \ref{hel10} apresenta, à esquerda, a hélice original e, à direita, os $189$ pontos da hélice após aplicação do algoritmo das autofunções do laplaciano. Esta figura foi gerada com o parâmetro $\varepsilon=0,1r^2,$ ou seja, como sendo dez por cento
do quadrado
da maior distância entre os dados de entrada.
Para a Figura \ref{LE100hel1000} (a) o experimento foi repetido fazendo-se o $\varepsilon=r^2$ enquanto a Figura \ref{LE100hel1000} (b) mostra o caso para $\varepsilon=10r^2.$
\begin{figure}[!httb] % Figura feita com luleplote(TX19,10), TX19 de todo_dado.m
\centering
\includegraphics[width=\textwidth]{LEhel10.png}
\caption[Autofunção do laplaciano - $\varepsilon = 0,1r$ - hélice]{Uma hélice original e ao lado a curva resultante da aplicação das autofunções do laplaciano em $\re^3.$ O parâmetro $\varepsilon = 0,1r^2$ foi utilizado.}
\label{hel10}
\end{figure}
Nas figuras supracitadas podemos notar que, neste exemplo, o fato do $\varepsilon$ aumentar implica num
gráfico semelhante à hélice original com suas três voltas já quando $\varepsilon$ diminui a hélice é desenrolada. Uma possível explicação é que, para $\varepsilon$ grande, todos os pontos ficam conectados, assim como no espaço de entrada $\re^3,$ em que há um grafo completo induzido pelas distâncias ponto a ponto. Já com $\varepsilon$ pequeno o grafo de similaridades tende a conectar apenas vizinhos ao longo da variedade, sendo uma aproximação à variedade.
\begin{figure}%Feita com luleplote comentando algumas partes
\centering
\subfigure[refhel100][$\varepsilon = r^2$ ]{\includegraphics[scale=0.5]{LEhel100.png}}
\subfigure[refhel1000][ $\varepsilon = 10r^2$]{\includegraphics[scale=0.5]{LEhel1000.png}}
\caption[Autofunção do laplaciano - $\varepsilon = r$ e $\varepsilon = 10r$ - hélice]{(a) Representação de uma hélice em $\re^3$ após aplicação das autofunções do laplaciano com $\varepsilon$ igual ao quadrado do diâmetro do conjunto dos dados de entrada. (b) O mesmo experimento para $\varepsilon$ sendo dez vezes o valor anterior.}
\label{LE100hel1000}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%FALO EM NORMALIZADOS E NÃO NORMALIZADOS ???????????%%%%%%%%%%%%%%%%%%%%%%%%%%
%Neste exemplo percebemos uma diferença sensível para o fato de normalizar ou não os dados. Aqui estou usando a palavra normalizar no sentido de tornar unitária a norma dos dados. As figuras comentadas a seguir são para os dados originais sem normalização.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
A figura \ref{LEhelice}(a) mostra os pontos da própria hélice e suas imagens em $\re,$ $\re^2$ e $\re^3.$ As imagens e os dados originais juntos num mesmo gráfico nos revelam a diferença de escala entre os dados originais e suas imagens pelo método das autofunções do Laplaciano.
Na figura \ref{LEhelice}(b) ampliamos as imagens sem a hélice original para melhor compreensão.
%não temos muito interesse já que não estamos reduzindo a dimensionalidade, mas mesmo assim plotamos a imagem para verificar o que aconteceria.
\begin{figure}[!httb]
\centering
\includegraphics[scale=0.4]{LE_helice123D.png}
\caption{Uma hélice em $\re^3$ com suas imagens pelas autofunções do Laplaciano em $\re^3$, $\re^2$ e $\re.$}
\label{LEhelice} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
\begin{figure}
\centering
\subfigure[refLE123][Uma hélice em $\re^3$ com suas imagens pelas autofunções do Laplaciano em $\re^3$, $\re^2$ e $\re.$ ]{\includegraphics[scale=0.4]{LE_helice123D.png}}
\subfigure[refLE123amp][Ampliação das imagens nas três dimensões]{\includegraphics[scale=0.4]{LE_hel123Damplia.png}}
\caption{(a) A figura apresenta uma hélice e suas imagens pelas autofunções do Laplaciano para uma, duas e três dimensões. (b) As três imagens anteriores foram ampliadas para melhor visualização.}
\label{LEhelice} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Não sei pq está parecendo esta parte de baixo msm com comentário, não era para aparecer
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Na figura \ref{LEhel}(a) ampliamos apenas as imagens em uma e duas dimensões. Note que a imagem em uma dimensão ficou semelhante a imagem do PCA onde as cores organizadas conforme os dados de entrada guardam as informações iniciais de modo satisfatório. Em $\re^2$ a imagem ficou semelhante a uma parábola também mantendo a distribuição das cores originais.
Na figura \ref{LEhel}(b) ampliamos a imagem da hélice em $\re^3.$ Note que neste caso encontramos um pedaço de hélice em escala reduzida. Também neste caso a ordem das cores são mantidas revelando bem as informações da hélice original.
A figure \ref{LEhel3D3D} mostra a hélice original junto com sua imagem em três dimensões para facilitar a visualização da posição relativa entre as duas hélices, a original e a imagem em 3D. Note que a hélice original “sobe” do azul para o marrom enquanto a sua imagem reduzida “desce” do azul para o marrom.
\begin{figure}
\centering
\subfigure[refLE1d2d][Mapeamento ampliado da hélice em uma e duas dimensões ]{\includegraphics[scale=0.4]{LE_hel1d2d.png}}
\subfigure[refLE3d][Mapeamento ampliado da hélice em três dimensões]{\includegraphics[scale=0.4]{LE_hel3d.png}}
\caption{(a) A figura apresenta de maneira ampliada as imagens pelas autofunções do Laplaciano para a hélice em uma e duas dimensões. Nos dois casos a ordem das cores indica uma boa percepção das informações contidas nos pontos da hélice original. (b) O mesmo procedimento foi feito para as imagens da hélice em três dimensões. Também neste caso a ordem das cores é coerente com a distribuição de cores na hélice original.}
\label{LEhel} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
\begin{figure}[!httb]
\centering
\includegraphics[scale=0.4]{LE_hel3D3D.png}
\caption{A hélice original em $\re^3$ com sua imagem pelas autofunções do Laplaciano em 3D.}
\label{LEhel3D3D} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
\end{comment}
A figura \ref{autc10c100c1000}
mostra o gráfico dos primeiros autovalores do laplaciano generalizado para este exemplo da hélice. Conforme variamos o parâmetro $\varepsilon$ o comportamento dos autovalores também se altera. O primeiro autovalor é zero nas três situações como esperado. A Tabela
~\ref{tabautovcap4} a seguir apresenta os dez primeiros autovalores para o exemplo da hélice considerando as três escolhas de $\varepsilon.$ Para as maiores vizinhanças vemos que os autovalores logo se estabilizam no valor $1,$ para a menor vizinhança utilizada, $\varepsilon=0,1r^2 ,$ somente a partir do $18º$ é que os autovalores passaram a ser iguais a $1.$
%
\begin{table}[!htpb]
\begin{center}
\caption{Primeiros dez autovalores da matriz laplaciana para o exemplo da hélice com três escolhas diferentes para o tamanho da vizinhança na matriz dos pesos das arestas.}
\begin{tabular}{|p{6em}||p{6em}||p{6em}|}
\hline
%\multicolumn{3}{|c|}{\textbf{Autovalores para autofunções do laplaciano }}\\
\hline
$\varepsilon=0,1r^2$ & $\varepsilon=r^2$ & $\varepsilon=10r^2$ \\
\hline\hline
0.0000&0.0000&0.0000 \\ \hline
0.2703&0.8438&0.9833 \\ \hline
0.6440&0.9893&0.9997\\ \hline
0.8609&0.9972&0.9997\\ \hline
0.9468&0.9973&0.9999\\ \hline
0.9690&0.9994&1.0000\\ \hline
0.9713&0.9997&1.0000 \\ \hline
0.9759&0.9998&1.0000\\ \hline
0.9859&1.0000&1.0000\\ \hline
0.9937&1.0000&1.0000\\ \hline
\end{tabular}
\label{tabautovcap4}
\end{center}
\end{table}
%\begin{figure}[!httb]
%\centering
%\includegraphics[scale=0.4]{aut_LE_hel.png}
%\caption{Gráfico dos autovalores do laplaciano.}
%\label{LEhel3D3D} % Para referenciar esta figura mais a frente caso sj necessário
%\end{figure}
%
\begin{figure} % Figura feita com lule(TX19,c) com c=10,100 e 1000. Qdo quero só os 10 primeiros coloco j=1:10 no gráfico em lule.m
\centering
\subfigure[refautc10][ $ \varepsilon = 0,1r^2$ ]{\includegraphics[scale=0.3]{LE_helc10aut.png}}
\subfigure[refautc100][ $ \varepsilon = r^2$ ]
{\includegraphics[scale=0.3]{LE_helc100aut.png}}
\subfigure[refautc1000][ $ \varepsilon = 10r^2$ ]{\includegraphics[scale=0.3]{LE_helc1000aut.png}}
\caption[Autofunções do laplaciano - autovalores hélice]{(a) Gráfico dos $20$ primeiros autovalores do laplaciano generalizado para o exemplo da hélice tridimensional com $\varepsilon= 0,1r^2.$ A partir do $18º$ autovalor todos se igualam a $1.$ (b) Gráfico dos $10$ primeiros autovalores para $\varepsilon=r^2.$ Já a partir do $9º$ os autovalores são $1.$ (c) O maior valor utilizado para este parâmetro $\varepsilon=10r^2.$ A partir do $6º$ os autovalores já se igualam a $1.$}
\label{autc10c100c1000}
\end{figure}
%
\begin{comment} % Francisco mandou tirar
Para efeito de comparação com a Figura \ref{pcahelice} do capítulo anterior plotamos num mesmo gráfico a hélice original junto com as imagens dos seus $189$ pontos de $\re^3$ reduzidos para a reta unidimensional. A reta é de tamanho tão reduzido que foi necessário ampliá-la para perceber a relação entre as cores. A Figura \ref{hel1D10} mostra a hélice junto com a reta para $\varepsilon$ sendo $10$ por cento da maior distância, $\varepsilon=0,1r.$ A Figura \ref{retas} (a) amplia a reta para melhor discernirmos a mudança das cores. Em Figura \ref{retas} (b) ampliamos para $\varepsilon$ sendo a maior distância, $\varepsilon = r$ e na Figura \ref{retas} (c) ampliamos para $\varepsilon$ sendo dez vezes a maior distância, $\varepsilon = 10r.$ Nestes exemplos percebemos que para valores menores de $\varepsilon$ a ordem de distribuição das cores da hélice e da reta coincidem, para valores maiores as cores se invertem.
% Francisco mandou tirar em 08/01/14
\begin{figure}[!httb]
\centering
\includegraphics[scale=0.4]{LEhel10scat.png}
\caption{Uma hélice original junto da minúscula reta resultante da aplicação das autofunções do Laplaciano de $\re^3$ para $\re.$ O parâmetro $\varepsilon$ utilizado foi $10$ por cento da maior distância entre os pontos originais.}
\label{hel1D10}
\end{figure}
\end{comment}
Este experimento exibe a capacidade do algoritmo das autofunções do laplaciano de `desenrolar' a hélice, e tendencialmente reduzir a dimensionalidade do espaço que contém as suas características desde que seja escolhida uma vizinhança de tamanho adequado.
\begin{comment}
\todo{Acho que é melhor tirar estas retinhas tb.}
\begin{figure}
\centering
\subfigure[hel10reta][ $ \varepsilon = 0,1r$ ]{\includegraphics[scale=0.35]{helscat10.png}}
\subfigure[hel100reta][ $ \varepsilon = r$ ]{\includegraphics[scale=0.35]{helscat100.png}}
\subfigure[hel1000reta][ $ \varepsilon = 10r$ ]{\includegraphics[scale=0.35]{helscat1000.png}}
\caption{(a) Reta representativa da hélice em $\re^3$ após aplicação das autofunções do laplaciano com $\varepsilon$ sendo $10$ por cento da maior distância entre os dados de entrada. (b) O mesmo experimento para $\varepsilon = r.$ A ordem das cores se inverte em relação a hélice original. (c) A reta agora é resultado do $\varepsilon = 10r.$ A distribuição das cores para $\varepsilon$ maiores inverte a ordem das cores.}
\label{retas}
\end{figure}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%% FALO EM NORMALIZADOS E NÃO NORMALIZADOS ???????????%%%%%%%%%%%%%%%%%%%%%%%%%%
%Para comparar os resultados no caso de normalizarmos os dados de entrada acrescentamos a figura \ref{LEhelnor} a seguir.
%\begin{figure}[!httb]
%\centering
%\includegraphics[scale=0.7]{LEhel.png}
%\caption{A hélice com suas imagens em $\re,\re^2$ e $\re^3$ para dados normalizados.}
%\label{LEhelnor} % Para referenciar esta figura mais a frente caso sj necessário
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%% FIM DO COMENTÁRIO ACIMA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks