-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
2828 lines (2453 loc) · 201 KB
/
index.html
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
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 7.3.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.6.0/css/all.min.css" integrity="sha256-5eIC48iZUHmSlSUz9XtjRyK2mzQkHScZY1WdMaoz74E=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/5.0.31/fancybox/fancybox.css" integrity="sha256-gkQVf8UKZgQ0HyuxL/VnacadJ+D2Kox2TCEBuNQg5+w=" crossorigin="anonymous">
<script class="next-config" data-name="main" type="application/json">{"hostname":"chengmingbo.github.io","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.21.0","exturl":false,"sidebar":{"position":"right","width_expanded":320,"width_dual_column":240,"display":"always","padding":18,"offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},"hljswrap":true,"copycode":{"enable":false,"style":null},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"}}</script><script src="/js/config.js"></script>
<meta name="description" content="Mingbo">
<meta property="og:type" content="website">
<meta property="og:title" content="Mingbo">
<meta property="og:url" content="http://chengmingbo.github.io/index.html">
<meta property="og:site_name" content="Mingbo">
<meta property="og:description" content="Mingbo">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="Mingbo Cheng">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="http://chengmingbo.github.io/">
<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":true,"isPost":false,"lang":"zh-CN","comments":"","permalink":"","path":"index.html","title":""}</script>
<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>Mingbo</title>
<noscript>
<link rel="stylesheet" href="/css/noscript.css">
</noscript>
<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/style.css">
<!-- hexo injector head_end end --></head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<div class="column">
<header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<i class="logo-line"></i>
<h1 class="site-title">Mingbo</h1>
<i class="logo-line"></i>
</a>
<img class="custom-logo-image" src="/%5Bobject%20Object%5D" alt="Mingbo">
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger" aria-label="搜索" role="button">
</div>
</div>
</div>
<nav class="site-nav">
<ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="home fa-fw"></i>首页</a></li><li class="menu-item menu-item-slides"><a href="/slides/" rel="section"><i class="area-chart fa-fw"></i>slides</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a></li>
</ul>
</nav>
</header>
<aside class="sidebar">
<div class="sidebar-inner sidebar-overview-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">Mingbo Cheng</p>
<div class="site-description" itemprop="description">Mingbo</div>
</div>
<div class="site-state-wrap animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">20</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<span class="site-state-item-count">1</span>
<span class="site-state-item-name">分类</span>
</div>
<div class="site-state-item site-state-tags">
<span class="site-state-item-count">5</span>
<span class="site-state-item-name">标签</span>
</div>
</nav>
</div>
<div class="links-of-author animated">
<span class="links-of-author-item">
<a href="https://github.com/chengmingbo" title="GitHub → https://github.com/chengmingbo" rel="noopener me" target="_blank"><i class="github fa-fw"></i>GitHub</a>
</span>
</div>
</div>
</div>
</div>
<div class="sidebar-inner sidebar-blogroll">
<div class="links-of-blogroll animated">
<div class="links-of-blogroll-title"><i class="fa fa-globe fa-fw"></i>
链接
</div>
<ul class="links-of-blogroll-list">
<li class="links-of-blogroll-item">
<a href="https://deeplearningmath.org/supervised-machine-learning" title="https://deeplearningmath.org/supervised-machine-learning" rel="noopener" target="_blank">deeplearningmath</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://lilianweng.github.io/archives/" title="https://lilianweng.github.io/archives/" rel="noopener" target="_blank">Lil'Log</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://www.zybuluo.com/codeep/note/163962" title="https://www.zybuluo.com/codeep/note/163962" rel="noopener" target="_blank">mathjax grammar</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://vividfree.github.io/" title="http://vividfree.github.io/" rel="noopener" target="_blank">vividfree</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://colah.github.io/" title="http://colah.github.io/" rel="noopener" target="_blank">colah</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://www.autonlab.org/tutorials" title="https://www.autonlab.org/tutorials" rel="noopener" target="_blank">Andrew Moore</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://plot.ly/matlab/plot/" title="https://plot.ly/matlab/plot/" rel="noopener" target="_blank">matlabplot</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://www.ryanzhang.info/blog/" title="http://www.ryanzhang.info/blog/" rel="noopener" target="_blank">Ryan’s Cabinet</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://www.cnblogs.com/jerrylead/tag/Machine%20Learning/" title="http://www.cnblogs.com/jerrylead/tag/Machine%20Learning/" rel="noopener" target="_blank">JerryLead</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://yxzf.github.io/" title="https://yxzf.github.io/" rel="noopener" target="_blank">YXZF'S BLOG</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://vonng.com/" title="http://vonng.com" rel="noopener" target="_blank">VONNG</a>
</li>
</ul>
</div>
</div>
</aside>
</div>
<div class="main-inner index posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://chengmingbo.github.io/2023/05/10/from_laplacian_to_hodge_laplacian/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mingbo Cheng">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Mingbo">
<meta itemprop="description" content="Mingbo">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Mingbo">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2023/05/10/from_laplacian_to_hodge_laplacian/" class="post-title-link" itemprop="url">From graph laplacian to hodge laplacian</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2023-05-10 21:17:56" itemprop="dateCreated datePublished" datetime="2023-05-10T21:17:56+02:00">2023-05-10</time>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="preface">Preface</h2>
<p>Graph laplacian is familiar to computation science researcher, with
which we can perform spectral analysis such as diffusion map, eigenmap
or spectral clustering. Here, we discuss how to generalize the graph
laplacian to it's high-order form, i.e., Hodge laplacian.</p>
<h2 id="graph-laplacian">Graph laplacian</h2>
<p>In the previous post we know that the graph laplacian can be obtianed
by degree matrix <span class="math inline">\(D\)</span> and adjacency
matrix <span class="math inline">\(A\)</span> such that: <span
class="math display">\[\begin{equation}
L_0 = D - A
\end{equation}\]</span></p>
<p>We can find the adjacency matrix and degree matrix of the graph blow
with nine vertices: <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/hodge_graph_9_nodes.svg" /></p>
<p>such that:</p>
<p><span class="math display">\[\begin{equation}
A = \begin{array}[r]{c |c c c c c c c c c }
& 1 & 2 & 3 & 4 & 5 & 6 & 7 &
8 & 9\\
\hline
1& 0 & 1 & 0 & 0 & 0 & 0 & 0
& 0 & 0\\
2& 1 & 0 & 1 & 0 & 0 & 0 & 0
& 0 & 0\\
3& 0 & 1 & 0 & 0 & 0 & 0 & 0
& 0 & 0\\
4& 0 & 0 & 0 & 0 & 1 & 1 & 0
& 0 & 0\\
5& 0 & 0 & 0 & 1 & 0 & 1 & 0
& 0 & 0\\
6& 0 & 0 & 0 & 1 & 1 & 0 & 1
& 0 & 0\\
7& 0 & 0 & 0 & 0 & 0 & 1 & 0
& 0 & 0\\
8& 0 & 0 & 0 & 0 & 0 & 0 & 0
& 0 & 1\\
9& 0 & 0 & 0 & 0 & 0 & 0 & 0
& 1 & 0\\
\end{array}
\end{equation}\]</span></p>
<p>and</p>
<p><span class="math display">\[\begin{equation}
D = \begin{array}[r]{c |c c c c c c c c c }
& 1 & 2 & 3 & 4 & 5 & 6 & 7 &
8 & 9\\
\hline
1& 1 & 0 & 0 & 0 & 0 & 0 & 0
& 0 & 0\\
2& 0 & 2 & 0 & 0 & 0 & 0 & 0
& 0 & 0\\
3& 0 & 0 & 1 & 0 & 0 & 0 & 0
& 0 & 0\\
4& 0 & 0 & 0 & 2 & 0 & 0 & 0
& 0 & 0\\
5& 0 & 0 & 0 & 0 & 2 & 0 & 0
& 0 & 0\\
6& 0 & 0 & 0 & 0 & 0 & 3 & 0
& 0 & 0\\
7& 0 & 0 & 0 & 0 & 0 & 0 & 1
& 0 & 0\\
8& 0 & 0 & 0 & 0 & 0 & 0 & 0
& 1 & 0\\
9& 0 & 0 & 0 & 0 & 0 & 0 & 0
& 0 & 1\\
\end{array}
\end{equation}\]</span></p>
<p>And the graph laplacian thus can be calculated as:</p>
<p><span class="math display">\[\begin{equation}
L_0 = D - A = \begin{array}[r]{c |c c c c c c c c c }
& 1 & 2 & 3 & 4 & 5 & 6 & 7 &
8 & 9\\
\hline
1& 1 & -1 & 0 & 0 & 0 & 0 & 0
& 0 & 0\\
2& -1 & 2 & -1 & 0 & 0 & 0 & 0
& 0 & 0\\
3& 0 & -1 & 1 & 0 & 0 & 0 & 0
& 0 & 0\\
4& 0 & 0 & 0 & 2 & -1 & -1 & 0
& 0 & 0\\
5& 0 & 0 & 0 & -1 & 2 & -1 & 0
& 0 & 0\\
6& 0 & 0 & 0 & -1 & -1 & 3 & -1
& 0 & 0\\
7& 0 & 0 & 0 & 0 & 0 & -1 & 1
& 0 & 0\\
8& 0 & 0 & 0 & 0 & 0 & 0 & 0
& 1 & -1\\
9& 0 & 0 & 0 & 0 & 0 & 0 & 0
& -1 & 1\\
\end{array}
\end{equation}\]</span></p>
<p>However, there's anoth way to represent the graph laplacian. Before
that, we first introduce the incidence matrix of a graph. First, we can
convert an undirected graph to be directed just assign the direction of
edges by book keeping order. Next, let's construct the incidence matrix,
each row represent a vertex, and each colum is an edge. We set the entry
to be 1 if the the edge enter the vertex -1 when leave the vertex. Set 0
if there's no connection between a vertex and an edge. Thus the
incidence matrix of a graph <span class="math inline">\(G\)</span> is
<span class="math inline">\(B\)</span> such that: <span
class="math display">\[\begin{equation}
B_1 =
\begin{array}[r]{c | c c c c c c c}
& \cdots & [4,5] & [4,6]& [5,6]&
[6,7]& \cdots\\
\hline
\vdots & \cdots & & \cdots & &
\cdots & \\
4 & \cdots & -1 & -1 & 0 & 0
& \cdots\\
5 & \cdots & 1 & 0 & -1 & 0 &
\cdots\\
6 & \cdots & 0 & 1 & 1 & -1 &
\cdots\\
7 & \cdots & 0 & 0 & 0 & 1 &
\cdots\\
\vdots & \cdots & & \cdots & &
\cdots & \\
\end{array}
\end{equation}\]</span> Next, let construct graph laplacian matrix using
<span class="math inline">\(B_1\)</span>. Actually, the graph laplacian
is： <span class="math display">\[\begin{equation}
L_0=B_1 B_1^\top = \begin{array}[r]{c |c c c c c c c c c }
& 1 & 2 & 3 & 4 & 5 & 6 & 7 &
8 & 9\\
\hline
1& 1 & -1 & 0 & 0 & 0 & 0 & 0
& 0 & 0\\
2& -1 & 2 & -1 & 0 & 0 & 0 & 0
& 0 & 0\\
3& 0 & -1 & 1 & 0 & 0 & 0 & 0
& 0 & 0\\
4& 0 & 0 & 0 & 2 & -1 & -1 & 0
& 0 & 0\\
5& 0 & 0 & 0 & -1 & 2 & -1 & 0
& 0 & 0\\
6& 0 & 0 & 0 & -1 & -1 & 3 & -1
& 0 & 0\\
7& 0 & 0 & 0 & 0 & 0 & -1 & 1
& 0 & 0\\
8& 0 & 0 & 0 & 0 & 0 & 0 & 0
& 1 & -1\\
9& 0 & 0 & 0 & 0 & 0 & 0 & 0
& -1 & 1\\
\end{array}
\end{equation}\]</span> As we can see that, <span
class="math inline">\(L_0\)</span> is the same as the that obtained from
degree matrix and adjacency matrix.</p>
<h2 id="zero-eigenvaules-of-graph-laplacian">Zero eigenvaules of graph
laplacian</h2>
<p>We know that for the application of diffusion map or spectral
analysis, we have to drop the first eigenvector due to its same values
and the eigenvaule is 0. The second eigenvector is also called fidler
vector. However, these applications usually created a connected graph.
Since the graph we show here is an unconnected graph. We can stop here
to take a guess: Is the zero eigenvaule still there, or if so, how many
zero eigenvaules?</p>
<p>Now, let's perform the eigenvaule decomposition that: <span
class="math display">\[\begin{equation}
L_0 = Q\Lambda Q^\top
\end{equation}\]</span></p>
<p>Interestingly, the top 3 eigenvalues are all zero and we also have 3
connected components in the graph. Is this a coincidence or a property
of graph laplacian decomposition? <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/hodge_graph_9_nodes_eigenvalues.svg" /></p>
<p>Furthermore, the top 3 eigenvectors corresponding to the zero
eigenvaules are also interesting. Notice that the first eigenvector can
differentiate the components <span
class="math inline">\(\{4,5,6,7\}\)</span> from the rest vectices.
Likewise, the second eigenvector select the connected component <span
class="math inline">\(\{8,9\}\)</span> and the third choose the
component <span class="math inline">\(\{1,2,3\}\)</span>. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/hodge_graph_9_nodes_eigenvectors.svg" /></p>
<p>In fact, in the field of Topological Data Analysis (TDA), the <span
class="math inline">\(L_0\)</span> is the special case of hodge
laplacian (<span class="math inline">\(L_k\)</span>). The number of
connected components is call 0-dimensional cycles. And the graph
laplaican can capture these cycles. The 1-dimensional cycles are
correspond to holes, we will go into detail in the next section.</p>
<h2 id="hodge-laplacian">Hodge laplacian</h2>
<p>We can see the graph laplacian zero-order of hodge laplacian, and the
formalu can be represented as: <span
class="math display">\[\begin{equation}
L_0 = \mathbf{0}^\top \mathbf{0} + B_1 B_1^\top
\end{equation}\]</span></p>
<p>Similarly, we can obtian <span
class="math inline">\(L_1\)</span>:</p>
<p><span class="math display">\[\begin{equation}
L_1 = B_1^\top B_1 + B_2 B_2^\top
\end{equation}\]</span></p>
<p>You must ask where is <span class="math inline">\(B_2\)</span> coming
from? We know that <span class="math inline">\(B_1\)</span> captures the
relationship between vertices and edges. Thus, <span
class="math inline">\(B_2\)</span> captures the relationship between
edges and triangles. We can also define <span
class="math inline">\(B_3\)</span> to capture relationship between
triangles and tetrahedron and so on and so forth. So what is a triangle
or a tetrahedron in a graph? We would not go into the detail of the
thory of Simplex and Simplicial complex. Here we just need to know that
three connected vertices forms a triangle. Similarly, four connected
vertices forms a tetrahedron which is a high-order of triangles. To
define <span class="math inline">\(B_2\)</span>, of a graph <span
class="math inline">\(G\)</span>, we would check the direction of an
edge <span class="math inline">\(e_j\)</span> to the triangle <span
class="math inline">\(\bigtriangleup_q\)</span> it beblongs, if it has
the same direction as the triangle, the entry would be <span
class="math inline">\(1\)</span>, if the direction is opposite, the
entry would be -1, otherwise the entry would be zero. Specifically:</p>
<p><span class="math display">\[\begin{equation}
{B}_2[j, q] =
\begin{cases}
1 & \text{if } e_j \in \bigtriangleup_q \quad \text{with}\quad
\text{same}\quad \text{direction} \\
-1 & \text{if } e_j \in \bigtriangleup_q \quad \text{with}\quad
\text{opposite}\quad \text{direction} \\
0 & \text{otherwise}
\end{cases}
\end{equation}\]</span></p>
<p>With the definition, we can obtian <span
class="math inline">\(B_2\)</span> of the graph aforementioned: <span
class="math display">\[\begin{equation}
B_2 =
\begin{array}[r]{c | c }
& [4,5,6]\\
\hline
\vdots & \cdots \\
[4,5] & 1\\
[4,6] & -1\\
[5,6]& 1\\
[6,7] & 0\\
\vdots & \cdots \\
\end{array}
\end{equation}\]</span></p>
<p>We next introduce the normalized form and the decomposition of hodge
1-laplacian. The normalized form of hodge 1-laplacian is given:</p>
<p><span class="math display">\[\begin{equation}
\mathcal{L}_1 = {D}_2 {B}_1^\top {D}_1^{-1} {B}_1 + {B}_2 {D}_3
{B}_2^\top {D}_2^{-1}
\end{equation}\]</span> where <span
class="math inline">\(\mathbf{D}_1\)</span> is the vertices degree
matrix, <span class="math inline">\({D}_2\)</span> is <span
class="math inline">\(\max{(\text{diag}(|{B}_2| \mathbf{1}),
\mathbf{I})}\)</span> and <span class="math inline">\({D}_3\)</span> is
<span class="math inline">\(\frac{1}{3}\mathbf{I}\)</span>. Since the
normalized <span class="math inline">\(L_1\)</span> is not neccessarily
symmetric, we next need to define the symmetric normalized Hodge
1-Laplacian such that: <span class="math display">\[\begin{equation}
\begin{aligned}
\mathcal{L}_1^s
& = {D}_2^{-1/2} \mathcal{L}_1 {D}_2^{1/2}\\
& = {D}_2^{1/2} {B}_1^\top {D}_1^{-1} {B}_1 {D}_2^{1/2} +
{D}^{-1/2} {B}_2 {D}_3 {B}_2^\top {D}_2^{-1/2}
\end{aligned}
\end{equation}\]</span></p>
<p>We use the graph with three holes to present hodge 1-laplacian: <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/hodge_graph_3holes.svg" /></p>
<p>We next can perform eigenvalues decomposition on <span
class="math inline">\(\mathcal{L}_1\)</span>: <span
class="math display">\[\begin{equation}
\begin{aligned}
\mathcal{L}_1
& = \mathbf{D}_2^{1/2} \mathcal{L}_1^s
\mathbf{D}_2^{-1/2} \\
& = \mathbf{D}_2^{1/2} Q \Lambda Q^\top
\mathbf{D}_2^{-1/2} \\
& = \mathbf{U} \Lambda \mathbf{U}^{-1}
\end{aligned}
\end{equation}\]</span> Interestingly, the top 3 eigenvector also all
zero which corresponding to the 3 holes, namely, the three 1-dimensional
cycles. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/hodge_graph_3holes_eigenvalues.svg" /></p>
<p>When it comes to the eigenvectors, we can also notice that the top
three eigenvectors are around the three holes. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/hodge_graph_3holes_eigenvectors.svg" /></p>
<p>In algebraic geometry, these the eigenvectors with zero eigenvaules
are called harmonic function or harmonic. These harmonic function around
holes is useful for some analysis like clustering to find the
1-dimensional cycles etc.</p>
<h2 id="conclusion">Conclusion</h2>
<p>Today, we review the graph laplacian, and we can find the zeor
eigenvalues and theirs corresponding eigenvectors can be used to find
connected components. The high order graph laplacian hodge laplacian
have the similar properties, we presented the hodge 1-laplaican and its
eigenvalues decomposition. We can find that the zero eigenvalues
indicates the number of holes of a graph. Furthermore, the corresponding
eigenvectors with zero eigenvalues are around holes.</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://chengmingbo.github.io/2020/12/07/spectral_2/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mingbo Cheng">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Mingbo">
<meta itemprop="description" content="Mingbo">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Mingbo">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/07/spectral_2/" class="post-title-link" itemprop="url">Spectral analysis (2)</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-12-07 21:10:01" itemprop="dateCreated datePublished" datetime="2020-12-07T21:10:01+01:00">2020-12-07</time>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="diffussion-map">Diffussion map</h2>
<p>Eigenvalue decomposition of weighted graph laplacian is used to
obtain diffusion map. The asymmetric matrix or transition matrix <span
class="math inline">\(P=D^{-1}W\)</span>. The decomposition is: <span
class="math display">\[\begin{equation}
P = D^{-1/2}S\Lambda S^\top D^{1/2}
\end{equation}\]</span> In fact, the random walk on the graph would give
rise to the transition graph such that: <span
class="math display">\[\begin{equation}
p^{t+1}= p^t D^{-1}W = p^t P
\end{equation}\]</span> where <span class="math inline">\(p\)</span> is
a initial state of the graph (vertices weight). That is, after a certain
step of random walk on the graph, we would reach a steady state when any
more random walk would not change the weight. Let <span
class="math inline">\(Q=D^{-1/2}S\)</span>, then <span
class="math inline">\(Q^{-1}=S^{\top} D^{1/2}\)</span>, we can derive
<span class="math inline">\(P = Q\Lambda Q^{-1}\)</span>. The random
walk above mentioned can then be represent: <span
class="math display">\[\begin{equation}
\begin{aligned}
P^t &= Q\Lambda Q^{-1}Q\Lambda Q^{-1}\cdots Q\Lambda Q^{-1}
&= Q\Lambda^t Q
\end{aligned}
\end{equation}\]</span> Since <span
class="math inline">\(\Lambda\)</span> is diagnoal, the random walk on a
graph can be easily cacluted by using the eigenvalue decomposition
outcome. The column of <span class="math inline">\(Q\)</span> is the
diffusion map dimensions.</p>
<h2 id="diffusion-map-example">Diffusion map example</h2>
<p>To understand diffusion map, we here introduce an example data and
run diffusion map on it. The data is a single cell fibroblasts to neuron
data with 392 cells. We first download the data from NCBI and loaded the
data to memory:</p>
<figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">import requests</span><br><span class="line">url <span class="operator">=</span> <span class="string">'https://www.ncbi.nlm.nih.gov/geo/download/?acc=GSE67310&format=file&file=GSE67310%5FiN%5Fdata%5Flog2FPKM%5Fannotated.txt.gz'</span></span><br><span class="line">r <span class="operator">=</span> requests.get<span class="punctuation">(</span>url<span class="punctuation">,</span> allow_redirects<span class="operator">=</span>True<span class="punctuation">)</span></span><br><span class="line">open<span class="punctuation">(</span><span class="string">'GSE67310.txt.gz'</span><span class="punctuation">,</span> <span class="string">'wb'</span><span class="punctuation">)</span>.write<span class="punctuation">(</span>r.content<span class="punctuation">)</span></span><br><span class="line">data <span class="operator">=</span> pd.read_csv<span class="punctuation">(</span><span class="string">'GSE67310.txt.gz'</span><span class="punctuation">,</span> sep<span class="operator">=</span><span class="string">'\t'</span><span class="punctuation">,</span> index_col<span class="operator">=</span><span class="number">0</span><span class="punctuation">)</span></span><br><span class="line">data <span class="operator">=</span> data.loc<span class="punctuation">[</span>data<span class="punctuation">[</span><span class="string">'assignment'</span><span class="punctuation">]</span> <span class="operator">!=</span><span class="string">'Fibroblast'</span><span class="punctuation">]</span></span><br><span class="line">group <span class="operator">=</span> data<span class="punctuation">[</span><span class="string">'assignment'</span><span class="punctuation">]</span></span><br></pre></td></tr></table></figure>
<p>From the code as we can see that, we extract the cell types from the
data and stores it into the variable <code>group</code>. The rest part
of the data is the normalized gene expression count matrix.</p>
<p>To do the pre-processing, we first get the log-normalized count
matrix <span class="math inline">\(X\)</span> and revert it to the
counts and apply log geomatric scaling to the count matrix as the
pre-processing then store it to matrix <span
class="math inline">\(Y\)</span>. <figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">X <span class="operator">=</span> np.array<span class="punctuation">(</span>data.iloc<span class="punctuation">[</span><span class="operator">:</span><span class="punctuation">,</span> <span class="number">5</span><span class="operator">:</span><span class="punctuation">]</span><span class="punctuation">)</span>.T</span><br><span class="line">X <span class="operator">=</span> np.power<span class="punctuation">(</span><span class="number">2</span><span class="punctuation">,</span> X<span class="punctuation">[</span>np.apply_along_axis<span class="punctuation">(</span>np.var<span class="punctuation">,</span> <span class="number">1</span><span class="punctuation">,</span> X<span class="punctuation">)</span><span class="operator">></span><span class="number">0</span><span class="punctuation">,</span> <span class="operator">:</span><span class="punctuation">]</span><span class="punctuation">)</span> <span class="operator">-</span> <span class="number">1</span></span><br><span class="line">Y <span class="operator">=</span> np.log<span class="punctuation">(</span>gscale<span class="punctuation">(</span>X<span class="operator">+</span><span class="number">0.5</span><span class="punctuation">)</span><span class="punctuation">)</span>.T</span><br></pre></td></tr></table></figure> The geomatric scaling
implementation is: <figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">def gscale<span class="punctuation">(</span>X<span class="operator">:</span>np.ndarray<span class="punctuation">)</span> <span class="operator">-></span> np.ndarray<span class="operator">:</span></span><br><span class="line"> assert<span class="punctuation">(</span>X.all<span class="punctuation">(</span><span class="punctuation">)</span><span class="operator">>=</span><span class="number">0</span><span class="punctuation">)</span></span><br><span class="line"> div_ <span class="operator">=</span> np.divide<span class="punctuation">(</span>X.T<span class="punctuation">,</span> np.apply_along_axis<span class="punctuation">(</span>lambda x<span class="operator">:</span>np.exp<span class="punctuation">(</span>np.mean<span class="punctuation">(</span>np.log<span class="punctuation">(</span>x<span class="punctuation">)</span><span class="punctuation">)</span><span class="punctuation">)</span><span class="punctuation">,</span> <span class="number">1</span><span class="punctuation">,</span></span><br><span class="line"> X<span class="punctuation">)</span><span class="punctuation">)</span>.T</span><br><span class="line"> scale_ <span class="operator">=</span> np.apply_along_axis<span class="punctuation">(</span>np.median<span class="punctuation">,</span><span class="number">0</span><span class="punctuation">,</span> div_<span class="punctuation">)</span></span><br><span class="line"> sc <span class="operator">=</span> StandardScaler<span class="punctuation">(</span>with_mean<span class="operator">=</span>False<span class="punctuation">)</span></span><br><span class="line"> sc.fit<span class="punctuation">(</span>X<span class="punctuation">)</span></span><br><span class="line"> sc.scale_ <span class="operator">=</span> scale_</span><br><span class="line"> <span class="built_in">return</span> sc.transform<span class="punctuation">(</span>X<span class="punctuation">)</span></span><br></pre></td></tr></table></figure> After the pre-processing, we we next
run PCA to perform dimensionality reduction and use which to calculate
euclidean distances between cells, and then run diffusion map.</p>
<figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">pc <span class="operator">=</span> run_pca<span class="punctuation">(</span>Y<span class="punctuation">,</span> <span class="number">100</span><span class="punctuation">)</span></span><br><span class="line">R <span class="operator">=</span> distance_matrix<span class="punctuation">(</span>pc<span class="punctuation">,</span> pc<span class="punctuation">)</span></span><br><span class="line">d <span class="operator">=</span> diffusionMaps<span class="punctuation">(</span>R<span class="punctuation">,</span><span class="number">7</span><span class="punctuation">)</span></span><br></pre></td></tr></table></figure>
<p>We first take a look at the PCA figure which shows the first 2 PCs of
the dataset. PCA is a linear methods which cannot reflect cell fate
differentation process. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/fib2neuron_pca.png" />
Since the diffusion map applied the Gaussian kernal during the distances
calculation, it usually a better way to capture the cell differentation
events. Here we show diffusion dimension 1,2 and 1,3. It's clear that
1,2 captures the cell differentation from fibroblasts to neuron, and 1,3
captures the differentiation from firoblasts to myocytes. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/fib2neuron_diffusions.png" /></p>
<p>We can change the bandwidth from 7 to 100, which use the 100th
neareast neighbor as bandwidth instead of 7th. The following shows the
diffusion map that bandwidth=100. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/fib2neuron_bandwidth100.png" /></p>
<h2 id="pseudo-time-by-random-walk">pseudo time by random walk</h2>
<p>The eigenvalue decomposition of graph laplacian can also be used to
infer the pseudo time simulating the pseudo time of cell differentation
events. We here set top <span class="math inline">\(m\)</span> cells
<span class="math inline">\(1/m\)</span> of the progenitor cells (MEF)
and set other cell 0 as the initial state. Next, we perform random walk
to get new pesudotime <span class="math inline">\(u\)</span> such that:
<span class="math display">\[\begin{equation}
u = [\frac{1}{m}, \frac{1}{m}, \cdots, 0, \cdots 0](D^{-1}W)^t
\end{equation}\]</span> By testing different number of random walk steps
we can check the new pseudo time <span class="math inline">\(u\)</span>.
Here we show time step equals to 1, 10, 100 and 200. From the figure we
can notice that after certain step, the pseudo time will not change
anymore. That means the random walk reaches the steady state. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/fib2neuron_pseudotime.png" /></p>
<p>To test when can we reach the steady state, I use the graph we
mentioned in my last post <a
href="https://chengmingbo.github.io/2020/06/07/spectral/">Spectral
analysis (1)</a>:
<img src="https://cmb.oss-cn-qingdao.aliyuncs.com/a_graph.png" height="250px"></p>
<p>Here we random generate two initial states (<span
class="math inline">\(v_1\)</span>, <span
class="math inline">\(v_2\)</span>) to do the random walk such that:
<span class="math display">\[\begin{equation}
\begin{aligned}
v_1 &= [0.15,0.41,0.54,0.9,0.62,0.93,0.1,0.46,0.01,0.88]\\
v_2 &= [0.89,0.93,0.07,0.41,0.52,0.88,0.43,0.09,0.1,0.2]
\end{aligned}
\end{equation}\]</span></p>
<p>From the the figure below we can see that <span
class="math inline">\(v_1\)</span> reaches the steady state in 30 steps
whereas <span class="math inline">\(v_2\)</span> reaches steady state in
100 steps. In total, all these two initial state will reach the steady
state that would not change any longer. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/fib2neuron_steady.png" /></p>
<h2 id="spectral-clustering">spectral clustering</h2>
<p>The eigenvectors of graph Laplacian can also be used to do the
clustering. From the figure we can find clear cut using the 1st, 2nd and
the 3rd diffusion dimensions. In practice, we can use kmeans, DBSCAN,
leiden, louvain algorithm to perform clustering using the diffusion
dimensions. <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/fib2neuron_clustering.png" /></p>
<h2 id="appendix">Appendix</h2>
<h5 id="pca-function">PCA function</h5>
<figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">def run_pca<span class="punctuation">(</span>mtx<span class="punctuation">,</span> n_components<span class="operator">=</span><span class="number">2</span><span class="punctuation">,</span> random_state<span class="operator">=</span><span class="number">2022</span><span class="punctuation">)</span><span class="operator">:</span></span><br><span class="line"> dm <span class="operator">=</span> None</span><br><span class="line"> <span class="keyword">if</span> scipy.sparse.issparse<span class="punctuation">(</span>mtx<span class="punctuation">)</span><span class="operator">:</span></span><br><span class="line"> clf <span class="operator">=</span> TruncatedSVD<span class="punctuation">(</span>n_components<span class="punctuation">,</span> random_state<span class="operator">=</span>random_state<span class="punctuation">)</span></span><br><span class="line"> dm <span class="operator">=</span> clf.fit_transform<span class="punctuation">(</span>mtx<span class="punctuation">)</span></span><br><span class="line"> <span class="keyword">else</span><span class="operator">:</span></span><br><span class="line"> pca <span class="operator">=</span> PCA<span class="punctuation">(</span>n_components<span class="operator">=</span>n_components<span class="punctuation">,</span> random_state<span class="operator">=</span>random_state<span class="punctuation">)</span></span><br><span class="line"> dm <span class="operator">=</span> pca.fit_transform<span class="punctuation">(</span>mtx<span class="punctuation">)</span></span><br><span class="line"> <span class="built_in">return</span> dm</span><br></pre></td></tr></table></figure>
<h5 id="affinity-matrix-function">Affinity matrix function</h5>
<figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">def affinity<span class="punctuation">(</span>R<span class="punctuation">,</span> k<span class="operator">=</span><span class="number">7</span><span class="punctuation">,</span> sigma<span class="operator">=</span>None<span class="punctuation">,</span> <span class="built_in">log</span><span class="operator">=</span>False<span class="punctuation">)</span><span class="operator">:</span></span><br><span class="line"> <span class="string">""</span><span class="string">"</span></span><br><span class="line"><span class="string"> Gaussian affinity matrix constructor</span></span><br><span class="line"><span class="string"> W = exp(-r_{ij}^2/sigma)</span></span><br><span class="line"><span class="string"> "</span><span class="string">""</span></span><br><span class="line"> def top_k<span class="punctuation">(</span>lst<span class="punctuation">,</span> k<span class="operator">=</span><span class="number">1</span><span class="punctuation">)</span><span class="operator">:</span></span><br><span class="line"> assert<span class="punctuation">(</span>len<span class="punctuation">(</span>lst<span class="punctuation">)</span> <span class="operator">></span>k<span class="punctuation">)</span></span><br><span class="line"> <span class="built_in">return</span> np.partition<span class="punctuation">(</span>lst<span class="punctuation">,</span> k<span class="punctuation">)</span><span class="punctuation">[</span>k<span class="punctuation">]</span></span><br><span class="line"></span><br><span class="line"> R <span class="operator">=</span> np.array<span class="punctuation">(</span>R<span class="punctuation">)</span></span><br><span class="line"> <span class="keyword">if</span> not sigma<span class="operator">:</span></span><br><span class="line"> s <span class="operator">=</span> <span class="punctuation">[</span>top_k<span class="punctuation">(</span>R<span class="punctuation">[</span><span class="operator">:</span><span class="punctuation">,</span> i<span class="punctuation">]</span><span class="punctuation">,</span> k<span class="operator">=</span>k<span class="punctuation">)</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span><span class="punctuation">(</span>R.shape<span class="punctuation">[</span><span class="number">1</span><span class="punctuation">]</span><span class="punctuation">)</span><span class="punctuation">]</span></span><br><span class="line"> S <span class="operator">=</span> np.sqrt<span class="punctuation">(</span>np.outer<span class="punctuation">(</span>s<span class="punctuation">,</span> s<span class="punctuation">)</span><span class="punctuation">)</span></span><br><span class="line"> <span class="keyword">else</span><span class="operator">:</span></span><br><span class="line"> S <span class="operator">=</span> sigma</span><br><span class="line"> logW <span class="operator">=</span> <span class="operator">-</span>np.power<span class="punctuation">(</span>np.divide<span class="punctuation">(</span>R<span class="punctuation">,</span> S<span class="punctuation">)</span><span class="punctuation">,</span> <span class="number">2</span><span class="punctuation">)</span></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">log</span><span class="operator">:</span></span><br><span class="line"> <span class="built_in">return</span> logW</span><br><span class="line"> <span class="built_in">return</span> np.exp<span class="punctuation">(</span>logW<span class="punctuation">)</span></span><br></pre></td></tr></table></figure>
<h5 id="diffusion-map-function">Diffusion map function</h5>
<figure class="highlight r"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">def diffusionMaps<span class="punctuation">(</span>R<span class="punctuation">,</span>k<span class="operator">=</span><span class="number">7</span><span class="punctuation">,</span>sigma<span class="operator">=</span>None<span class="punctuation">)</span><span class="operator">:</span></span><br><span class="line"> <span class="string">""</span><span class="string">"</span></span><br><span class="line"><span class="string"> Diffusion map(Coifman, 2005)</span></span><br><span class="line"><span class="string"> https://en.wikipedia.org/wiki/Diffusion_map</span></span><br><span class="line"><span class="string"> ----------</span></span><br><span class="line"><span class="string"> dic:</span></span><br><span class="line"><span class="string"> psi: right eigvector of P = D^{-1/2} * evec</span></span><br><span class="line"><span class="string"> phi: left eigvector of P = D^{1/2} * evec</span></span><br><span class="line"><span class="string"> eig: eigenvalues</span></span><br><span class="line"><span class="string"> "</span><span class="string">""</span></span><br><span class="line"> k<span class="operator">=</span>k<span class="operator">-</span><span class="number">1</span> <span class="comment">## k is R version minus 1 for the index</span></span><br><span class="line"> logW <span class="operator">=</span> affinity<span class="punctuation">(</span>R<span class="punctuation">,</span>k<span class="punctuation">,</span>sigma<span class="punctuation">,</span><span class="built_in">log</span><span class="operator">=</span>True<span class="punctuation">)</span></span><br><span class="line"> rs <span class="operator">=</span> np.exp<span class="punctuation">(</span><span class="punctuation">[</span>logsumexp<span class="punctuation">(</span>logW<span class="punctuation">[</span>i<span class="punctuation">,</span><span class="operator">:</span><span class="punctuation">]</span><span class="punctuation">)</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span><span class="punctuation">(</span>logW.shape<span class="punctuation">[</span><span class="number">0</span><span class="punctuation">]</span><span class="punctuation">)</span><span class="punctuation">]</span><span class="punctuation">)</span> <span class="comment">## dii=\sum_j</span></span><br><span class="line"> w_<span class="punctuation">{</span>i<span class="punctuation">,</span>j<span class="punctuation">}</span></span><br><span class="line"> D <span class="operator">=</span> np.diag<span class="punctuation">(</span>np.sqrt<span class="punctuation">(</span>rs<span class="punctuation">)</span><span class="punctuation">)</span></span><br><span class="line"> <span class="comment">## D^{1/2}</span></span><br><span class="line"> Dinv <span class="operator">=</span> np.diag<span class="punctuation">(</span><span class="number">1</span><span class="operator">/</span>np.sqrt<span class="punctuation">(</span>rs<span class="punctuation">)</span><span class="punctuation">)</span> <span class="comment">##D^{-1/2}</span></span><br><span class="line"> Ms <span class="operator">=</span> Dinv <span class="operator">@</span> np.exp<span class="punctuation">(</span>logW<span class="punctuation">)</span> <span class="operator">@</span> Dinv <span class="comment">## D^{-1/2} W D^{-1/2}</span></span><br><span class="line"> e <span class="operator">=</span> np.linalg.eigh<span class="punctuation">(</span>Ms<span class="punctuation">)</span> <span class="comment">## eigen decomposition of P'</span></span><br><span class="line"> evalue<span class="operator">=</span> e<span class="punctuation">[</span><span class="number">0</span><span class="punctuation">]</span><span class="punctuation">[</span><span class="operator">::</span><span class="operator">-</span><span class="number">1</span><span class="punctuation">]</span></span><br><span class="line"> evec <span class="operator">=</span> np.flip<span class="punctuation">(</span>e<span class="punctuation">[</span><span class="number">1</span><span class="punctuation">]</span><span class="punctuation">,</span> axis<span class="operator">=</span><span class="number">1</span><span class="punctuation">)</span></span><br><span class="line"> s <span class="operator">=</span> np.sum<span class="punctuation">(</span>np.sqrt<span class="punctuation">(</span>rs<span class="punctuation">)</span> <span class="operator">*</span> evec<span class="punctuation">[</span><span class="operator">:</span><span class="punctuation">,</span><span class="number">0</span><span class="punctuation">]</span><span class="punctuation">)</span> <span class="comment"># scaling</span></span><br><span class="line"> <span class="comment"># Phi is orthonormal under the weighted inner product</span></span><br><span class="line"> <span class="comment">#0:Psi, 1:Phi, 2:eig</span></span><br><span class="line"> dic <span class="operator">=</span> <span class="punctuation">{</span><span class="string">'psi'</span><span class="operator">:</span>s <span class="operator">*</span> Dinv<span class="operator">@</span>evec<span class="punctuation">,</span> <span class="string">'phi'</span><span class="operator">:</span> <span class="punctuation">(</span><span class="number">1</span><span class="operator">/</span>s<span class="punctuation">)</span><span class="operator">*</span>D<span class="operator">@</span>evec<span class="punctuation">,</span> <span class="string">"eig"</span><span class="operator">:</span> evalue<span class="punctuation">}</span></span><br><span class="line"> <span class="built_in">return</span> dic</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://chengmingbo.github.io/2020/06/07/spectral/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mingbo Cheng">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Mingbo">
<meta itemprop="description" content="Mingbo">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Mingbo">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/06/07/spectral/" class="post-title-link" itemprop="url">Spectral analysis (1)</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-06-07 18:30:22" itemprop="dateCreated datePublished" datetime="2020-06-07T18:30:22+02:00">2020-06-07</time>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="introduction">Introduction</h2>
<p>Newton used glass separted the white sunlight into red, orange,
yellow, green, blue, indigo and violet single colors. The light spectrum
analysis can help scientists to interpret the world. For example, we can
detect the elements of our solar system as well as far stars in the
universe. The spectrum analysis is also a field in mathmatjics. In the
graph thoery field, Laplacian matrix is used to represented a graph. We
can obtian features from the undirected graph below (<a
target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Laplacian_matrix">wikipedia</a>).
<img src="https://cmb.oss-cn-qingdao.aliyuncs.com/a_graph.png" height="300px"></p>
<p>For example, we can check the degree of each vertex, which forms our
Degree matrix <span class="math inline">\(D\)</span> such that: <span
class="math display">\[\begin{equation}
D = \begin{pmatrix}
2 & 0 & 0 & 0 & 0 & 0\\
0 & 3 & 0 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0 & 0\\
0 & 0 & 0 & 3 & 0 &0\\
0 & 0 & 0 & 0 & 3 & 0\\
0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
\end{equation}\]</span></p>
<p>By checking the connection between all pairs nodes, we can create a
Adjacency matrix:</p>
<p><span class="math display">\[\begin{equation}
A = \begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 &1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{pmatrix}
\end{equation}\]</span></p>
<h2 id="graph-laplacian">graph laplacian</h2>
<p>The graph Laplacian <span class="math inline">\(L\)</span> extracts
all useful information from a graph which is: <span
class="math display">\[\begin{equation}
L=D-A =\begin{pmatrix}
2 & -1 & 0 & 0 & -1 & 0\\
-1 & 3 & -1 & 0 & -1 & 0\\
0 & -1 & 2 & -1 & 0 & 0\\
0 & 0 & -1 & 3 & -1 & -1\\
-1 & -1 & 0 & -1 & 3 & 0\\
0 & 0 & 0 & -1 & 0 & 1
\end{pmatrix}
\end{equation}\]</span></p>
<p>In fact, the graph Laplaican matrix is symmetric and also positive
semidefinite (PSD), which means if we perform eigenvalue decomposition,
the eigen values are all real and nonnegative. We can normlize the graph
Laplaican by left multiplying the <span
class="math inline">\(D^{-1}\)</span> which will give rise to all <span
class="math inline">\(1\)</span>s of the diagnal entries of the matrix,
namely: <span class="math display">\[\begin{equation}
\text{norm}({L}) = D^{-1}L = \begin{pmatrix}1 & -0.50 & 0
& 0 & -0.50 & 0\\
-0.33 & 1 & -0.33 & 0 & -0.33 & 0\\
0 & -0.50 & 1 & -0.50 & 0 & 0\\
0 & 0 & -0.33 & 1 & -0.33 &-0.33\\
-0.33 & -0.33 & 0 & -0.33 & 1 & 0\\
0 & 0 & 0 & -1 & 0 & 1
\end{pmatrix}
\end{equation}\]</span> This matrix is called transition matrix.
However, the matrix would not keep the symmetric and the PSD property
after the normalization. We will come back to discuss the spectral for
the normalized graph Laplacian.</p>
<h2 id="weighted-graph">Weighted graph</h2>
<p>In practice, graph are usually weighted. The weight between vertices
can be euclidean distance or other measures. The figure blow shows the
weights of the graph. Here we apply gussian kernel to the euclidean
distances between vertices such that: <img
src="https://cmb.oss-cn-qingdao.aliyuncs.com/a_graph_weighted.png"
alt="weighted graph" /></p>
<p><span class="math display">\[\begin{equation}
w_{ij} =\exp (-r_{ij}^2/\sigma) = \exp \big(\frac{-\|x_i -
x_j\|^2}{\sigma_i\sigma_j}\big)
\end{equation}\]</span> where <span
class="math inline">\(r_{ij}\)</span> is the euclidean distance between
vetex <span class="math inline">\(i\)</span> and <span
class="math inline">\(j\)</span>, and <span
class="math inline">\(sigma\)</span> controls the bandwidth. We call the
matrix <span class="math inline">\(W=(w_{ij})\)</span> gaussian affinity
matrix such that: <span class="math display">\[\begin{equation}
\begin{pmatrix}
0 & w_{12} & w_{13} & w_{14} & w_{15}& w_{16}\\
w_{21} & 0 & w_{23} & w_{24} & w_{25}& w_{26}\\
w_{31} & w_{32} & 0 & w_{34} & w_{35}& w_{36}\\
w_{41} & w_{42} & w_{43} & 0 & w_{45}& w_{46}\\
w_{51} & w_{52} & w_{53} & w_{54} & 0& w_{56}\\
w_{61} & w_{62} & w_{63} & w_{64} & w_{65}& 0
\end{pmatrix}
\end{equation}\]</span> The guassian kernel would enlarge the distance
between too far vertices. Similar to unweighted matrix, we can also
construct graph Laplaican matrix using the gaussian affinity matrix.
First, we need find the weighted degree based on <span
class="math inline">\(W\)</span> such that: <span
class="math display">\[\begin{equation}
d_{ii} = \sum_j{w_{ij}}
\end{equation}\]</span> With the diagnal degree matrix and affinity
matrix, we now can have the weighted laplacian that: <span
class="math display">\[\begin{equation}
L = D - W
\end{equation}\]</span> Likewise, we next give the normalized form of
Laplacian such that: <span class="math display">\[\begin{equation}
\text{norm}{(L)}= D^{-1}L = I - D^{-1}W
\end{equation}\]</span> To facilitate the eigenvalue decomposition, we
need apply trick to the asymmetric matrix <span
class="math inline">\(D^{-1}L\)</span>. Since the eigenvectors of <span
class="math inline">\(D^{-1}L\)</span> and <span
class="math inline">\(D^{-1}W\)</span> are the same, we apply some trick
to <span class="math inline">\(P = D^{-1}W\)</span> to simplify the
problem. Lets construct <span class="math inline">\(P'\)</span> such
that: <span class="math display">\[\begin{equation}
P' = D^{1/2} P D^{-1/2} = D^{-1/2}WD^{-1/2}
\end{equation}\]</span> It obvious <span
class="math inline">\(P'\)</span> is symmetric due to the
symmetrisation of <span class="math inline">\(W\)</span>. We can perform
eigenvalue decomposition on <span class="math inline">\(P'\)</span>
such that: <span class="math display">\[\begin{equation}
P' = S\Lambda S^\top
\end{equation}\]</span> Where S stores the eigenvectors of <span
class="math inline">\(P'\)</span> and the diagonals of <span
class="math inline">\(\Lambda\)</span> records the eigenvalues of <span
class="math inline">\(P'\)</span>. We can also get the decompostion
to <span class="math inline">\(P\)</span> such that: <span
class="math display">\[\begin{equation}
P = D^{-1/2}S\Lambda S^\top D^{1/2}
\end{equation}\]</span> Let <span
class="math inline">\(Q=D^{-1/2}\)</span>, then <span
class="math inline">\(Q^{-1}=S^{\top}D^{1/2}\)</span>. We therefore find
the right and left eigenvector of <span class="math inline">\(P\)</span>
such that: <span class="math display">\[\begin{equation}
\psi = D^{-1/2} S \qquad
\phi = S^{\top}D^{1/2}
\end{equation}\]</span> In fact, columns of <span
class="math inline">\(\psi\)</span> stores the spectral of the graph
which also call diffusion map dimensions.</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="http://chengmingbo.github.io/2020/03/07/pytorch_abc/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mingbo Cheng">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Mingbo">
<meta itemprop="description" content="Mingbo">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Mingbo">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/03/07/pytorch_abc/" class="post-title-link" itemprop="url">Pytorch ABC</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-03-07 22:50:11" itemprop="dateCreated datePublished" datetime="2020-03-07T22:50:11+01:00">2020-03-07</time>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="fundamentals">Fundamentals</h2>
<h4 id="torch.tensor">Torch.tensor</h4>
<pre><code><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">t = tensor([[<span class="number">1</span>,<span class="number">2</span>,<span class="number">4</span>],[<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>]])</span><br><span class="line">t.shape: (<span class="number">2</span>,<span class="number">3</span>)</span><br><span class="line">t.ndim: <span class="number">2</span></span><br><span class="line"><span class="built_in">type</span>: scalar, vector, matrix, tensor</span><br></pre></td></tr></table></figure></code></pre>
<h4 id="tensor-data-produce">Tensor data produce</h4>
<pre><code><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">random_tensor = torch.rand(size=(<span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>))</span><br><span class="line">zeros = torch.zeros(size=(<span class="number">3</span>, <span class="number">4</span>))</span><br><span class="line">ones = torch.ones(size=(<span class="number">3</span>, <span class="number">4</span>))</span><br><span class="line">zero_to_ten = torch.arange(start=<span class="number">0</span>, end=<span class="number">10</span>, step=<span class="number">1</span>)</span><br><span class="line">ten_zeros = torch.zeros_like(<span class="built_in">input</span>=zero_to_ten) <span class="comment"># same shape but all zeros</span></span><br></pre></td></tr></table></figure></code></pre>
<h4 id="float">Float</h4>
<pre><code><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">torch.float32/torch.<span class="built_in">float</span></span><br><span class="line">torch.float16</span><br><span class="line">torch.half</span><br><span class="line">torch.float64/torch.double</span><br></pre></td></tr></table></figure></code></pre>
<h4 id="types-specific-for-gpu-or-cpu">types specific for GPU or
CPU</h4>