Repository navigation
Expand file tree
/
Copy pathquickstart.html
More file actions
1160 lines (1040 loc) · 96.1 KB
/
Copy pathquickstart.html
File metadata and controls
1160 lines (1040 loc) · 96.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
<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Quick start guide — POT Python Optimal Transport 0.7.0 documentation</title>
<link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="_static/gallery.css" type="text/css" />
<link rel="stylesheet" href="_static/gallery-binder.css" type="text/css" />
<link rel="stylesheet" href="_static/gallery-dataframe.css" type="text/css" />
<!--[if lt IE 9]>
<script src="_static/js/html5shiv.min.js"></script>
<![endif]-->
<script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
<script src="_static/jquery.js"></script>
<script src="_static/underscore.js"></script>
<script src="_static/doctools.js"></script>
<script src="_static/language_data.js"></script>
<script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/javascript" src="_static/js/theme.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="API and modules" href="all.html" />
<link rel="prev" title="POT: Python Optimal Transport" href="index.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="index.html" class="icon icon-home" alt="Documentation Home"> POT Python Optimal Transport
</a>
<div class="version">
0.7.0
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div>
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="index.html">POT: Python Optimal Transport</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Quick start guide</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#optimal-transport-and-wasserstein-distance">Optimal transport and Wasserstein distance</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#solving-optimal-transport">Solving optimal transport</a></li>
<li class="toctree-l3"><a class="reference internal" href="#computing-wasserstein-distance">Computing Wasserstein distance</a></li>
<li class="toctree-l3"><a class="reference internal" href="#special-cases">Special cases</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#regularized-optimal-transport">Regularized Optimal Transport</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#entropic-regularized-ot">Entropic regularized OT</a></li>
<li class="toctree-l3"><a class="reference internal" href="#other-regularization">Other regularization</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#quadratic-regularization">Quadratic regularization</a></li>
<li class="toctree-l4"><a class="reference internal" href="#group-lasso-regularization">Group Lasso regularization</a></li>
<li class="toctree-l4"><a class="reference internal" href="#generic-solvers">Generic solvers</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#wasserstein-barycenters">Wasserstein Barycenters</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#barycenters-with-fixed-support">Barycenters with fixed support</a></li>
<li class="toctree-l3"><a class="reference internal" href="#barycenters-with-free-support">Barycenters with free support</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#monge-mapping-and-domain-adaptation">Monge mapping and Domain adaptation</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#monge-mapping-estimation">Monge Mapping estimation</a></li>
<li class="toctree-l3"><a class="reference internal" href="#domain-adaptation-classes">Domain adaptation classes</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#other-applications">Other applications</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#wasserstein-discriminant-analysis">Wasserstein Discriminant Analysis</a></li>
<li class="toctree-l3"><a class="reference internal" href="#unbalanced-optimal-transport">Unbalanced optimal transport</a></li>
<li class="toctree-l3"><a class="reference internal" href="#unbalanced-barycenters">Unbalanced Barycenters</a></li>
<li class="toctree-l3"><a class="reference internal" href="#partial-optimal-transport">Partial optimal transport</a></li>
<li class="toctree-l3"><a class="reference internal" href="#gromov-wasserstein">Gromov-Wasserstein</a></li>
<li class="toctree-l3"><a class="reference internal" href="#gpu-acceleration">GPU acceleration</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#faq">FAQ</a></li>
<li class="toctree-l2"><a class="reference internal" href="#references">References</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="all.html">API and modules</a></li>
<li class="toctree-l1"><a class="reference internal" href="auto_examples/index.html">Examples gallery</a></li>
<li class="toctree-l1"><a class="reference internal" href="releases.html">Releases</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
<nav class="wy-nav-top" aria-label="top navigation">
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="index.html">POT Python Optimal Transport</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="breadcrumbs navigation">
<ul class="wy-breadcrumbs">
<li><a href="index.html" class="icon icon-home"></a> »</li>
<li>Quick start guide</li>
<li class="wy-breadcrumbs-aside">
<a href="_sources/quickstart.rst.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<div class="section" id="quick-start-guide">
<h1>Quick start guide<a class="headerlink" href="#quick-start-guide" title="Permalink to this headline">¶</a></h1>
<p>In the following we provide some pointers about which functions and classes
to use for different problems related to optimal transport (OT) and machine
learning. We refer when we can to concrete examples in the documentation that
are also available as notebooks on the POT Github.</p>
<p>This document is not a tutorial on numerical optimal transport. For this we strongly
recommend to read the very nice book <a class="footnote-reference brackets" href="#id64" id="id1">15</a> .</p>
<div class="section" id="optimal-transport-and-wasserstein-distance">
<h2>Optimal transport and Wasserstein distance<a class="headerlink" href="#optimal-transport-and-wasserstein-distance" title="Permalink to this headline">¶</a></h2>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>In POT, most functions that solve OT or regularized OT problems have two
versions that return the OT matrix or the value of the optimal solution. For
instance <a class="reference internal" href="all.html#ot.emd" title="ot.emd"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd</span></code></a> return the OT matrix and <a class="reference internal" href="all.html#ot.emd2" title="ot.emd2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd2</span></code></a> return the
Wassertsein distance. This approach has been implemented in practice for all
solvers that return an OT matrix (even Gromov-Wasserstsein)</p>
</div>
<div class="section" id="solving-optimal-transport">
<h3>Solving optimal transport<a class="headerlink" href="#solving-optimal-transport" title="Permalink to this headline">¶</a></h3>
<p>The optimal transport problem between discrete distributions is often expressed
as</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}\gamma^* = arg\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j}\\s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>where :</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(M\in\mathbb{R}_+^{m\times n}\)</span> is the metric cost matrix defining the cost to move mass from bin <span class="math notranslate nohighlight">\(a_i\)</span> to bin <span class="math notranslate nohighlight">\(b_j\)</span>.</p></li>
<li><p><span class="math notranslate nohighlight">\(a\)</span> and <span class="math notranslate nohighlight">\(b\)</span> are histograms on the simplex (positive, sum to 1) that represent the</p></li>
</ul>
<p>weights of each samples in the source an target distributions.</p>
<p>Solving the linear program above can be done using the function <a class="reference internal" href="all.html#ot.emd" title="ot.emd"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd</span></code></a>
that will return the optimal transport matrix <span class="math notranslate nohighlight">\(\gamma^*\)</span>:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># a,b are 1D histograms (sum to 1 and positive)</span>
<span class="c1"># M is the ground cost matrix</span>
<span class="n">T</span><span class="o">=</span><span class="n">ot</span><span class="o">.</span><span class="n">emd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">,</span><span class="n">M</span><span class="p">)</span> <span class="c1"># exact linear program</span>
</pre></div>
</div>
<p>The method implemented for solving the OT problem is the network simplex, it is
implemented in C from <a class="footnote-reference brackets" href="#id50" id="id2">1</a>. It has a complexity of <span class="math notranslate nohighlight">\(O(n^3)\)</span> but the
solver is quite efficient and uses sparsity of the solution.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of use for <a class="reference internal" href="all.html#ot.emd" title="ot.emd"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd</span></code></a> are available in :</p>
<ul class="simple">
<li><p><a class="reference internal" href="auto_examples/plot_OT_2D_samples.html"><span class="doc">2D Optimal transport between empirical distributions</span></a></p></li>
<li><p><a class="reference internal" href="auto_examples/plot_OT_1D.html"><span class="doc">1D optimal transport</span></a></p></li>
<li><p><a class="reference internal" href="auto_examples/plot_OT_L1_vs_L2.html"><span class="doc">2D Optimal transport for different metrics</span></a></p></li>
</ul>
</div>
</div>
<div class="section" id="computing-wasserstein-distance">
<h3>Computing Wasserstein distance<a class="headerlink" href="#computing-wasserstein-distance" title="Permalink to this headline">¶</a></h3>
<p>The value of the OT solution is often more of interest than the OT matrix :</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}OT(a,b)=\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j}\\s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>It can computed from an already estimated OT matrix with
<code class="code docutils literal notranslate"><span class="pre">np.sum(T*M)</span></code> or directly with the function <a class="reference internal" href="all.html#ot.emd2" title="ot.emd2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd2</span></code></a>.</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># a,b are 1D histograms (sum to 1 and positive)</span>
<span class="c1"># M is the ground cost matrix</span>
<span class="n">W</span><span class="o">=</span><span class="n">ot</span><span class="o">.</span><span class="n">emd2</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">,</span><span class="n">M</span><span class="p">)</span> <span class="c1"># Wasserstein distance / EMD value</span>
</pre></div>
</div>
<p>Note that the well known <a class="reference external" href="https://en.wikipedia.org/wiki/Wasserstein_metric">Wasserstein distance</a> between distributions a and
b is defined as</p>
<blockquote>
<div><div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}W_p(a,b)=(\min_\gamma \sum_{i,j}\gamma_{i,j}\|x_i-y_j\|_p)^\frac{1}{p}\\s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
</div></blockquote>
<p>This means that if you want to compute the <span class="math notranslate nohighlight">\(W_2\)</span> you need to compute the
square root of <a class="reference internal" href="all.html#ot.emd2" title="ot.emd2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd2</span></code></a> when providing
<code class="code docutils literal notranslate"><span class="pre">M=ot.dist(xs,xt)</span></code> that use the squared euclidean distance by default. Computing
the <span class="math notranslate nohighlight">\(W_1\)</span> wasserstein distance can be done directly with <a class="reference internal" href="all.html#ot.emd2" title="ot.emd2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd2</span></code></a>
when providing <code class="code docutils literal notranslate"><span class="pre">M=ot.dist(xs,xt,</span> <span class="pre">metric='euclidean')</span></code> to use the euclidean
distance.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>An example of use for <a class="reference internal" href="all.html#ot.emd2" title="ot.emd2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd2</span></code></a> is available in :</p>
<ul class="simple">
<li><p><a class="reference internal" href="auto_examples/plot_compute_emd.html"><span class="doc">Plot multiple EMD</span></a></p></li>
</ul>
</div>
</div>
<div class="section" id="special-cases">
<h3>Special cases<a class="headerlink" href="#special-cases" title="Permalink to this headline">¶</a></h3>
<p>Note that the OT problem and the corresponding Wasserstein distance can in some
special cases be computed very efficiently.</p>
<p>For instance when the samples are in 1D, then the OT problem can be solved in
<span class="math notranslate nohighlight">\(O(n\log(n))\)</span> by using a simple sorting. In this case we provide the
function <a class="reference internal" href="all.html#id0" title="ot.emd_1d"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd_1d</span></code></a> and <a class="reference internal" href="all.html#ot.emd2_1d" title="ot.emd2_1d"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd2_1d</span></code></a> to return respectively the OT
matrix and value. Note that since the solution is very sparse the <code class="code docutils literal notranslate"><span class="pre">sparse</span></code>
parameter of <a class="reference internal" href="all.html#id0" title="ot.emd_1d"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd_1d</span></code></a> allows for solving and returning the solution for
very large problems. Note that in order to compute directly the <span class="math notranslate nohighlight">\(W_p\)</span>
Wasserstein distance in 1D we provide the function <a class="reference internal" href="all.html#ot.wasserstein_1d" title="ot.wasserstein_1d"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.wasserstein_1d</span></code></a> that
takes <code class="code docutils literal notranslate"><span class="pre">p</span></code> as a parameter.</p>
<p>Another special case for estimating OT and Monge mapping is between Gaussian
distributions. In this case there exists a close form solution given in Remark
2.29 in <a class="footnote-reference brackets" href="#id64" id="id3">15</a> and the Monge mapping is an affine function and can be
also computed from the covariances and means of the source and target
distributions. In the case when the finite sample dataset is supposed gaussian, we provide
<a class="reference internal" href="gen_modules/ot.da.html#ot.da.OT_mapping_linear" title="ot.da.OT_mapping_linear"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.da.OT_mapping_linear</span></code></a> that returns the parameters for the Monge
mapping.</p>
</div>
</div>
<div class="section" id="regularized-optimal-transport">
<h2>Regularized Optimal Transport<a class="headerlink" href="#regularized-optimal-transport" title="Permalink to this headline">¶</a></h2>
<p>Recent developments have shown the interest of regularized OT both in terms of
computational and statistical properties.
We address in this section the regularized OT problems that can be expressed as</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}\gamma^* = arg\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j} + \lambda\Omega(\gamma)\\ s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>where :</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(M\in\mathbb{R}_+^{m\times n}\)</span> is the metric cost matrix defining the cost to move mass from bin <span class="math notranslate nohighlight">\(a_i\)</span> to bin <span class="math notranslate nohighlight">\(b_j\)</span>.</p></li>
<li><p><span class="math notranslate nohighlight">\(a\)</span> and <span class="math notranslate nohighlight">\(b\)</span> are histograms (positive, sum to 1) that represent the weights of each samples in the source an target distributions.</p></li>
<li><p><span class="math notranslate nohighlight">\(\Omega\)</span> is the regularization term.</p></li>
</ul>
<p>We discuss in the following specific algorithms that can be used depending on
the regularization term.</p>
<div class="section" id="entropic-regularized-ot">
<h3>Entropic regularized OT<a class="headerlink" href="#entropic-regularized-ot" title="Permalink to this headline">¶</a></h3>
<p>This is the most common regularization used for optimal transport. It has been
proposed in the ML community by Marco Cuturi in his seminal paper <a class="footnote-reference brackets" href="#id51" id="id4">2</a>. This
regularization has the following expression</p>
<div class="math notranslate nohighlight">
\[\Omega(\gamma)=\sum_{i,j}\gamma_{i,j}\log(\gamma_{i,j})\]</div>
<p>The use of the regularization term above in the optimization problem has a very
strong impact. First it makes the problem smooth which leads to new optimization
procedures such as the well known Sinkhorn algorithm <a class="footnote-reference brackets" href="#id51" id="id5">2</a> or L-BFGS (see
<a class="reference internal" href="gen_modules/ot.smooth.html#module-ot.smooth" title="ot.smooth"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.smooth</span></code></a> ). Next it makes the problem
strictly convex meaning that there will be a unique solution. Finally the
solution of the resulting optimization problem can be expressed as:</p>
<div class="math notranslate nohighlight">
\[\gamma_\lambda^*=\text{diag}(u)K\text{diag}(v)\]</div>
<p>where <span class="math notranslate nohighlight">\(u\)</span> and <span class="math notranslate nohighlight">\(v\)</span> are vectors and <span class="math notranslate nohighlight">\(K=\exp(-M/\lambda)\)</span> where
the <span class="math notranslate nohighlight">\(\exp\)</span> is taken component-wise. In order to solve the optimization
problem, on can use an alternative projection algorithm called Sinkhorn-Knopp that can be very
efficient for large values if regularization.</p>
<p>The Sinkhorn-Knopp algorithm is implemented in <a class="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn</span></code></a> and
<a class="reference internal" href="all.html#ot.sinkhorn2" title="ot.sinkhorn2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn2</span></code></a> that return respectively the OT matrix and the value of the
linear term. Note that the regularization parameter <span class="math notranslate nohighlight">\(\lambda\)</span> in the
equation above is given to those functions with the parameter <code class="code docutils literal notranslate"><span class="pre">reg</span></code>.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="kn">import</span> <span class="nn">ot</span>
<span class="gp">>>> </span><span class="n">a</span><span class="o">=</span><span class="p">[</span><span class="o">.</span><span class="mi">5</span><span class="p">,</span><span class="o">.</span><span class="mi">5</span><span class="p">]</span>
<span class="gp">>>> </span><span class="n">b</span><span class="o">=</span><span class="p">[</span><span class="o">.</span><span class="mi">5</span><span class="p">,</span><span class="o">.</span><span class="mi">5</span><span class="p">]</span>
<span class="gp">>>> </span><span class="n">M</span><span class="o">=</span><span class="p">[[</span><span class="mf">0.</span><span class="p">,</span><span class="mf">1.</span><span class="p">],[</span><span class="mf">1.</span><span class="p">,</span><span class="mf">0.</span><span class="p">]]</span>
<span class="gp">>>> </span><span class="n">ot</span><span class="o">.</span><span class="n">sinkhorn</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">,</span><span class="n">M</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
<span class="go">array([[ 0.36552929, 0.13447071],</span>
<span class="go"> [ 0.13447071, 0.36552929]])</span>
</pre></div>
</div>
<p>More details about the algorithms used are given in the following note.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>The main function to solve entropic regularized OT is <a class="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn</span></code></a>.
This function is a wrapper and the parameter <code class="code docutils literal notranslate"><span class="pre">method</span></code> help you select
the actual algorithm used to solve the problem:</p>
<ul class="simple">
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn'</span></code> calls <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_knopp" title="ot.bregman.sinkhorn_knopp"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.sinkhorn_knopp</span></code></a> the
classic algorithm <a class="footnote-reference brackets" href="#id51" id="id6">2</a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn_stabilized'</span></code> calls <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_stabilized" title="ot.bregman.sinkhorn_stabilized"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.sinkhorn_stabilized</span></code></a> the
log stabilized version of the algorithm <a class="footnote-reference brackets" href="#id58" id="id7">9</a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn_epsilon_scaling'</span></code> calls
<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_epsilon_scaling" title="ot.bregman.sinkhorn_epsilon_scaling"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.sinkhorn_epsilon_scaling</span></code></a> the epsilon scaling version
of the algorithm <a class="footnote-reference brackets" href="#id58" id="id8">9</a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='greenkhorn'</span></code> calls <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.greenkhorn" title="ot.bregman.greenkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.greenkhorn</span></code></a> the
greedy sinkhorn verison of the algorithm <a class="footnote-reference brackets" href="#id71" id="id9">22</a>.</p></li>
</ul>
<p>In addition to all those variants of sinkhorn, we have another
implementation solving the problem in the smooth dual or semi-dual in
<a class="reference internal" href="gen_modules/ot.smooth.html#module-ot.smooth" title="ot.smooth"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.smooth</span></code></a>. This solver uses the <a class="reference external" href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html#scipy.optimize.minimize" title="(in SciPy v1.5.2)"><code class="xref any docutils literal notranslate"><span class="pre">scipy.optimize.minimize</span></code></a>
function to solve the smooth problem with <code class="code docutils literal notranslate"><span class="pre">L-BFGS-B</span></code> algorithm. Tu use
this solver, use functions <a class="reference internal" href="gen_modules/ot.smooth.html#ot.smooth.smooth_ot_dual" title="ot.smooth.smooth_ot_dual"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.smooth.smooth_ot_dual</span></code></a> or
<a class="reference internal" href="gen_modules/ot.smooth.html#ot.smooth.smooth_ot_semi_dual" title="ot.smooth.smooth_ot_semi_dual"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.smooth.smooth_ot_semi_dual</span></code></a> with parameter <code class="code docutils literal notranslate"><span class="pre">reg_type='kl'</span></code> to
choose entropic/Kullbach Leibler regularization.</p>
</div>
<p>Recently <a class="footnote-reference brackets" href="#id72" id="id10">23</a> introduced the sinkhorn divergence that build from entropic
regularization to compute fast and differentiable geometric divergence between
empirical distributions. Note that we provide a function that compute directly
(with no need to pre compute the <code class="code docutils literal notranslate"><span class="pre">M</span></code> matrix)
the sinkhorn divergence for empirical distributions in
<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.empirical_sinkhorn_divergence" title="ot.bregman.empirical_sinkhorn_divergence"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.empirical_sinkhorn_divergence</span></code></a>. Similarly one can compute the
OT matrix and loss for empirical distributions with respectively
<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.empirical_sinkhorn" title="ot.bregman.empirical_sinkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.empirical_sinkhorn</span></code></a> and <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.empirical_sinkhorn2" title="ot.bregman.empirical_sinkhorn2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.empirical_sinkhorn2</span></code></a>.</p>
<p>Finally note that we also provide in <a class="reference internal" href="gen_modules/ot.stochastic.html#module-ot.stochastic" title="ot.stochastic"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.stochastic</span></code></a> several implementation
of stochastic solvers for entropic regularized OT <a class="footnote-reference brackets" href="#id67" id="id11">18</a> <a class="footnote-reference brackets" href="#id68" id="id12">19</a>. Those pure Python
implementations are not optimized for speed but provide a roust implementation
of algorithms in <a class="footnote-reference brackets" href="#id67" id="id13">18</a> <a class="footnote-reference brackets" href="#id68" id="id14">19</a>.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of use for <a class="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn</span></code></a> are available in :</p>
<ul class="simple">
<li><p><a class="reference internal" href="auto_examples/plot_OT_2D_samples.html"><span class="doc">2D Optimal transport between empirical distributions</span></a></p></li>
<li><p><a class="reference internal" href="auto_examples/plot_OT_1D.html"><span class="doc">1D optimal transport</span></a></p></li>
<li><p><a class="reference internal" href="auto_examples/plot_OT_1D_smooth.html"><span class="doc">1D smooth optimal transport</span></a></p></li>
<li><p><a class="reference internal" href="auto_examples/plot_stochastic.html"><span class="doc">Stochastic examples</span></a></p></li>
</ul>
</div>
</div>
<div class="section" id="other-regularization">
<h3>Other regularization<a class="headerlink" href="#other-regularization" title="Permalink to this headline">¶</a></h3>
<p>While entropic OT is the most common and favored in practice, there exist other
kind of regularization. We provide in POT two specific solvers for other
regularization terms, namely quadratic regularization and group lasso
regularization. But we also provide in <a class="reference internal" href="gen_modules/ot.optim.html#module-ot.optim" title="ot.optim"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.optim</span></code></a> two generic solvers that allows solving any
smooth regularization in practice.</p>
<div class="section" id="quadratic-regularization">
<h4>Quadratic regularization<a class="headerlink" href="#quadratic-regularization" title="Permalink to this headline">¶</a></h4>
<p>The first general regularization term we can solve is the quadratic
regularization of the form</p>
<div class="math notranslate nohighlight">
\[\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}^2\]</div>
<p>this regularization term has a similar effect to entropic regularization in
densifying the OT matrix but it keeps some sort of sparsity that is lost with
entropic regularization as soon as <span class="math notranslate nohighlight">\(\lambda>0\)</span> <a class="footnote-reference brackets" href="#id66" id="id15">17</a>. This problem can be
solved with POT using solvers from <a class="reference internal" href="gen_modules/ot.smooth.html#module-ot.smooth" title="ot.smooth"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.smooth</span></code></a>, more specifically
functions <a class="reference internal" href="gen_modules/ot.smooth.html#ot.smooth.smooth_ot_dual" title="ot.smooth.smooth_ot_dual"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.smooth.smooth_ot_dual</span></code></a> or
<a class="reference internal" href="gen_modules/ot.smooth.html#ot.smooth.smooth_ot_semi_dual" title="ot.smooth.smooth_ot_semi_dual"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.smooth.smooth_ot_semi_dual</span></code></a> with parameter <code class="code docutils literal notranslate"><span class="pre">reg_type='l2'</span></code> to
choose the quadratic regularization.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of quadratic regularization are available in :</p>
<ul class="simple">
<li><p><a class="reference internal" href="auto_examples/plot_OT_1D_smooth.html"><span class="doc">1D smooth optimal transport</span></a></p></li>
<li><p><a class="reference internal" href="auto_examples/plot_optim_OTreg.html"><span class="doc">Regularized OT with generic solver</span></a></p></li>
</ul>
</div>
</div>
<div class="section" id="group-lasso-regularization">
<h4>Group Lasso regularization<a class="headerlink" href="#group-lasso-regularization" title="Permalink to this headline">¶</a></h4>
<p>Another regularization that has been used in recent years <a class="footnote-reference brackets" href="#id54" id="id16">5</a> is the group lasso
regularization</p>
<div class="math notranslate nohighlight">
\[\Omega(\gamma)=\sum_{j,G\in\mathcal{G}} \|\gamma_{G,j}\|_q^p\]</div>
<p>where <span class="math notranslate nohighlight">\(\mathcal{G}\)</span> contains non overlapping groups of lines in the OT
matrix. This regularization proposed in <a class="footnote-reference brackets" href="#id54" id="id17">5</a> will promote sparsity at the group level and for
instance will force target samples to get mass from a small number of groups.
Note that the exact OT solution is already sparse so this regularization does
not make sens if it is not combined with entropic regularization. Depending on
the choice of <code class="code docutils literal notranslate"><span class="pre">p</span></code> and <code class="code docutils literal notranslate"><span class="pre">q</span></code>, the problem can be solved with different
approaches. When <code class="code docutils literal notranslate"><span class="pre">q=1</span></code> and <code class="code docutils literal notranslate"><span class="pre">p<1</span></code> the problem is non convex but can
be solved using an efficient majoration minimization approach with
<a class="reference internal" href="all.html#ot.sinkhorn_lpl1_mm" title="ot.sinkhorn_lpl1_mm"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn_lpl1_mm</span></code></a>. When <code class="code docutils literal notranslate"><span class="pre">q=2</span></code> and <code class="code docutils literal notranslate"><span class="pre">p=1</span></code> we recover the
convex group lasso and we provide a solver using generalized conditional
gradient algorithm <a class="footnote-reference brackets" href="#id56" id="id18">7</a> in function
<a class="reference internal" href="gen_modules/ot.da.html#ot.da.sinkhorn_l1l2_gl" title="ot.da.sinkhorn_l1l2_gl"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.da.sinkhorn_l1l2_gl</span></code></a>.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of group Lasso regularization are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_classes</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_d2</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="generic-solvers">
<h4>Generic solvers<a class="headerlink" href="#generic-solvers" title="Permalink to this headline">¶</a></h4>
<p>Finally we propose in POT generic solvers that can be used to solve any
regularization as long as you can provide a function computing the
regularization and a function computing its gradient (or sub-gradient).</p>
<p>In order to solve</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}\gamma^* = arg\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j} + \lambda\Omega(\gamma)\\ s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>you can use function <a class="reference internal" href="gen_modules/ot.optim.html#ot.optim.cg" title="ot.optim.cg"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.optim.cg</span></code></a> that will use a conditional gradient as
proposed in <a class="footnote-reference brackets" href="#id55" id="id19">6</a> . You need to provide the regularization function as parameter
<code class="docutils literal notranslate"><span class="pre">f</span></code> and its gradient as parameter <code class="docutils literal notranslate"><span class="pre">df</span></code>. Note that the conditional gradient relies on
iterative solving of a linearization of the problem using the exact
<a class="reference internal" href="all.html#ot.emd" title="ot.emd"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.emd</span></code></a> so it can be slow in practice. But, being an interior point
algorithm, it always returns a
transport matrix that does not violates the marginals.</p>
<p>Another generic solver is proposed to solve the problem</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}\gamma^* = arg\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j}+ \lambda_e\Omega_e(\gamma) + \lambda\Omega(\gamma)\\ s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>where <span class="math notranslate nohighlight">\(\Omega_e\)</span> is the entropic regularization. In this case we use a
generalized conditional gradient <a class="footnote-reference brackets" href="#id56" id="id20">7</a> implemented in <a class="reference internal" href="gen_modules/ot.optim.html#ot.optim.gcg" title="ot.optim.gcg"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.optim.gcg</span></code></a> that
does not linearize the entropic term but
relies on <a class="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn</span></code></a> for its iterations.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>An example of generic solvers are available in :</p>
<ul class="simple">
<li><p><a class="reference internal" href="auto_examples/plot_optim_OTreg.html"><span class="doc">Regularized OT with generic solver</span></a></p></li>
</ul>
</div>
</div>
</div>
</div>
<div class="section" id="wasserstein-barycenters">
<h2>Wasserstein Barycenters<a class="headerlink" href="#wasserstein-barycenters" title="Permalink to this headline">¶</a></h2>
<p>A Wasserstein barycenter is a distribution that minimize its Wasserstein
distance with respect to other distributions <a class="footnote-reference brackets" href="#id65" id="id21">16</a>. It corresponds to minimizing the
following problem by searching a distribution <span class="math notranslate nohighlight">\(\mu\)</span> such that</p>
<div class="math notranslate nohighlight">
\[\min_\mu \quad \sum_{k} w_kW(\mu,\mu_k)\]</div>
<p>In practice we model a distribution with a finite number of support position:</p>
<div class="math notranslate nohighlight">
\[\mu=\sum_{i=1}^n a_i\delta_{x_i}\]</div>
<p>where <span class="math notranslate nohighlight">\(a\)</span> is an histogram on the simplex and the <span class="math notranslate nohighlight">\(\{x_i\}\)</span> are the
position of the support. We can clearly see here that optimizing <span class="math notranslate nohighlight">\(\mu\)</span> can
be done by searching for optimal weights <span class="math notranslate nohighlight">\(a\)</span> or optimal support
<span class="math notranslate nohighlight">\(\{x_i\}\)</span> (optimizing both is also an option).
We provide in POT solvers to estimate a discrete
Wasserstein barycenter in both cases.</p>
<div class="section" id="barycenters-with-fixed-support">
<h3>Barycenters with fixed support<a class="headerlink" href="#barycenters-with-fixed-support" title="Permalink to this headline">¶</a></h3>
<p>When optimizing a barycenter with a fixed support, the optimization problem can
be expressed as</p>
<div class="math notranslate nohighlight">
\[\min_a \quad \sum_{k} w_k W(a,b_k)\]</div>
<p>where <span class="math notranslate nohighlight">\(b_k\)</span> are also weights in the simplex. In the non-regularized case,
the problem above is a classical linear program. In this case we propose a
solver <code class="xref any docutils literal notranslate"><span class="pre">ot.lp.barycenter</span></code> that rely on generic LP solvers. By default the
function uses <a class="reference external" href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html#scipy.optimize.linprog" title="(in SciPy v1.5.2)"><code class="xref any docutils literal notranslate"><span class="pre">scipy.optimize.linprog</span></code></a>, but more efficient LP solvers from
cvxopt can be also used by changing parameter <code class="code docutils literal notranslate"><span class="pre">solver</span></code>. Note that this problem
requires to solve a very large linear program and can be very slow in
practice.</p>
<p>Similarly to the OT problem, OT barycenters can be computed in the regularized
case. When using entropic regularization is used, the problem can be solved with a
generalization of the sinkhorn algorithm based on bregman projections <a class="footnote-reference brackets" href="#id52" id="id22">3</a>. This
algorithm is provided in function <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.barycenter" title="ot.bregman.barycenter"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.barycenter</span></code></a> also available as
<a class="reference internal" href="all.html#ot.barycenter" title="ot.barycenter"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.barycenter</span></code></a>. In this case, the algorithm scales better to large
distributions and rely only on matrix multiplications that can be performed in
parallel.</p>
<p>In addition to the speedup brought by regularization, one can also greatly
accelerate the estimation of Wasserstein barycenter when the support has a
separable structure <a class="footnote-reference brackets" href="#id70" id="id23">21</a>. In the case of 2D images for instance one can replace
the matrix vector production in the Bregman projections by convolution
operators. We provide an implementation of this algorithm in function
<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.convolutional_barycenter2d" title="ot.bregman.convolutional_barycenter2d"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.convolutional_barycenter2d</span></code></a>.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of Wasserstein (<code class="xref any docutils literal notranslate"><span class="pre">ot.lp.barycenter</span></code>) and regularized Wasserstein
barycenter (<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.barycenter" title="ot.bregman.barycenter"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.barycenter</span></code></a>) computation are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_barycenter_1D</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_barycenter_lp_vs_entropic</span></code></p></li>
</ul>
<p>An example of convolutional barycenter
(<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.convolutional_barycenter2d" title="ot.bregman.convolutional_barycenter2d"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.convolutional_barycenter2d</span></code></a>) computation
for 2D images is available
in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_convolutional_barycenter</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="barycenters-with-free-support">
<h3>Barycenters with free support<a class="headerlink" href="#barycenters-with-free-support" title="Permalink to this headline">¶</a></h3>
<p>Estimating the Wasserstein barycenter with free support but fixed weights
corresponds to solving the following optimization problem:</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}\min_{\{x_i\}} \quad \sum_{k} w_kW(\mu,\mu_k)\\s.t. \quad \mu=\sum_{i=1}^n a_i\delta_{x_i}\end{aligned}\end{align} \]</div>
<p>We provide a solver based on <a class="footnote-reference brackets" href="#id69" id="id24">20</a> in
<a class="reference internal" href="gen_modules/ot.lp.html#ot.lp.free_support_barycenter" title="ot.lp.free_support_barycenter"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.lp.free_support_barycenter</span></code></a>. This function minimize the problem and
return a locally optimal support <span class="math notranslate nohighlight">\(\{x_i\}\)</span> for uniform or given weights
<span class="math notranslate nohighlight">\(a\)</span>.</p>
<blockquote>
<div><div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>An example of the free support barycenter estimation is available
in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_free_support_barycenter</span></code></p></li>
</ul>
</div>
</div></blockquote>
</div>
</div>
<div class="section" id="monge-mapping-and-domain-adaptation">
<h2>Monge mapping and Domain adaptation<a class="headerlink" href="#monge-mapping-and-domain-adaptation" title="Permalink to this headline">¶</a></h2>
<p>The original transport problem investigated by Gaspard Monge was seeking for a
mapping function that maps (or transports) between a source and target
distribution but that minimizes the transport loss. The existence and uniqueness of this
optimal mapping is still an open problem in the general case but has been proven
for smooth distributions by Brenier in his eponym <a class="reference external" href="https://who.rocq.inria.fr/Jean-David.Benamou/demiheure.pdf">theorem</a>. We provide in
<a class="reference internal" href="gen_modules/ot.da.html#module-ot.da" title="ot.da"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.da</span></code></a> several solvers for smooth Monge mapping estimation and domain
adaptation from discrete distributions.</p>
<div class="section" id="monge-mapping-estimation">
<h3>Monge Mapping estimation<a class="headerlink" href="#monge-mapping-estimation" title="Permalink to this headline">¶</a></h3>
<p>We now discuss several approaches that are implemented in POT to estimate or
approximate a Monge mapping from finite distributions.</p>
<p>First note that when the source and target distributions are supposed to be Gaussian
distributions, there exists a close form solution for the mapping and its an
affine function <a class="footnote-reference brackets" href="#id63" id="id25">14</a> of the form <span class="math notranslate nohighlight">\(T(x)=Ax+b\)</span> . In this case we provide the function
<a class="reference internal" href="gen_modules/ot.da.html#ot.da.OT_mapping_linear" title="ot.da.OT_mapping_linear"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.da.OT_mapping_linear</span></code></a> that return the operator <span class="math notranslate nohighlight">\(A\)</span> and vector
<span class="math notranslate nohighlight">\(b\)</span>. Note that if the number of samples is too small there is a parameter
<code class="code docutils literal notranslate"><span class="pre">reg</span></code> that provide a regularization for the covariance matrix estimation.</p>
<p>For a more general mapping estimation we also provide the barycentric mapping
proposed in <a class="footnote-reference brackets" href="#id55" id="id26">6</a> . It is implemented in the class <a class="reference internal" href="gen_modules/ot.da.html#ot.da.EMDTransport" title="ot.da.EMDTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.EMDTransport</span></code></a> and
other transport based classes in <a class="reference internal" href="gen_modules/ot.da.html#module-ot.da" title="ot.da"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.da</span></code></a> . Those classes are discussed more
in the following but follow an interface similar to sklearn classes. Finally a
method proposed in <a class="footnote-reference brackets" href="#id57" id="id27">8</a> that estimates a continuous mapping approximating the
barycentric mapping is provided in <a class="reference internal" href="gen_modules/ot.da.html#ot.da.joint_OT_mapping_linear" title="ot.da.joint_OT_mapping_linear"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.da.joint_OT_mapping_linear</span></code></a> for
linear mapping and <a class="reference internal" href="gen_modules/ot.da.html#ot.da.joint_OT_mapping_kernel" title="ot.da.joint_OT_mapping_kernel"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.da.joint_OT_mapping_kernel</span></code></a> for non linear mapping.</p>
<blockquote>
<div><div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>An example of the linear Monge mapping estimation is available
in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_linear_mapping</span></code></p></li>
</ul>
</div>
</div></blockquote>
</div>
<div class="section" id="domain-adaptation-classes">
<h3>Domain adaptation classes<a class="headerlink" href="#domain-adaptation-classes" title="Permalink to this headline">¶</a></h3>
<p>The use of OT for domain adaptation (OTDA) has been first proposed in <a class="footnote-reference brackets" href="#id54" id="id28">5</a> that also
introduced the group Lasso regularization. The main idea of OTDA is to estimate
a mapping of the samples between source and target distributions which allows to
transport labeled source samples onto the target distribution with no labels.</p>
<p>We provide several classes based on <a class="reference internal" href="gen_modules/ot.da.html#ot.da.BaseTransport" title="ot.da.BaseTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.BaseTransport</span></code></a> that provide
several OT and mapping estimations. The interface of those classes is similar to
classifiers in sklearn toolbox. At initialization, several parameters such as</p>
<blockquote>
<div><p>regularization parameter value can be set. Then one needs to estimate the</p>
</div></blockquote>
<p>mapping with function <a class="reference internal" href="gen_modules/ot.da.html#ot.da.BaseTransport.fit" title="ot.da.BaseTransport.fit"><code class="xref any py py-meth docutils literal notranslate"><span class="pre">ot.da.BaseTransport.fit</span></code></a>. Finally one can map the
samples from source to target with <a class="reference internal" href="gen_modules/ot.da.html#ot.da.BaseTransport.transform" title="ot.da.BaseTransport.transform"><code class="xref any py py-meth docutils literal notranslate"><span class="pre">ot.da.BaseTransport.transform</span></code></a> and
from target to source with <a class="reference internal" href="gen_modules/ot.da.html#ot.da.BaseTransport.inverse_transform" title="ot.da.BaseTransport.inverse_transform"><code class="xref any py py-meth docutils literal notranslate"><span class="pre">ot.da.BaseTransport.inverse_transform</span></code></a>.</p>
<p>Here is
an example for class <a class="reference internal" href="gen_modules/ot.da.html#ot.da.EMDTransport" title="ot.da.EMDTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.EMDTransport</span></code></a> :</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">ot_emd</span> <span class="o">=</span> <span class="n">ot</span><span class="o">.</span><span class="n">da</span><span class="o">.</span><span class="n">EMDTransport</span><span class="p">()</span>
<span class="n">ot_emd</span><span class="o">.</span><span class="n">fit</span><span class="p">(</span><span class="n">Xs</span><span class="o">=</span><span class="n">Xs</span><span class="p">,</span> <span class="n">Xt</span><span class="o">=</span><span class="n">Xt</span><span class="p">)</span>
<span class="n">Mapped_Xs</span><span class="o">=</span> <span class="n">ot_emd</span><span class="o">.</span><span class="n">transform</span><span class="p">(</span><span class="n">Xs</span><span class="o">=</span><span class="n">Xs</span><span class="p">)</span>
</pre></div>
</div>
<p>A list of the provided implementation is given in the following note.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>Here is a list of the OT mapping classes inheriting from
<a class="reference internal" href="gen_modules/ot.da.html#ot.da.BaseTransport" title="ot.da.BaseTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.BaseTransport</span></code></a></p>
<ul class="simple">
<li><p><a class="reference internal" href="gen_modules/ot.da.html#ot.da.EMDTransport" title="ot.da.EMDTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.EMDTransport</span></code></a> : Barycentric mapping with EMD transport</p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#ot.da.SinkhornTransport" title="ot.da.SinkhornTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.SinkhornTransport</span></code></a> : Barycentric mapping with Sinkhorn transport</p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#ot.da.SinkhornL1l2Transport" title="ot.da.SinkhornL1l2Transport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.SinkhornL1l2Transport</span></code></a> : Barycentric mapping with Sinkhorn +
group Lasso regularization <a class="footnote-reference brackets" href="#id54" id="id29">5</a></p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#ot.da.SinkhornLpl1Transport" title="ot.da.SinkhornLpl1Transport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.SinkhornLpl1Transport</span></code></a> : Barycentric mapping with Sinkhorn +
non convex group Lasso regularization <a class="footnote-reference brackets" href="#id54" id="id30">5</a></p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#ot.da.LinearTransport" title="ot.da.LinearTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.LinearTransport</span></code></a> : Linear mapping estimation between Gaussians
<a class="footnote-reference brackets" href="#id63" id="id31">14</a></p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#ot.da.MappingTransport" title="ot.da.MappingTransport"><code class="xref any py py-class docutils literal notranslate"><span class="pre">ot.da.MappingTransport</span></code></a> : Nonlinear mapping estimation <a class="footnote-reference brackets" href="#id57" id="id32">8</a></p></li>
</ul>
</div>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Example of the use of OTDA classes are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_color_images</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_mapping</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_mapping_colors_images</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_otda_semi_supervised</span></code></p></li>
</ul>
</div>
</div>
</div>
<div class="section" id="other-applications">
<h2>Other applications<a class="headerlink" href="#other-applications" title="Permalink to this headline">¶</a></h2>
<p>We discuss in the following several OT related problems and tools that has been
proposed in the OT and machine learning community.</p>
<div class="section" id="wasserstein-discriminant-analysis">
<h3>Wasserstein Discriminant Analysis<a class="headerlink" href="#wasserstein-discriminant-analysis" title="Permalink to this headline">¶</a></h3>
<p>Wasserstein Discriminant Analysis <a class="footnote-reference brackets" href="#id60" id="id33">11</a> is a generalization of <a class="reference external" href="https://en.wikipedia.org/wiki/Linear_discriminant_analysis">Fisher Linear Discriminant
Analysis</a> that
allows discrimination between classes that are not linearly separable. It
consist in finding a linear projector optimizing the following criterion</p>
<div class="math notranslate nohighlight">
\[P = \text{arg}\min_P \frac{\sum_i OT_e(\mu_i\#P,\mu_i\#P)}{\sum_{i,j\neq i}
OT_e(\mu_i\#P,\mu_j\#P)}\]</div>
<p>where <span class="math notranslate nohighlight">\(\#\)</span> is the push-forward operator, <span class="math notranslate nohighlight">\(OT_e\)</span> is the entropic OT
loss and <span class="math notranslate nohighlight">\(\mu_i\)</span> is the
distribution of samples from class <span class="math notranslate nohighlight">\(i\)</span>. <span class="math notranslate nohighlight">\(P\)</span> is also constrained to
be in the Stiefel manifold. WDA can be solved in POT using function
<a class="reference internal" href="gen_modules/ot.dr.html#ot.dr.wda" title="ot.dr.wda"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.dr.wda</span></code></a>. It requires to have installed <code class="code docutils literal notranslate"><span class="pre">pymanopt</span></code> and
<code class="code docutils literal notranslate"><span class="pre">autograd</span></code> for manifold optimization and automatic differentiation
respectively. Note that we also provide the Fisher discriminant estimator in
<a class="reference internal" href="gen_modules/ot.dr.html#ot.dr.fda" title="ot.dr.fda"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.dr.fda</span></code></a> for easy comparison.</p>
<div class="admonition warning">
<p class="admonition-title">Warning</p>
<p>Note that due to the hard dependency on <code class="code docutils literal notranslate"><span class="pre">pymanopt</span></code> and
<code class="code docutils literal notranslate"><span class="pre">autograd</span></code>, <a class="reference internal" href="gen_modules/ot.dr.html#module-ot.dr" title="ot.dr"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.dr</span></code></a> is not imported by default. If you want to
use it you have to specifically import it with <code class="code docutils literal notranslate"><span class="pre">import</span> <span class="pre">ot.dr</span></code> .</p>
</div>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>An example of the use of WDA is available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_WDA</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="unbalanced-optimal-transport">
<h3>Unbalanced optimal transport<a class="headerlink" href="#unbalanced-optimal-transport" title="Permalink to this headline">¶</a></h3>
<p>Unbalanced OT is a relaxation of the entropy regularized OT problem where the violation of
the constraint on the marginals is added to the objective of the optimization
problem. The unbalanced OT metric between two unbalanced histograms a and b is defined as <a class="footnote-reference brackets" href="#id74" id="id34">25</a> <a class="footnote-reference brackets" href="#id59" id="id35">10</a>:</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}W_u(a, b) = \min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j} + reg\cdot\Omega(\gamma) + reg_m KL(\gamma 1, a) + reg_m KL(\gamma^T 1, b)\\s.t. \quad \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>where KL is the Kullback-Leibler divergence. This formulation allows for
computing approximate mapping between distributions that do not have the same
amount of mass. Interestingly the problem can be solved with a generalization of
the Bregman projections algorithm <a class="footnote-reference brackets" href="#id59" id="id36">10</a>. We provide a solver for unbalanced OT
in <a class="reference internal" href="gen_modules/ot.unbalanced.html#module-ot.unbalanced" title="ot.unbalanced"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.unbalanced</span></code></a>. Computing the optimal transport
plan or the transport cost is similar to the balanced case. The Sinkhorn-Knopp
algorithm is implemented in <a class="reference internal" href="all.html#ot.sinkhorn_unbalanced" title="ot.sinkhorn_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn_unbalanced</span></code></a> and <a class="reference internal" href="all.html#ot.sinkhorn_unbalanced2" title="ot.sinkhorn_unbalanced2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn_unbalanced2</span></code></a>
that return respectively the OT matrix and the value of the
linear term.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>The main function to solve entropic regularized UOT is <a class="reference internal" href="all.html#ot.sinkhorn_unbalanced" title="ot.sinkhorn_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn_unbalanced</span></code></a>.
This function is a wrapper and the parameter <code class="code docutils literal notranslate"><span class="pre">method</span></code> helps you select
the actual algorithm used to solve the problem:</p>
<ul class="simple">
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn'</span></code> calls <a class="reference internal" href="gen_modules/ot.unbalanced.html#ot.unbalanced.sinkhorn_knopp_unbalanced" title="ot.unbalanced.sinkhorn_knopp_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.unbalanced.sinkhorn_knopp_unbalanced</span></code></a>
the generalized Sinkhorn algorithm <a class="footnote-reference brackets" href="#id74" id="id37">25</a> <a class="footnote-reference brackets" href="#id59" id="id38">10</a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn_stabilized'</span></code> calls <a class="reference internal" href="gen_modules/ot.unbalanced.html#ot.unbalanced.sinkhorn_stabilized_unbalanced" title="ot.unbalanced.sinkhorn_stabilized_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.unbalanced.sinkhorn_stabilized_unbalanced</span></code></a>
the log stabilized version of the algorithm <a class="footnote-reference brackets" href="#id59" id="id39">10</a>.</p></li>
</ul>
</div>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of the use of <a class="reference internal" href="all.html#ot.sinkhorn_unbalanced" title="ot.sinkhorn_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.sinkhorn_unbalanced</span></code></a> are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_UOT_1D</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="unbalanced-barycenters">
<h3>Unbalanced Barycenters<a class="headerlink" href="#unbalanced-barycenters" title="Permalink to this headline">¶</a></h3>
<p>As with balanced distributions, we can define a barycenter of a set of
histograms with different masses as a Fréchet Mean:</p>
<blockquote>
<div><div class="math notranslate nohighlight">
\[\min_{\mu} \quad \sum_{k} w_kW_u(\mu,\mu_k)\]</div>
</div></blockquote>
<p>Where <span class="math notranslate nohighlight">\(W_u\)</span> is the unbalanced Wasserstein metric defined above. This problem
can also be solved using generalized version of Sinkhorn’s algorithm and it is
implemented the main function <a class="reference internal" href="all.html#ot.barycenter_unbalanced" title="ot.barycenter_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.barycenter_unbalanced</span></code></a>.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>The main function to compute UOT barycenters is <a class="reference internal" href="all.html#ot.barycenter_unbalanced" title="ot.barycenter_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.barycenter_unbalanced</span></code></a>.
This function is a wrapper and the parameter <code class="code docutils literal notranslate"><span class="pre">method</span></code> help you select
the actual algorithm used to solve the problem:</p>
<ul class="simple">
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn'</span></code> calls <code class="xref any docutils literal notranslate"><span class="pre">ot.unbalanced.barycenter_unbalanced_sinkhorn_unbalanced</span></code>
the generalized Sinkhorn algorithm <a class="footnote-reference brackets" href="#id59" id="id40">10</a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn_stabilized'</span></code> calls <a class="reference internal" href="gen_modules/ot.unbalanced.html#ot.unbalanced.barycenter_unbalanced_stabilized" title="ot.unbalanced.barycenter_unbalanced_stabilized"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.unbalanced.barycenter_unbalanced_stabilized</span></code></a>
the log stabilized version of the algorithm <a class="footnote-reference brackets" href="#id59" id="id41">10</a>.</p></li>
</ul>
</div>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of the use of <a class="reference internal" href="all.html#ot.barycenter_unbalanced" title="ot.barycenter_unbalanced"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.barycenter_unbalanced</span></code></a> are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_UOT_barycenter_1D</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="partial-optimal-transport">
<h3>Partial optimal transport<a class="headerlink" href="#partial-optimal-transport" title="Permalink to this headline">¶</a></h3>
<p>Partial OT is a variant of the optimal transport problem when only a fixed amount of mass m
is to be transported. The partial OT metric between two histograms a and b is defined as <a class="footnote-reference brackets" href="#id77" id="id42">28</a>:</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}\gamma = \arg\min_\gamma <\gamma,M>_F\\\begin{split}s.t.
\gamma\geq 0 \\
\gamma 1 \leq a\\
\gamma^T 1 \leq b\\
1^T \gamma^T 1 = m \leq \min\{\|a\|_1, \|b\|_1\}\end{split}\end{aligned}\end{align} \]</div>
<p>Interestingly the problem can be casted into a regular OT problem by adding reservoir points
in which the surplus mass is sent <a class="footnote-reference brackets" href="#id78" id="id43">29</a>. We provide a solver for partial OT
in <a class="reference internal" href="gen_modules/ot.partial.html#module-ot.partial" title="ot.partial"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.partial</span></code></a>. The exact resolution of the problem is computed in <a class="reference internal" href="gen_modules/ot.partial.html#ot.partial.partial_wasserstein" title="ot.partial.partial_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.partial.partial_wasserstein</span></code></a>
and <a class="reference internal" href="gen_modules/ot.partial.html#ot.partial.partial_wasserstein2" title="ot.partial.partial_wasserstein2"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.partial.partial_wasserstein2</span></code></a> that return respectively the OT matrix and the value of the
linear term. The entropic solution of the problem is computed in <a class="reference internal" href="gen_modules/ot.partial.html#ot.partial.entropic_partial_wasserstein" title="ot.partial.entropic_partial_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.partial.entropic_partial_wasserstein</span></code></a>
(see <a class="footnote-reference brackets" href="#id52" id="id44">3</a>).</p>
<p>The partial Gromov-Wasserstein formulation of the problem</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}GW = \min_\gamma \sum_{i,j,k,l} L(C1_{i,k},C2_{j,l})*\gamma_{i,j}*\gamma_{k,l}\\\begin{split}s.t.
\gamma\geq 0 \\
\gamma 1 \leq a\\
\gamma^T 1 \leq b\\
1^T \gamma^T 1 = m \leq \min\{\|a\|_1, \|b\|_1\}\end{split}\end{aligned}\end{align} \]</div>
<p>is computed in <a class="reference internal" href="gen_modules/ot.partial.html#ot.partial.partial_gromov_wasserstein" title="ot.partial.partial_gromov_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.partial.partial_gromov_wasserstein</span></code></a> and in
<a class="reference internal" href="gen_modules/ot.partial.html#ot.partial.entropic_partial_gromov_wasserstein" title="ot.partial.entropic_partial_gromov_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.partial.entropic_partial_gromov_wasserstein</span></code></a> when considering the entropic
regularization of the problem.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of the use of <a class="reference internal" href="gen_modules/ot.partial.html#module-ot.partial" title="ot.partial"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.partial</span></code></a> are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_partial</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="gromov-wasserstein">
<h3>Gromov-Wasserstein<a class="headerlink" href="#gromov-wasserstein" title="Permalink to this headline">¶</a></h3>
<p>Gromov Wasserstein (GW) is a generalization of OT to distributions that do not lie in
the same space <a class="footnote-reference brackets" href="#id62" id="id45">13</a>. In this case one cannot compute distance between samples
from the two distributions. <a class="footnote-reference brackets" href="#id62" id="id46">13</a> proposed instead to realign the metric spaces
by computing a transport between distance matrices. The Gromow Wasserstein
alignement between two distributions can be expressed as the one minimizing:</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}GW = \min_\gamma \sum_{i,j,k,l} L(C1_{i,k},C2_{j,l})*\gamma_{i,j}*\gamma_{k,l}\\s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align} \]</div>
<p>where :<span class="math notranslate nohighlight">\(C1\)</span> is the distance matrix between samples in the source
distribution and <span class="math notranslate nohighlight">\(C2\)</span> the one between samples in the target,
<span class="math notranslate nohighlight">\(L(C1_{i,k},C2_{j,l})\)</span> is a measure of similarity between
<span class="math notranslate nohighlight">\(C1_{i,k}\)</span> and <span class="math notranslate nohighlight">\(C2_{j,l}\)</span> often chosen as
<span class="math notranslate nohighlight">\(L(C1_{i,k},C2_{j,l})=\|C1_{i,k}-C2_{j,l}\|^2\)</span>. The optimization problem
above is a non-convex quadratic program but we provide a solver that finds a
local minimum using conditional gradient in <a class="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.gromov_wasserstein" title="ot.gromov.gromov_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gromov.gromov_wasserstein</span></code></a>.
There also exists an entropic regularized variant of GW that has been proposed in
<a class="footnote-reference brackets" href="#id61" id="id47">12</a> and we provide an implementation of their algorithm in
<a class="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.entropic_gromov_wasserstein" title="ot.gromov.entropic_gromov_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gromov.entropic_gromov_wasserstein</span></code></a>.</p>
<p>Note that similarly to Wasserstein distance GW allows for the definition of GW
barycenters that can be expressed as</p>
<div class="math notranslate nohighlight">
\[\min_{C\geq 0} \quad \sum_{k} w_k GW(C,Ck)\]</div>
<p>where <span class="math notranslate nohighlight">\(Ck\)</span> is the distance matrix between samples in distribution
<span class="math notranslate nohighlight">\(k\)</span>. Note that interestingly the barycenter is defined as a symmetric
positive matrix. We provide a block coordinate optimization procedure in
<a class="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.gromov_barycenters" title="ot.gromov.gromov_barycenters"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gromov.gromov_barycenters</span></code></a> and
<a class="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.entropic_gromov_barycenters" title="ot.gromov.entropic_gromov_barycenters"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gromov.entropic_gromov_barycenters</span></code></a> for non-regularized and regularized
barycenters respectively.</p>
<p>Finally note that recently a fusion between Wasserstein and GW, coined Fused
Gromov-Wasserstein (FGW) has been proposed
in <a class="footnote-reference brackets" href="#id73" id="id48">24</a>. It allows to compute a similarity between objects that are only partly in
the same space. As such it can be used to measure similarity between labeled
graphs for instance and also provide computable barycenters.
The implementations of FGW and FGW barycenter is provided in functions
<a class="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.fused_gromov_wasserstein" title="ot.gromov.fused_gromov_wasserstein"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gromov.fused_gromov_wasserstein</span></code></a> and <a class="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.fgw_barycenters" title="ot.gromov.fgw_barycenters"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gromov.fgw_barycenters</span></code></a>.</p>
<div class="admonition hint">
<p class="admonition-title">Hint</p>
<p>Examples of computation of GW, regularized G and FGW are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_gromov</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_fgw</span></code></p></li>
</ul>
<p>Examples of GW, regularized GW and FGW barycenters are available in :</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_gromov_barycenter</span></code></p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">auto_examples/plot_barycenter_fgw</span></code></p></li>
</ul>
</div>
</div>
<div class="section" id="gpu-acceleration">
<h3>GPU acceleration<a class="headerlink" href="#gpu-acceleration" title="Permalink to this headline">¶</a></h3>
<p>We provide several implementation of our OT solvers in <a class="reference internal" href="gen_modules/ot.gpu.html#module-ot.gpu" title="ot.gpu"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.gpu</span></code></a>. Those
implementations use the <code class="code docutils literal notranslate"><span class="pre">cupy</span></code> toolbox that obviously need to be installed.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>Several implementations of POT functions (mainly those relying on linear
algebra) have been implemented in <a class="reference internal" href="gen_modules/ot.gpu.html#module-ot.gpu" title="ot.gpu"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.gpu</span></code></a>. Here is a short list on the
main entries:</p>
<ul class="simple">
<li><p><code class="xref any docutils literal notranslate"><span class="pre">ot.gpu.dist</span></code> : computation of distance matrix</p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">ot.gpu.sinkhorn</span></code> : computation of sinkhorn</p></li>
<li><p><code class="xref any docutils literal notranslate"><span class="pre">ot.gpu.sinkhorn_lpl1_mm</span></code> : computation of sinkhorn + group lasso</p></li>
</ul>
</div>
<p>Note that while the <a class="reference internal" href="gen_modules/ot.gpu.html#module-ot.gpu" title="ot.gpu"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.gpu</span></code></a> module has been designed to be compatible with
POT, calling its function with <a class="reference external" href="https://numpy.org/doc/stable/reference/index.html#module-numpy" title="(in NumPy v1.19)"><code class="xref any docutils literal notranslate"><span class="pre">numpy</span></code></a> arrays will incur a large overhead due to
the memory copy of the array on GPU prior to computation and conversion of the
array after computation. To avoid this overhead, we provide functions
<code class="xref any docutils literal notranslate"><span class="pre">ot.gpu.to_gpu</span></code> and <code class="xref any docutils literal notranslate"><span class="pre">ot.gpu.to_np</span></code> that perform the conversion
explicitly.</p>
<div class="admonition warning">
<p class="admonition-title">Warning</p>
<p>Note that due to the hard dependency on <code class="code docutils literal notranslate"><span class="pre">cupy</span></code>, <a class="reference internal" href="gen_modules/ot.gpu.html#module-ot.gpu" title="ot.gpu"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.gpu</span></code></a> is not
imported by default. If you want to
use it you have to specifically import it with <code class="code docutils literal notranslate"><span class="pre">import</span> <span class="pre">ot.gpu</span></code> .</p>
</div>
</div>
</div>
<div class="section" id="faq">
<h2>FAQ<a class="headerlink" href="#faq" title="Permalink to this headline">¶</a></h2>
<ol class="arabic">
<li><p><strong>How to solve a discrete optimal transport problem ?</strong></p>
<blockquote>
<div><p>The solver for discrete OT is the function <a class="reference internal" href="all.html#ot.emd" title="ot.emd"><code class="xref py py-mod docutils literal notranslate"><span class="pre">ot.emd</span></code></a> that returns
the OT transport matrix. If you want to solve a regularized OT you can
use <a class="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><code class="xref py py-mod docutils literal notranslate"><span class="pre">ot.sinkhorn</span></code></a>.</p>
<p>Here is a simple use case:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># a,b are 1D histograms (sum to 1 and positive)</span>
<span class="c1"># M is the ground cost matrix</span>
<span class="n">T</span><span class="o">=</span><span class="n">ot</span><span class="o">.</span><span class="n">emd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">,</span><span class="n">M</span><span class="p">)</span> <span class="c1"># exact linear program</span>
<span class="n">T_reg</span><span class="o">=</span><span class="n">ot</span><span class="o">.</span><span class="n">sinkhorn</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">,</span><span class="n">M</span><span class="p">,</span><span class="n">reg</span><span class="p">)</span> <span class="c1"># entropic regularized OT</span>
</pre></div>
</div>
<p>More detailed examples can be seen on this example:
<a class="reference internal" href="auto_examples/plot_OT_2D_samples.html"><span class="doc">2D Optimal transport between empirical distributions</span></a></p>
</div></blockquote>
</li>
<li><p><strong>pip install POT fails with error : ImportError: No module named Cython.Build</strong></p>
<blockquote>
<div><p>As discussed shortly in the README file. POT requires to have <code class="code docutils literal notranslate"><span class="pre">numpy</span></code>
and <code class="code docutils literal notranslate"><span class="pre">cython</span></code> installed to build. This corner case is not yet handled
by <code class="code docutils literal notranslate"><span class="pre">pip</span></code> and for now you need to install both library prior to
installing POT.</p>
<p>Note that this problem do not occur when using conda-forge since the packages
there are pre-compiled.</p>
<p>See <a class="reference external" href="https://github.com/rflamary/POT/issues/59">Issue #59</a> for more
details.</p>
</div></blockquote>
</li>
<li><p><strong>Why is Sinkhorn slower than EMD ?</strong></p>
<blockquote>
<div><p>This might come from the choice of the regularization term. The speed of
convergence of sinkhorn depends directly on this term <a class="footnote-reference brackets" href="#id71" id="id49">22</a> and when the
regularization gets very small the problem try and approximate the exact OT
which leads to slow convergence in addition to numerical problems. In other
words, for large regularization sinkhorn will be very fast to converge, for
small regularization (when you need an OT matrix close to the true OT), it
might be quicker to use the EMD solver.</p>
<p>Also note that the numpy implementation of the sinkhorn can use parallel
computation depending on the configuration of your system but very important
speedup can be obtained by using a GPU implementation since all operations
are matrix/vector products.</p>
</div></blockquote>
</li>
<li><p><strong>Using GPU fails with error: module ‘ot’ has no attribute ‘gpu’</strong></p>
<blockquote>
<div><p>In order to limit import time and hard dependencies in POT. we do not import
some sub-modules automatically with <code class="code docutils literal notranslate"><span class="pre">import</span> <span class="pre">ot</span></code>. In order to use the
acceleration in <a class="reference internal" href="gen_modules/ot.gpu.html#module-ot.gpu" title="ot.gpu"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.gpu</span></code></a> you need first to import is with
<code class="code docutils literal notranslate"><span class="pre">import</span> <span class="pre">ot.gpu</span></code>.</p>
<p>See <a class="reference external" href="https://github.com/rflamary/POT/issues/85">Issue #85</a> and <a class="reference internal" href="gen_modules/ot.gpu.html#module-ot.gpu" title="ot.gpu"><code class="xref any py py-mod docutils literal notranslate"><span class="pre">ot.gpu</span></code></a>
for more details.</p>
</div></blockquote>
</li>
</ol>
</div>
<div class="section" id="references">
<h2>References<a class="headerlink" href="#references" title="Permalink to this headline">¶</a></h2>
<dl class="footnote brackets">
<dt class="label" id="id50"><span class="brackets"><a class="fn-backref" href="#id2">1</a></span></dt>
<dd><p>Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011,
December). <a class="reference external" href="https://people.csail.mit.edu/sparis/publi/2011/sigasia/Bonneel_11_Displacement_Interpolation.pdf">Displacement nterpolation using Lagrangian mass transport</a>.
In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.</p>
</dd>
<dt class="label" id="id51"><span class="brackets">2</span><span class="fn-backref">(<a href="#id4">1</a>,<a href="#id5">2</a>,<a href="#id6">3</a>)</span></dt>
<dd><p>Cuturi, M. (2013). <a class="reference external" href="https://arxiv.org/pdf/1306.0895.pdf">Sinkhorn distances: Lightspeed computation of
optimal transport</a>. In Advances
in Neural Information Processing Systems (pp. 2292-2300).</p>
</dd>
<dt class="label" id="id52"><span class="brackets">3</span><span class="fn-backref">(<a href="#id22">1</a>,<a href="#id44">2</a>)</span></dt>
<dd><p>Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G.
(2015). <a class="reference external" href="https://arxiv.org/pdf/1412.5154.pdf">Iterative Bregman projections for regularized transportation
problems</a>. SIAM Journal on
Scientific Computing, 37(2), A1111-A1138.</p>
</dd>
<dt class="label" id="id53"><span class="brackets">4</span></dt>
<dd><p>S. Nakhostin, N. Courty, R. Flamary, D. Tuia, T. Corpetti,
<a class="reference external" href="https://hal.archives-ouvertes.fr/hal-01377236/document">Supervised planetary unmixing with optimal
transport</a>,
Whorkshop on Hyperspectral Image and Signal Processing : Evolution in
Remote Sensing (WHISPERS), 2016.</p>
</dd>
<dt class="label" id="id54"><span class="brackets">5</span><span class="fn-backref">(<a href="#id16">1</a>,<a href="#id17">2</a>,<a href="#id28">3</a>,<a href="#id29">4</a>,<a href="#id30">5</a>)</span></dt>
<dd><p>N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, <a class="reference external" href="https://arxiv.org/pdf/1507.00504.pdf">Optimal Transport
for Domain Adaptation</a>, in IEEE
Transactions on Pattern Analysis and Machine Intelligence , vol.PP,
no.99, pp.1-1</p>
</dd>
<dt class="label" id="id55"><span class="brackets">6</span><span class="fn-backref">(<a href="#id19">1</a>,<a href="#id26">2</a>)</span></dt>
<dd><p>Ferradans, S., Papadakis, N., Peyré, G., & Aujol, J. F. (2014).
<a class="reference external" href="https://arxiv.org/pdf/1307.5551.pdf">Regularized discrete optimal
transport</a>. SIAM Journal on
Imaging Sciences, 7(3), 1853-1882.</p>
</dd>
<dt class="label" id="id56"><span class="brackets">7</span><span class="fn-backref">(<a href="#id18">1</a>,<a href="#id20">2</a>)</span></dt>
<dd><p>Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). <a class="reference external" href="https://arxiv.org/pdf/1510.06567.pdf">Generalized
conditional gradient: analysis of convergence and
applications</a>. arXiv preprint
arXiv:1510.06567.</p>
</dd>
<dt class="label" id="id57"><span class="brackets">8</span><span class="fn-backref">(<a href="#id27">1</a>,<a href="#id32">2</a>)</span></dt>
<dd><p>M. Perrot, N. Courty, R. Flamary, A. Habrard (2016), <a class="reference external" href="http://remi.flamary.com/biblio/perrot2016mapping.pdf">Mapping
estimation for discrete optimal
transport</a>,
Neural Information Processing Systems (NIPS).</p>
</dd>
<dt class="label" id="id58"><span class="brackets">9</span><span class="fn-backref">(<a href="#id7">1</a>,<a href="#id8">2</a>)</span></dt>
<dd><p>Schmitzer, B. (2016). <a class="reference external" href="https://arxiv.org/pdf/1610.06519.pdf">Stabilized Sparse Scaling Algorithms for
Entropy Regularized Transport
Problems</a>. arXiv preprint
arXiv:1610.06519.</p>
</dd>
<dt class="label" id="id59"><span class="brackets">10</span><span class="fn-backref">(<a href="#id35">1</a>,<a href="#id36">2</a>,<a href="#id38">3</a>,<a href="#id39">4</a>,<a href="#id40">5</a>,<a href="#id41">6</a>)</span></dt>
<dd><p>Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016).
<a class="reference external" href="https://arxiv.org/pdf/1607.05816.pdf">Scaling algorithms for unbalanced transport
problems</a>. arXiv preprint
arXiv:1607.05816.</p>
</dd>
<dt class="label" id="id60"><span class="brackets"><a class="fn-backref" href="#id33">11</a></span></dt>
<dd><p>Flamary, R., Cuturi, M., Courty, N., & Rakotomamonjy, A. (2016).
<a class="reference external" href="https://arxiv.org/pdf/1608.08063.pdf">Wasserstein Discriminant
Analysis</a>. arXiv preprint
arXiv:1608.08063.</p>
</dd>
<dt class="label" id="id61"><span class="brackets"><a class="fn-backref" href="#id47">12</a></span></dt>