Repository navigation
Expand file tree
/
Copy pathquickstart.html
More file actions
1494 lines (1456 loc) · 152 KB
/
Copy pathquickstart.html
File metadata and controls
1494 lines (1456 loc) · 152 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" data-content_root="./">
<head>
<meta charset="utf-8" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Quick start guide — POT Python Optimal Transport 0.9.6dev0 documentation</title>
<link rel="stylesheet" type="text/css" href="_static/pygments.css?v=b86133f3" />
<link rel="stylesheet" type="text/css" href="_static/css/theme.css?v=e59714d7" />
<link rel="stylesheet" type="text/css" href="_static/sg_gallery.css?v=d2d258e8" />
<link rel="stylesheet" type="text/css" href="_static/sg_gallery-binder.css?v=f4aeca0c" />
<link rel="stylesheet" type="text/css" href="_static/sg_gallery-dataframe.css?v=2082cf3c" />
<link rel="stylesheet" type="text/css" href="_static/sg_gallery-rendered-html.css?v=1277b6f3" />
<script src="_static/jquery.js?v=5d32c60e"></script>
<script src="_static/_sphinx_javascript_frameworks_compat.js?v=2cd50e6c"></script>
<script src="_static/documentation_options.js?v=6e3d2238"></script>
<script src="_static/doctools.js?v=9bcbadda"></script>
<script src="_static/sphinx_highlight.js?v=dc90522c"></script>
<script async="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script 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">
POT Python Optimal Transport
<img src="_static/logo_dark.svg" class="logo" alt="Logo"/>
</a>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="search.html" method="get">
<input type="text" name="q" placeholder="Search docs" aria-label="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="Navigation menu">
<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="#why-optimal-transport">Why Optimal Transport ?</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#when-to-use-ot">When to use OT</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#wasserstein-distance-between-distributions">Wasserstein distance between distributions</a></li>
<li class="toctree-l4"><a class="reference internal" href="#ot-for-mapping-estimation">OT for mapping estimation</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#when-to-use-pot">When to use POT</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#when-not-to-use-pot">When not to use POT</a></li>
</ul>
</li>
</ul>
</li>
<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><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-use-for-ot-emd">Examples of use for <code class="xref any docutils literal notranslate"><span class="pre">ot.emd</span></code></a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#computing-wasserstein-distance">Computing Wasserstein distance</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-use-for-ot-emd2">Examples of use for <code class="xref any docutils literal notranslate"><span class="pre">ot.emd2</span></code></a></li>
</ul>
</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><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-use-for-ot-sinkhorn">Examples of use for <code class="xref any docutils literal notranslate"><span class="pre">ot.sinkhorn</span></code></a></li>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-use-for-ot-sinkhorn2">Examples of use for <code class="xref any docutils literal notranslate"><span class="pre">ot.sinkhorn2</span></code></a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#other-regularizations">Other regularizations</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="#examples-of-use-of-quadratic-regularization">Examples of use of 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="#examples-of-group-lasso-regularization">Examples of group Lasso regularization</a></li>
<li class="toctree-l4"><a class="reference internal" href="#generic-solvers">Generic solvers</a></li>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-the-generic-solvers">Examples of the 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><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-wasserstein-and-regularized-wasserstein-barycenters">Examples of Wasserstein and regularized Wasserstein barycenters</a></li>
<li class="toctree-l4"><a class="reference internal" href="#an-example-of-convolutional-barycenter-ot-bregman-convolutional-barycenter2d-computation">An example of convolutional barycenter (<code class="xref any docutils literal notranslate"><span class="pre">ot.bregman.convolutional_barycenter2d</span></code>) computation</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#barycenters-with-free-support">Barycenters with free support</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-free-support-barycenter-estimation">Examples of free support barycenter estimation</a></li>
</ul>
</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><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-the-use-of-otda-classes">Examples of the use of OTDA classes</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#unbalanced-and-partial-ot">Unbalanced and partial OT</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#unbalanced-optimal-transport">Unbalanced optimal transport</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-unbalanced-ot">Examples of Unbalanced OT</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#unbalanced-barycenters">Unbalanced Barycenters</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-unbalanced-ot-barycenters">Examples of Unbalanced OT barycenters</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#partial-optimal-transport">Partial optimal transport</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-partial-ot">Examples of Partial OT</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#gromov-wasserstein-and-extensions">Gromov Wasserstein and extensions</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#gromov-wasserstein-gw">Gromov Wasserstein(GW)</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-computation-of-gw-regularized-g-and-fgw">Examples of computation of GW, regularized G and FGW</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#gromov-wasserstein-barycenters">Gromov Wasserstein barycenters</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-gw-regularized-g-and-fgw-barycenters">Examples of GW, regularized G and FGW barycenters</a></li>
</ul>
</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><ul>
<li class="toctree-l4"><a class="reference internal" href="#examples-of-the-use-of-wda">Examples of the use of WDA</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#solving-ot-with-multiple-backends-on-cpu-gpu">Solving OT with Multiple backends on CPU/GPU</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#how-it-works">How it works</a></li>
<li class="toctree-l3"><a class="reference internal" href="#gpu-acceleration">GPU acceleration</a></li>
<li class="toctree-l3"><a class="reference internal" href="#list-of-compatible-backends">List of compatible Backends</a></li>
<li class="toctree-l3"><a class="reference internal" href="#list-of-compatible-modules">List of compatible modules</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>
<li class="toctree-l1"><a class="reference internal" href="contributors.html">Contributors</a></li>
<li class="toctree-l1"><a class="reference internal" href="contributing.html">Contributing to POT</a></li>
<li class="toctree-l1"><a class="reference internal" href="code_of_conduct.html">Code of conduct</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<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="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="index.html" class="icon icon-home" aria-label="Home"></a></li>
<li class="breadcrumb-item active">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">
<section id="quick-start-guide">
<h1>Quick start guide<a class="headerlink" href="#quick-start-guide" title="Link to this heading"></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>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>For a good introduction to numerical optimal transport we refer the reader
to <a class="reference external" href="https://arxiv.org/pdf/1803.00567.pdf">the book</a> by Peyré and Cuturi
<a class="footnote-reference brackets" href="#id66" id="id1" role="doc-noteref"><span class="fn-bracket">[</span>15<span class="fn-bracket">]</span></a>. For more detailed introduction to OT and how it can be used
in ML applications we refer the reader to the following <a class="reference external" href="https://remi.flamary.com/cours/tuto_otml.html">OTML tutorial</a>.</p>
</div>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>Since version 0.8, POT provides a backend to automatically solve some OT
problems independently from the toolbox used by the user (numpy/torch/jax).
We provide a discussion about which functions are compatible in section
<a class="reference external" href="#solving-ot-with-multiple-backends">Backend section</a> .</p>
</div>
<section id="why-optimal-transport">
<h2>Why Optimal Transport ?<a class="headerlink" href="#why-optimal-transport" title="Link to this heading"></a></h2>
<section id="when-to-use-ot">
<h3>When to use OT<a class="headerlink" href="#when-to-use-ot" title="Link to this heading"></a></h3>
<p>Optimal Transport (OT) is a mathematical problem introduced by Gaspard Monge in
1781 that aim at finding the most efficient way to move mass between
distributions. The cost of moving a unit of mass between two positions is called
the ground cost and the objective is to minimize the overall cost of moving one
mass distribution onto another one. The optimization problem can be expressed
for two distributions <span class="math notranslate nohighlight">\(\mu_s\)</span> and <span class="math notranslate nohighlight">\(\mu_t\)</span> as</p>
<div class="math notranslate nohighlight">
\[\min_{m, m \# \mu_s = \mu_t} \int c(x,m(x))d\mu_s(x) ,\]</div>
<p>where <span class="math notranslate nohighlight">\(c(\cdot,\cdot)\)</span> is the ground cost and the constraint
<span class="math notranslate nohighlight">\(m \# \mu_s = \mu_t\)</span> ensures that <span class="math notranslate nohighlight">\(\mu_s\)</span> is completely transported to <span class="math notranslate nohighlight">\(\mu_t\)</span>.
This problem is particularly difficult to solve because of this constraint and
has been replaced in practice (on discrete distributions) by a
linear program easier to solve. It corresponds to the Kantorovitch formulation
where the Monge mapping <span class="math notranslate nohighlight">\(m\)</span> is replaced by a joint distribution
(OT matrix expressed in the next section) (see <a class="reference internal" href="#kantorovitch-solve"><span class="std std-ref">Solving optimal transport</span></a>).</p>
<p>From the optimization problem above we can see that there are two main aspects
to the OT solution that can be used in practical applications:</p>
<ul class="simple">
<li><p>The optimal value (Wasserstein distance): Measures similarity between distributions.</p></li>
<li><p>The optimal mapping (Monge mapping, OT matrix): Finds correspondences between distributions.</p></li>
</ul>
<p>In the first case, OT can be used to measure similarity between distributions
(or datasets), in this case the Wasserstein distance (the optimal value of the
problem) is used. In the second case one can be interested in the way the mass
is moved between the distributions (the mapping). This mapping can then be used
to transfer knowledge between distributions.</p>
<section id="wasserstein-distance-between-distributions">
<h4>Wasserstein distance between distributions<a class="headerlink" href="#wasserstein-distance-between-distributions" title="Link to this heading"></a></h4>
<p>OT is often used to measure similarity between distributions, especially
when they do not share the same support. When the support between the
distributions is disjoint OT-based Wasserstein distances compare favorably to
popular f-divergences including the popular Kullback-Leibler, Jensen-Shannon
divergences, and the Total Variation distance. What is particularly interesting
for data science applications is that one can compute meaningful sub-gradients
of the Wasserstein distance. For these reasons it became a very efficient tool
for machine learning applications that need to measure and optimize similarity
between empirical distributions.</p>
<p>Numerous contributions make use of this an approach is the machine learning (ML)
literature. For example OT was used for training <a class="reference external" href="https://arxiv.org/pdf/1701.07875.pdf">Generative
Adversarial Networks (GANs)</a>
in order to overcome the vanishing gradient problem. It has also
been used to find <a class="reference external" href="https://arxiv.org/pdf/1608.08063.pdf">discriminant</a> or
<a class="reference external" href="https://arxiv.org/pdf/1901.08949.pdf">robust</a> subspaces for a dataset. The
Wasserstein distance has also been used to measure <a class="reference external" href="http://proceedings.mlr.press/v37/kusnerb15.pdf">similarity between word
embeddings of documents</a> or
between <a class="reference external" href="https://www.math.ucdavis.edu/~saito/data/acha.read.s19/kolouri-etal_optimal-mass-transport.pdf">signals</a>
or <a class="reference external" href="https://arxiv.org/pdf/1609.09799.pdf">spectra</a>.</p>
</section>
<section id="ot-for-mapping-estimation">
<h4>OT for mapping estimation<a class="headerlink" href="#ot-for-mapping-estimation" title="Link to this heading"></a></h4>
<p>A very interesting aspect of OT problem is the OT mapping in itself. When
computing optimal transport between discrete distributions one output is the OT
matrix that will provide you with correspondences between the samples in each
distributions.</p>
<p>This correspondence is estimated with respect to the OT criterion and is found
in a non-supervised way, which makes it very interesting on problems of transfer
between datasets. It has been used to perform
<a class="reference external" href="https://arxiv.org/pdf/1307.5551.pdf">color transfer between images</a> or in
the context of <a class="reference external" href="https://arxiv.org/pdf/1507.00504.pdf">domain adaptation</a>.
More recent applications include the use of extension of OT (Gromov-Wasserstein)
to find correspondences between languages in <a class="reference external" href="https://arxiv.org/pdf/1809.00013.pdf">word embeddings</a>.</p>
</section>
</section>
<section id="when-to-use-pot">
<h3>When to use POT<a class="headerlink" href="#when-to-use-pot" title="Link to this heading"></a></h3>
<p>The main objective of POT is to provide OT solvers for the rapidly growing area
of OT in the context of machine learning. To this end we implement a number of
solvers that have been proposed in research papers. Doing so we aim to promote
reproducible research and foster novel developments.</p>
<p>One very important aspect of POT is its ability to be easily extended. For
instance we provide a very generic OT solver <a class="reference internal" href="gen_modules/ot.optim.html#id0" title="ot.optim.cg"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.optim.cg</span></code></a> that can solve
OT problems with any smooth/continuous regularization term making it
particularly practical for research purpose. Note that this generic solver has
been used to solve both graph Laplacian regularization OT and Gromov
Wasserstein <a class="footnote-reference brackets" href="#id80" id="id2" role="doc-noteref"><span class="fn-bracket">[</span>30<span class="fn-bracket">]</span></a>.</p>
<section id="when-not-to-use-pot">
<h4>When not to use POT<a class="headerlink" href="#when-not-to-use-pot" title="Link to this heading"></a></h4>
<p>While POT has to the best of our knowledge one of the most efficient exact OT
solvers, it has not been designed to handle large scale OT problems. For
instance the memory cost for an OT problem is always <span class="math notranslate nohighlight">\(\mathcal{O}(n^2)\)</span> in
memory because the cost matrix has to be computed. The exact solver in of time
complexity <span class="math notranslate nohighlight">\(\mathcal{O}(n^3\log(n))\)</span> and the Sinkhorn solver has been
proven to be nearly <span class="math notranslate nohighlight">\(\mathcal{O}(n^2)\)</span> which is still too complex for very
large scale solvers.</p>
<p>If you need to solve OT with large number of samples, we recommend to use
entropic regularization and memory efficient implementation of Sinkhorn as
proposed in <a class="reference external" href="https://www.kernel-operations.io/geomloss/">GeomLoss</a>. This
implementation is compatible with Pytorch and can handle large number of
samples. Another approach to estimate the Wasserstein distance for very large
number of sample is to use the trick from <a class="reference external" href="https://arxiv.org/pdf/1701.07875.pdf">Wasserstein GAN</a> that solves the problem
in the dual with a neural network estimating the dual variable. Note that in this
case you are only solving an approximation of the Wasserstein distance because
the 1-Lipschitz constraint on the dual cannot be enforced exactly (approximated
through filter thresholding or regularization). Finally note that in order to
avoid solving large scale OT problems, a number of recent approached minimized
the expected Wasserstein distance on minibatches that is different from the
Wasserstein but has better computational and
<a class="reference external" href="https://arxiv.org/pdf/1910.04091.pdf">statistical properties</a>.</p>
</section>
</section>
</section>
<section id="optimal-transport-and-wasserstein-distance">
<h2>Optimal transport and Wasserstein distance<a class="headerlink" href="#optimal-transport-and-wasserstein-distance" title="Link to this heading"></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> returns 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> returns the
Wasserstein distance. This approach has been implemented in practice for all
solvers that return an OT matrix (even Gromov-Wasserstein).</p>
</div>
<section id="solving-optimal-transport">
<span id="kantorovitch-solve"></span><h3>Solving optimal transport<a class="headerlink" href="#solving-optimal-transport" title="Link to this heading"></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 \in \mathbb{R}_+^{m\times n}} \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>
<blockquote>
<div><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 weights of each samples in the source an target distributions.</p></li>
</ul>
</div></blockquote>
<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 and 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="#id53" id="id3" role="doc-noteref"><span class="fn-bracket">[</span>1<span class="fn-bracket">]</span></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>
<section id="examples-of-use-for-ot-emd">
<h4>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><a class="headerlink" href="#examples-of-use-for-ot-emd" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example first illustrates the computation of FGW for 1D measures estimated using a Conditional Gradient solver [24]."><img alt="" src="_images/sphx_glr_plot_fgw_thumb.png" />
<p><a class="reference internal" href="auto_examples/gromov/plot_fgw.html#sphx-glr-auto-examples-gromov-plot-fgw-py"><span class="std std-ref">Plot Fused-Gromov-Wasserstein</span></a></p>
<div class="sphx-glr-thumbnail-title">Plot Fused-Gromov-Wasserstein</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Illustration of 2D optimal transport between distributions that are weighted sum of Diracs. The OT matrix is plotted with the samples."><img alt="" src="_images/sphx_glr_plot_WeakOT_VS_OT_thumb.png" />
<p><a class="reference internal" href="auto_examples/others/plot_WeakOT_VS_OT.html#sphx-glr-auto-examples-others-plot-weakot-vs-ot-py"><span class="std std-ref">Weak Optimal Transport VS exact Optimal Transport</span></a></p>
<div class="sphx-glr-thumbnail-title">Weak Optimal Transport VS exact Optimal Transport</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Illustration of the factored coupling OT between 2D empirical distributions"><img alt="" src="_images/sphx_glr_plot_factored_coupling_thumb.png" />
<p><a class="reference internal" href="auto_examples/others/plot_factored_coupling.html#sphx-glr-auto-examples-others-plot-factored-coupling-py"><span class="std std-ref">Optimal transport with factored couplings</span></a></p>
<div class="sphx-glr-thumbnail-title">Optimal transport with factored couplings</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="In this example we plot the logo of the POT toolbox."><img alt="" src="_images/sphx_glr_plot_logo_thumb.png" />
<p><a class="reference internal" href="auto_examples/others/plot_logo.html#sphx-glr-auto-examples-others-plot-logo-py"><span class="std std-ref">Logo of the POT toolbox</span></a></p>
<div class="sphx-glr-thumbnail-title">Logo of the POT toolbox</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example gives an introduction on how to use Optimal Transport in Python."><img alt="" src="_images/sphx_glr_plot_Intro_OT_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_Intro_OT.html#sphx-glr-auto-examples-plot-intro-ot-py"><span class="std std-ref">Introduction to Optimal Transport with Python</span></a></p>
<div class="sphx-glr-thumbnail-title">Introduction to Optimal Transport with Python</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Illustration of 2D optimal transport between distributions that are weighted sum of Diracs. The OT matrix is plotted with the samples."><img alt="" src="_images/sphx_glr_plot_OT_2D_samples_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_OT_2D_samples.html#sphx-glr-auto-examples-plot-ot-2d-samples-py"><span class="std std-ref">Optimal Transport between 2D empirical distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">Optimal Transport between 2D empirical distributions</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="2D OT on empirical distribution with different ground metric."><img alt="" src="_images/sphx_glr_plot_OT_L1_vs_L2_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_OT_L1_vs_L2.html#sphx-glr-auto-examples-plot-ot-l1-vs-l2-py"><span class="std std-ref">Optimal Transport with different ground metrics</span></a></p>
<div class="sphx-glr-thumbnail-title">Optimal Transport with different ground metrics</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Illustrates the use of the generic solver for regularized OT with user-designed regularization term. It uses Conditional gradient as in [6] and generalized Conditional Gradient as proposed in [5,7]."><img alt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><span class="std std-ref">Regularized OT with generic solver</span></a></p>
<div class="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div></div></section>
</section>
<section id="computing-wasserstein-distance">
<h3>Computing Wasserstein distance<a class="headerlink" href="#computing-wasserstein-distance" title="Link to this heading"></a></h3>
<p>The value of the OT solution is often more interesting than the OT matrix:</p>
<div class="math notranslate nohighlight">
\[ \begin{align}\begin{aligned}OT(a,b) = \min_{\gamma \in \mathbb{R}_+^{m\times n}} \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 and 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 \in \mathbb{R}_+^{m\times n}} \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</span> <span class="pre">=</span> <span class="pre">ot.dist(xs,</span> <span class="pre">xt)</span></code>, that uses 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</span> <span class="pre">=</span> <span class="pre">ot.dist(xs,</span> <span class="pre">xt,</span> <span class="pre">metric='euclidean')</span></code> to use the Euclidean
distance.</p>
<section id="examples-of-use-for-ot-emd2">
<h4>Examples 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><a class="headerlink" href="#examples-of-use-for-ot-emd2" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="In this example we estimate mixing parameters from distributions that minimize the Wasserstein distance. In other words we suppose that a target distribution \mu^t can be expressed as a weighted sum of source distributions \mu^s_k with the following model:"><img alt="" src="_images/sphx_glr_plot_unmix_optim_torch_thumb.png" />
<p><a class="reference internal" href="auto_examples/backends/plot_unmix_optim_torch.html#sphx-glr-auto-examples-backends-plot-unmix-optim-torch-py"><span class="std std-ref">Wasserstein unmixing with PyTorch</span></a></p>
<div class="sphx-glr-thumbnail-title">Wasserstein unmixing with PyTorch</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="In this example we train a Wasserstein GAN using Wasserstein 2 on minibatches as a distribution fitting term."><img alt="" src="_images/sphx_glr_plot_wass2_gan_torch_thumb.png" />
<p><a class="reference internal" href="auto_examples/backends/plot_wass2_gan_torch.html#sphx-glr-auto-examples-backends-plot-wass2-gan-torch-py"><span class="std std-ref">Wasserstein 2 Minibatch GAN with PyTorch</span></a></p>
<div class="sphx-glr-thumbnail-title">Wasserstein 2 Minibatch GAN with PyTorch</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Shows how to compute multiple Wasserstein and Sinkhorn with two different ground metrics and plot their values for different distributions."><img alt="" src="_images/sphx_glr_plot_compute_emd_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_compute_emd.html#sphx-glr-auto-examples-plot-compute-emd-py"><span class="std std-ref">OT distances in 1D</span></a></p>
<div class="sphx-glr-thumbnail-title">OT distances in 1D</div>
</div></div></section>
</section>
<section id="special-cases">
<h3>Special cases<a class="headerlink" href="#special-cases" title="Link to this heading"></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#ot.emd_1d" 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#ot.emd_1d" 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="#id66" id="id4" role="doc-noteref"><span class="fn-bracket">[</span>15<span class="fn-bracket">]</span></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.gaussian.html#id39" title="ot.gaussian.bures_wasserstein_mapping"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gaussian.bures_wasserstein_mapping</span></code></a> that returns the parameters for the
Monge mapping.</p>
</section>
</section>
<section id="regularized-optimal-transport">
<h2>Regularized Optimal Transport<a class="headerlink" href="#regularized-optimal-transport" title="Link to this heading"></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 \in \mathbb{R}_+^{m\times n}} \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>
<section id="entropic-regularized-ot">
<h3>Entropic regularized OT<a class="headerlink" href="#entropic-regularized-ot" title="Link to this heading"></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="#id54" id="id5" role="doc-noteref"><span class="fn-bracket">[</span>2<span class="fn-bracket">]</span></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="#id54" id="id6" role="doc-noteref"><span class="fn-bracket">[</span>2<span class="fn-bracket">]</span></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, one can use an alternative projection algorithm called Sinkhorn-Knopp
that can be very efficient for large values of 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="w"> </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="mf">.5</span><span class="p">,</span> <span class="mf">.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="mf">.5</span><span class="p">,</span> <span class="mf">.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="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> allows you to 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="#id54" id="id7" role="doc-noteref"><span class="fn-bracket">[</span>2<span class="fn-bracket">]</span></a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='sinkhorn_log'</span></code> calls <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_log" title="ot.bregman.sinkhorn_log"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.sinkhorn_log</span></code></a> the
sinkhorn algorithm in log space <a class="footnote-reference brackets" href="#id54" id="id8" role="doc-noteref"><span class="fn-bracket">[</span>2<span class="fn-bracket">]</span></a> that is more stable but can be
slower in numpy since <cite>logsumexp</cite> is not implemented in parallel.
It is the recommended solver for applications that requires
differentiability with a small number of iterations.</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="#id60" id="id9" role="doc-noteref"><span class="fn-bracket">[</span>9<span class="fn-bracket">]</span></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="#id60" id="id10" role="doc-noteref"><span class="fn-bracket">[</span>9<span class="fn-bracket">]</span></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 version of the algorithm <a class="footnote-reference brackets" href="#id73" id="id11" role="doc-noteref"><span class="fn-bracket">[</span>22<span class="fn-bracket">]</span></a>.</p></li>
<li><p><code class="code docutils literal notranslate"><span class="pre">method='screenkhorn'</span></code> calls <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.screenkhorn" title="ot.bregman.screenkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.screenkhorn</span></code></a> the
screening sinkhorn version of the algorithm <a class="footnote-reference brackets" href="#id77" id="id12" role="doc-noteref"><span class="fn-bracket">[</span>26<span class="fn-bracket">]</span></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.15.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#id27" 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#id32" 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>
<p><strong>Choosing a Sinkhorn solver</strong></p>
<p>By default and when using a regularization parameter that is not too small
the default Sinkhorn solver should be enough. If you need to use a small
regularization to get sharper OT matrices, you should use the
<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> solver that will avoid numerical
errors. This last solver can be very slow in practice and might not even
converge to a reasonable OT matrix in a finite time. This is why
<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> that relies on iterating the value
of the regularization (and using warm start) sometimes leads to better
solutions. Note that the greedy version of the Sinkhorn
<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> can also lead to a speedup and the screening
version of the Sinkhorn <a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.screenkhorn" title="ot.bregman.screenkhorn"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.screenkhorn</span></code></a> aim a providing a
fast approximation of the Sinkhorn problem. For use of GPU and gradient
computation with small number of iterations we strongly recommend the
<a class="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_log" title="ot.bregman.sinkhorn_log"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.bregman.sinkhorn_log</span></code></a> solver that will no need to check for
numerical problems.</p>
</div>
<p>Recently Genevay et al. <a class="footnote-reference brackets" href="#id74" id="id13" role="doc-noteref"><span class="fn-bracket">[</span>23<span class="fn-bracket">]</span></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 computes directly
(with no need to precompute 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="#id69" id="id14" role="doc-noteref"><span class="fn-bracket">[</span>18<span class="fn-bracket">]</span></a> <a class="footnote-reference brackets" href="#id70" id="id15" role="doc-noteref"><span class="fn-bracket">[</span>19<span class="fn-bracket">]</span></a>. Those pure Python
implementations are not optimized for speed but provide a robust implementation
of algorithms in <a class="footnote-reference brackets" href="#id69" id="id16" role="doc-noteref"><span class="fn-bracket">[</span>18<span class="fn-bracket">]</span></a> <a class="footnote-reference brackets" href="#id70" id="id17" role="doc-noteref"><span class="fn-bracket">[</span>19<span class="fn-bracket">]</span></a>.</p>
<section id="examples-of-use-for-ot-sinkhorn">
<h4>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><a class="headerlink" href="#examples-of-use-for-ot-sinkhorn" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a target shift problem with two 2D source and 1 target domain."><img alt="" src="_images/sphx_glr_plot_otda_jcpot_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_jcpot.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-jcpot-py"><span class="std std-ref">OT for multi-source target shift</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for multi-source target shift</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example is designed to show how to use the stochastic optimization algorithms for discrete and semi-continuous measures from the POT library."><img alt="" src="_images/sphx_glr_plot_stochastic_thumb.png" />
<p><a class="reference internal" href="auto_examples/others/plot_stochastic.html#sphx-glr-auto-examples-others-plot-stochastic-py"><span class="std std-ref">Stochastic examples</span></a></p>
<div class="sphx-glr-thumbnail-title">Stochastic examples</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example gives an introduction on how to use Optimal Transport in Python."><img alt="" src="_images/sphx_glr_plot_Intro_OT_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_Intro_OT.html#sphx-glr-auto-examples-plot-intro-ot-py"><span class="std std-ref">Introduction to Optimal Transport with Python</span></a></p>
<div class="sphx-glr-thumbnail-title">Introduction to Optimal Transport with Python</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of EMD and Sinkhorn transport plans and their visualization."><img alt="" src="_images/sphx_glr_plot_OT_1D_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_OT_1D.html#sphx-glr-auto-examples-plot-ot-1d-py"><span class="std std-ref">Optimal Transport for 1D distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">Optimal Transport for 1D distributions</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Illustration of 2D optimal transport between distributions that are weighted sum of Diracs. The OT matrix is plotted with the samples."><img alt="" src="_images/sphx_glr_plot_OT_2D_samples_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_OT_2D_samples.html#sphx-glr-auto-examples-plot-ot-2d-samples-py"><span class="std std-ref">Optimal Transport between 2D empirical distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">Optimal Transport between 2D empirical distributions</div>
</div></div></section>
<section id="examples-of-use-for-ot-sinkhorn2">
<h4>Examples of use for <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><a class="headerlink" href="#examples-of-use-for-ot-sinkhorn2" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="Shows how to compute multiple Wasserstein and Sinkhorn with two different ground metrics and plot their values for different distributions."><img alt="" src="_images/sphx_glr_plot_compute_emd_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_compute_emd.html#sphx-glr-auto-examples-plot-compute-emd-py"><span class="std std-ref">OT distances in 1D</span></a></p>
<div class="sphx-glr-thumbnail-title">OT distances in 1D</div>
</div></div></section>
</section>
<section id="other-regularizations">
<h3>Other regularizations<a class="headerlink" href="#other-regularizations" title="Link to this heading"></a></h3>
<p>While entropic OT is the most common and favored in practice, there exists other
kinds of regularizations. 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>
<section id="quadratic-regularization">
<h4>Quadratic regularization<a class="headerlink" href="#quadratic-regularization" title="Link to this heading"></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 an effect similar to entropic regularization by
densifying the OT matrix, yet 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="#id68" id="id18" role="doc-noteref"><span class="fn-bracket">[</span>17<span class="fn-bracket">]</span></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#id27" 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#id32" 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>
</section>
<section id="examples-of-use-of-quadratic-regularization">
<h4>Examples of use of quadratic regularization<a class="headerlink" href="#examples-of-use-of-quadratic-regularization" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of Smooth and Sparse (KL an L2 reg.) OT and sparsity-constrained OT, together with their visualizations."><img alt="" src="_images/sphx_glr_plot_OT_1D_smooth_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_OT_1D_smooth.html#sphx-glr-auto-examples-plot-ot-1d-smooth-py"><span class="std std-ref">Smooth and sparse OT example</span></a></p>
<div class="sphx-glr-thumbnail-title">Smooth and sparse OT example</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Illustrates the use of the generic solver for regularized OT with user-designed regularization term. It uses Conditional gradient as in [6] and generalized Conditional Gradient as proposed in [5,7]."><img alt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><span class="std std-ref">Regularized OT with generic solver</span></a></p>
<div class="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div></div></section>
<section id="group-lasso-regularization">
<h4>Group Lasso regularization<a class="headerlink" href="#group-lasso-regularization" title="Link to this heading"></a></h4>
<p>Another regularization that has been used in recent years <a class="footnote-reference brackets" href="#id56" id="id19" role="doc-noteref"><span class="fn-bracket">[</span>5<span class="fn-bracket">]</span></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="#id56" id="id20" role="doc-noteref"><span class="fn-bracket">[</span>5<span class="fn-bracket">]</span></a> promotes 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 sense 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="#id58" id="id21" role="doc-noteref"><span class="fn-bracket">[</span>7<span class="fn-bracket">]</span></a> in function <a class="reference internal" href="gen_modules/ot.da.html#id137" 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>
</section>
<section id="examples-of-group-lasso-regularization">
<h4>Examples of group Lasso regularization<a class="headerlink" href="#examples-of-group-lasso-regularization" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and the 4 OTDA approaches currently supported in POT."><img alt="" src="_images/sphx_glr_plot_otda_classes_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_classes.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-classes-py"><span class="std std-ref">OT for domain adaptation</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for domain adaptation</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting. It explicit the problem of domain adaptation and introduces some optimal transport approaches to solve it."><img alt="" src="_images/sphx_glr_plot_otda_d2_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_d2.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-d2-py"><span class="std std-ref">OT for domain adaptation on empirical distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for domain adaptation on empirical distributions</div>
</div></div></section>
<section id="generic-solvers">
<h4>Generic solvers<a class="headerlink" href="#generic-solvers" title="Link to this heading"></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#id0" 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="#id57" id="id22" role="doc-noteref"><span class="fn-bracket">[</span>6<span class="fn-bracket">]</span></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 quite slow in practice. However, 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="#id58" id="id23" role="doc-noteref"><span class="fn-bracket">[</span>7<span class="fn-bracket">]</span></a> implemented in <a class="reference internal" href="gen_modules/ot.optim.html#id22" 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>
</section>
<section id="examples-of-the-generic-solvers">
<h4>Examples of the generic solvers<a class="headerlink" href="#examples-of-the-generic-solvers" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="Illustrates the use of the generic solver for regularized OT with user-designed regularization term. It uses Conditional gradient as in [6] and generalized Conditional Gradient as proposed in [5,7]."><img alt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><a class="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><span class="std std-ref">Regularized OT with generic solver</span></a></p>
<div class="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div></div></section>
</section>
</section>
<section id="wasserstein-barycenters">
<h2>Wasserstein Barycenters<a class="headerlink" href="#wasserstein-barycenters" title="Link to this heading"></a></h2>
<p>A Wasserstein barycenter is a distribution that minimizes its Wasserstein
distance with respect to other distributions <a class="footnote-reference brackets" href="#id67" id="id24" role="doc-noteref"><span class="fn-bracket">[</span>16<span class="fn-bracket">]</span></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>
<section id="barycenters-with-fixed-support">
<h3>Barycenters with fixed support<a class="headerlink" href="#barycenters-with-fixed-support" title="Link to this heading"></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 <a class="reference internal" href="gen_modules/ot.lp.html#ot.lp.barycenter" title="ot.lp.barycenter"><code class="xref py py-meth docutils literal notranslate"><span class="pre">ot.lp.barycenter()</span></code></a> that relies 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.15.2)"><code class="xref any docutils literal notranslate"><span class="pre">scipy.optimize.linprog</span></code></a>, but more efficient LP solvers from
<cite>cvxopt</cite> 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 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="#id55" id="id25" role="doc-noteref"><span class="fn-bracket">[</span>3<span class="fn-bracket">]</span></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 relies 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="#id72" id="id26" role="doc-noteref"><span class="fn-bracket">[</span>21<span class="fn-bracket">]</span></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>
<section id="examples-of-wasserstein-and-regularized-wasserstein-barycenters">
<h4>Examples of Wasserstein and regularized Wasserstein barycenters<a class="headerlink" href="#examples-of-wasserstein-and-regularized-wasserstein-barycenters" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of regularized Wasserstein Barycenter as proposed in [3]."><img alt="" src="_images/sphx_glr_plot_barycenter_1D_thumb.png" />
<p><a class="reference internal" href="auto_examples/barycenters/plot_barycenter_1D.html#sphx-glr-auto-examples-barycenters-plot-barycenter-1d-py"><span class="std std-ref">1D Wasserstein barycenter demo</span></a></p>
<div class="sphx-glr-thumbnail-title">1D Wasserstein barycenter demo</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of regularized Wasserstein Barycenter as proposed in [3] and exact LP barycenters using standard LP solver."><img alt="" src="_images/sphx_glr_plot_barycenter_lp_vs_entropic_thumb.png" />
<p><a class="reference internal" href="auto_examples/barycenters/plot_barycenter_lp_vs_entropic.html#sphx-glr-auto-examples-barycenters-plot-barycenter-lp-vs-entropic-py"><span class="std std-ref">1D Wasserstein barycenter: exact LP vs entropic regularization</span></a></p>
<div class="sphx-glr-thumbnail-title">1D Wasserstein barycenter: exact LP vs entropic regularization</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of the debiased Sinkhorn barycenter as proposed in [37]_."><img alt="" src="_images/sphx_glr_plot_debiased_barycenter_thumb.png" />
<p><a class="reference internal" href="auto_examples/barycenters/plot_debiased_barycenter.html#sphx-glr-auto-examples-barycenters-plot-debiased-barycenter-py"><span class="std std-ref">Debiased Sinkhorn barycenter demo</span></a></p>
<div class="sphx-glr-thumbnail-title">Debiased Sinkhorn barycenter demo</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="When the cost is discretized (Monge), the d-MMOT solver can more quickly compute and minimize the distance between many distributions without the need for intermediate barycenter computations. This example compares the time to identify, and the quality of, solutions for the d-MMOT problem using a primal/dual algorithm and classical LP barycenter approaches."><img alt="" src="_images/sphx_glr_plot_dmmot_thumb.png" />
<p><a class="reference internal" href="auto_examples/others/plot_dmmot.html#sphx-glr-auto-examples-others-plot-dmmot-py"><span class="std std-ref">Computing d-dimensional Barycenters via d-MMOT</span></a></p>
<div class="sphx-glr-thumbnail-title">Computing d-dimensional Barycenters via d-MMOT</div>
</div></div></section>
<section id="an-example-of-convolutional-barycenter-ot-bregman-convolutional-barycenter2d-computation">
<h4>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<a class="headerlink" href="#an-example-of-convolutional-barycenter-ot-bregman-convolutional-barycenter2d-computation" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example is designed to illustrate how the Convolutional Wasserstein Barycenter function of POT works."><img alt="" src="_images/sphx_glr_plot_convolutional_barycenter_thumb.png" />
<p><a class="reference internal" href="auto_examples/barycenters/plot_convolutional_barycenter.html#sphx-glr-auto-examples-barycenters-plot-convolutional-barycenter-py"><span class="std std-ref">Convolutional Wasserstein Barycenter example</span></a></p>
<div class="sphx-glr-thumbnail-title">Convolutional Wasserstein Barycenter example</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of the debiased Sinkhorn barycenter as proposed in [37]_."><img alt="" src="_images/sphx_glr_plot_debiased_barycenter_thumb.png" />
<p><a class="reference internal" href="auto_examples/barycenters/plot_debiased_barycenter.html#sphx-glr-auto-examples-barycenters-plot-debiased-barycenter-py"><span class="std std-ref">Debiased Sinkhorn barycenter demo</span></a></p>
<div class="sphx-glr-thumbnail-title">Debiased Sinkhorn barycenter demo</div>
</div></div></section>
</section>
<section id="barycenters-with-free-support">
<h3>Barycenters with free support<a class="headerlink" href="#barycenters-with-free-support" title="Link to this heading"></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="#id71" id="id27" role="doc-noteref"><span class="fn-bracket">[</span>20<span class="fn-bracket">]</span></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>
<section id="examples-of-free-support-barycenter-estimation">
<h4>Examples of free support barycenter estimation<a class="headerlink" href="#examples-of-free-support-barycenter-estimation" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="Illustration of 2D Wasserstein and Sinkhorn barycenters if distributions are weighted sum of Diracs."><img alt="" src="_images/sphx_glr_plot_free_support_barycenter_thumb.png" />
<p><a class="reference internal" href="auto_examples/barycenters/plot_free_support_barycenter.html#sphx-glr-auto-examples-barycenters-plot-free-support-barycenter-py"><span class="std std-ref">2D free support Wasserstein barycenters of distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">2D free support Wasserstein barycenters of distributions</div>
</div></div></section>
</section>
</section>
<section id="monge-mapping-and-domain-adaptation">
<h2>Monge mapping and Domain adaptation<a class="headerlink" href="#monge-mapping-and-domain-adaptation" title="Link to this heading"></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>
<section id="monge-mapping-estimation">
<h3>Monge Mapping estimation<a class="headerlink" href="#monge-mapping-estimation" title="Link to this heading"></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="#id65" id="id28" role="doc-noteref"><span class="fn-bracket">[</span>14<span class="fn-bracket">]</span></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.gaussian.html#id39" title="ot.gaussian.bures_wasserstein_mapping"><code class="xref any py py-func docutils literal notranslate"><span class="pre">ot.gaussian.bures_wasserstein_mapping</span></code></a> that returns 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 provides 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="#id57" id="id29" role="doc-noteref"><span class="fn-bracket">[</span>6<span class="fn-bracket">]</span></a>. It is implemented in the class <a class="reference internal" href="gen_modules/ot.da.html#id53" 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 scikit-learn classes. Finally a
method proposed in <a class="footnote-reference brackets" href="#id59" id="id30" role="doc-noteref"><span class="fn-bracket">[</span>8<span class="fn-bracket">]</span></a> that estimates a continuous mapping approximating the
barycentric mapping is provided in <code class="xref any docutils literal notranslate"><span class="pre">ot.da.joint_OT_mapping_linear</span></code> for
linear mapping and <code class="xref any docutils literal notranslate"><span class="pre">ot.da.joint_OT_mapping_kernel</span></code> for non-linear mapping.</p>
</section>
<section id="domain-adaptation-classes">
<h3>Domain adaptation classes<a class="headerlink" href="#domain-adaptation-classes" title="Link to this heading"></a></h3>
<p>The use of OT for domain adaptation (OTDA) has been first proposed in <a class="footnote-reference brackets" href="#id56" id="id31" role="doc-noteref"><span class="fn-bracket">[</span>5<span class="fn-bracket">]</span></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#id0" 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 scikit-learn. At initialization, several parameters such as
regularization parameter value can be set. Then one needs to estimate the
mapping with function <a class="reference internal" href="gen_modules/ot.da.html#id38" 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#id42" 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#id40" 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#id53" 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">Xs_mapped</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#id0" 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#id53" 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#id113" 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#id98" 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="#id56" id="id32" role="doc-noteref"><span class="fn-bracket">[</span>5<span class="fn-bracket">]</span></a></p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#id106" 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="#id56" id="id33" role="doc-noteref"><span class="fn-bracket">[</span>5<span class="fn-bracket">]</span></a></p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#id76" 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="#id65" id="id34" role="doc-noteref"><span class="fn-bracket">[</span>14<span class="fn-bracket">]</span></a></p></li>
<li><p><a class="reference internal" href="gen_modules/ot.da.html#id83" 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="#id59" id="id35" role="doc-noteref"><span class="fn-bracket">[</span>8<span class="fn-bracket">]</span></a></p></li>
</ul>
</div>
<section id="examples-of-the-use-of-otda-classes">
<h4>Examples of the use of OTDA classes<a class="headerlink" href="#examples-of-the-use-of-otda-classes" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and the 4 OTDA approaches currently supported in POT."><img alt="" src="_images/sphx_glr_plot_otda_classes_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_classes.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-classes-py"><span class="std std-ref">OT for domain adaptation</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for domain adaptation</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example presents a way of transferring colors between two images with Optimal Transport as introduced in [6]"><img alt="" src="_images/sphx_glr_plot_otda_color_images_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_color_images.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-color-images-py"><span class="std std-ref">OT for image color adaptation</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for image color adaptation</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting. It explicit the problem of domain adaptation and introduces some optimal transport approaches to solve it."><img alt="" src="_images/sphx_glr_plot_otda_d2_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_d2.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-d2-py"><span class="std std-ref">OT for domain adaptation on empirical distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for domain adaptation on empirical distributions</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a target shift problem with two 2D source and 1 target domain."><img alt="" src="_images/sphx_glr_plot_otda_jcpot_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_jcpot.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-jcpot-py"><span class="std std-ref">OT for multi-source target shift</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for multi-source target shift</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and OTDA approach with Laplacian regularization."><img alt="" src="_images/sphx_glr_plot_otda_laplacian_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_laplacian.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-laplacian-py"><span class="std std-ref">OT with Laplacian regularization for domain adaptation</span></a></p>
<div class="sphx-glr-thumbnail-title">OT with Laplacian regularization for domain adaptation</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="Linear OT mapping estimation"><img alt="" src="_images/sphx_glr_plot_otda_linear_mapping_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_linear_mapping.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-linear-mapping-py"><span class="std std-ref">Linear OT mapping estimation</span></a></p>
<div class="sphx-glr-thumbnail-title">Linear OT mapping estimation</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="OT for domain adaptation with image color adaptation [6] with mapping estimation [8]."><img alt="" src="_images/sphx_glr_plot_otda_mapping_colors_images_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_mapping_colors_images.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-mapping-colors-images-py"><span class="std std-ref">OT for image color adaptation with mapping estimation</span></a></p>
<div class="sphx-glr-thumbnail-title">OT for image color adaptation with mapping estimation</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This example introduces a semi supervised domain adaptation in a 2D setting. It explicit the problem of semi supervised domain adaptation and introduces some optimal transport approaches to solve it."><img alt="" src="_images/sphx_glr_plot_otda_semi_supervised_thumb.png" />
<p><a class="reference internal" href="auto_examples/domain-adaptation/plot_otda_semi_supervised.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-semi-supervised-py"><span class="std std-ref">OTDA unsupervised vs semi-supervised setting</span></a></p>
<div class="sphx-glr-thumbnail-title">OTDA unsupervised vs semi-supervised setting</div>
</div></div></section>
</section>
</section>
<section id="unbalanced-and-partial-ot">
<h2>Unbalanced and partial OT<a class="headerlink" href="#unbalanced-and-partial-ot" title="Link to this heading"></a></h2>
<section id="unbalanced-optimal-transport">
<h3>Unbalanced optimal transport<a class="headerlink" href="#unbalanced-optimal-transport" title="Link to this heading"></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="#id76" id="id36" role="doc-noteref"><span class="fn-bracket">[</span>25<span class="fn-bracket">]</span></a> <a class="footnote-reference brackets" href="#id61" id="id37" role="doc-noteref"><span class="fn-bracket">[</span>10<span class="fn-bracket">]</span></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="#id61" id="id38" role="doc-noteref"><span class="fn-bracket">[</span>10<span class="fn-bracket">]</span></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="#id76" id="id39" role="doc-noteref"><span class="fn-bracket">[</span>25<span class="fn-bracket">]</span></a> <a class="footnote-reference brackets" href="#id61" id="id40" role="doc-noteref"><span class="fn-bracket">[</span>10<span class="fn-bracket">]</span></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="#id61" id="id41" role="doc-noteref"><span class="fn-bracket">[</span>10<span class="fn-bracket">]</span></a>.</p></li>
</ul>
</div>
<section id="examples-of-unbalanced-ot">
<h4>Examples of Unbalanced OT<a class="headerlink" href="#examples-of-unbalanced-ot" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of Unbalanced Optimal transport using a Kullback-Leibler relaxation."><img alt="" src="_images/sphx_glr_plot_UOT_1D_thumb.png" />
<p><a class="reference internal" href="auto_examples/unbalanced-partial/plot_UOT_1D.html#sphx-glr-auto-examples-unbalanced-partial-plot-uot-1d-py"><span class="std std-ref">1D Unbalanced optimal transport</span></a></p>
<div class="sphx-glr-thumbnail-title">1D Unbalanced optimal transport</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="This examples illustrates the better convergence of the translation invariance Sinkhorn algorithm proposed in [73] compared to the classical Sinkhorn algorithm."><img alt="" src="_images/sphx_glr_plot_conv_sinkhorn_ti_thumb.png" />
<p><a class="reference internal" href="auto_examples/unbalanced-partial/plot_conv_sinkhorn_ti.html#sphx-glr-auto-examples-unbalanced-partial-plot-conv-sinkhorn-ti-py"><span class="std std-ref">Translation Invariant Sinkhorn for Unbalanced Optimal Transport</span></a></p>
<div class="sphx-glr-thumbnail-title">Translation Invariant Sinkhorn for Unbalanced Optimal Transport</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="UOT aims at solving the following optimization problem:"><img alt="" src="_images/sphx_glr_plot_unbalanced_OT_thumb.png" />
<p><a class="reference internal" href="auto_examples/unbalanced-partial/plot_unbalanced_OT.html#sphx-glr-auto-examples-unbalanced-partial-plot-unbalanced-ot-py"><span class="std std-ref">2D examples of exact and entropic unbalanced optimal transport</span></a></p>
<div class="sphx-glr-thumbnail-title">2D examples of exact and entropic unbalanced optimal transport</div>
</div></div></section>
</section>
<section id="unbalanced-barycenters">
<h3>Unbalanced Barycenters<a class="headerlink" href="#unbalanced-barycenters" title="Link to this heading"></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> 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 <code class="xref py py-meth docutils literal notranslate"><span class="pre">ot.unbalanced.barycenter_unbalanced_sinkhorn_unbalanced()</span></code>
the generalized Sinkhorn algorithm <a class="footnote-reference brackets" href="#id61" id="id42" role="doc-noteref"><span class="fn-bracket">[</span>10<span class="fn-bracket">]</span></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="#id61" id="id43" role="doc-noteref"><span class="fn-bracket">[</span>10<span class="fn-bracket">]</span></a>.</p></li>
</ul>
</div>
<section id="examples-of-unbalanced-ot-barycenters">
<h4>Examples of Unbalanced OT barycenters<a class="headerlink" href="#examples-of-unbalanced-ot-barycenters" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of regularized Wasserstein Barycenter as proposed in [10] for Unbalanced inputs."><img alt="" src="_images/sphx_glr_plot_UOT_barycenter_1D_thumb.png" />
<p><a class="reference internal" href="auto_examples/unbalanced-partial/plot_UOT_barycenter_1D.html#sphx-glr-auto-examples-unbalanced-partial-plot-uot-barycenter-1d-py"><span class="std std-ref">1D Wasserstein barycenter demo for Unbalanced distributions</span></a></p>
<div class="sphx-glr-thumbnail-title">1D Wasserstein barycenter demo for Unbalanced distributions</div>
</div></div></section>
</section>
<section id="partial-optimal-transport">
<h3>Partial optimal transport<a class="headerlink" href="#partial-optimal-transport" title="Link to this heading"></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="#id78" id="id44" role="doc-noteref"><span class="fn-bracket">[</span>28<span class="fn-bracket">]</span></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="#id79" id="id45" role="doc-noteref"><span class="fn-bracket">[</span>29<span class="fn-bracket">]</span></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#id34" 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#id37" 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#id21" 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="#id55" id="id46" role="doc-noteref"><span class="fn-bracket">[</span>3<span class="fn-bracket">]</span></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#id28" 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#id0" 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>
<section id="examples-of-partial-ot">
<h4>Examples of Partial OT<a class="headerlink" href="#examples-of-partial-ot" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example is designed to show how to use the Partial (Gromov-)Wasserstein distance computation in POT [29]."><img alt="" src="_images/sphx_glr_plot_partial_wass_and_gromov_thumb.png" />
<p><a class="reference internal" href="auto_examples/unbalanced-partial/plot_partial_wass_and_gromov.html#sphx-glr-auto-examples-unbalanced-partial-plot-partial-wass-and-gromov-py"><span class="std std-ref">Partial Wasserstein and Gromov-Wasserstein example</span></a></p>
<div class="sphx-glr-thumbnail-title">Partial Wasserstein and Gromov-Wasserstein example</div>
</div><div class="sphx-glr-thumbcontainer" tooltip="UOT aims at solving the following optimization problem:"><img alt="" src="_images/sphx_glr_plot_unbalanced_OT_thumb.png" />
<p><a class="reference internal" href="auto_examples/unbalanced-partial/plot_unbalanced_OT.html#sphx-glr-auto-examples-unbalanced-partial-plot-unbalanced-ot-py"><span class="std std-ref">2D examples of exact and entropic unbalanced optimal transport</span></a></p>
<div class="sphx-glr-thumbnail-title">2D examples of exact and entropic unbalanced optimal transport</div>
</div></div></section>
</section>
</section>
<section id="gromov-wasserstein-and-extensions">
<h2>Gromov Wasserstein and extensions<a class="headerlink" href="#gromov-wasserstein-and-extensions" title="Link to this heading"></a></h2>
<section id="gromov-wasserstein-gw">
<h3>Gromov Wasserstein(GW)<a class="headerlink" href="#gromov-wasserstein-gw" title="Link to this heading"></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="#id64" id="id47" role="doc-noteref"><span class="fn-bracket">[</span>13<span class="fn-bracket">]</span></a>. In this case one cannot compute distance between samples
from the two distributions. <a class="footnote-reference brackets" href="#id64" id="id48" role="doc-noteref"><span class="fn-bracket">[</span>13<span class="fn-bracket">]</span></a> proposed instead to realign the metric spaces
by computing a transport between distance matrices. The Gromov Wasserstein
alignment 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="#id63" id="id49" role="doc-noteref"><span class="fn-bracket">[</span>12<span class="fn-bracket">]</span></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>
<section id="examples-of-computation-of-gw-regularized-g-and-fgw">
<h4>Examples of computation of GW, regularized G and FGW<a class="headerlink" href="#examples-of-computation-of-gw-regularized-g-and-fgw" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="[12] Gabriel Peyré, Marco Cuturi, and Justin Solomon (2016), "Gromov-Wasserstein averaging of kernel and distance matrices". International Conference on Machine Learning (ICML)."><img alt="" src="_images/sphx_glr_plot_gromov_thumb.png" />
<p><a class="reference internal" href="auto_examples/gromov/plot_gromov.html#sphx-glr-auto-examples-gromov-plot-gromov-py"><span class="std std-ref">Gromov-Wasserstein example</span></a></p>
<div class="sphx-glr-thumbnail-title">Gromov-Wasserstein example</div>
</div></div></section>
</section>
<section id="gromov-wasserstein-barycenters">
<h3>Gromov Wasserstein barycenters<a class="headerlink" href="#gromov-wasserstein-barycenters" title="Link to this heading"></a></h3>
<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 <a class="footnote-reference brackets" href="#id75" id="id50" role="doc-noteref"><span class="fn-bracket">[</span>24<span class="fn-bracket">]</span></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>
<section id="examples-of-gw-regularized-g-and-fgw-barycenters">
<h4>Examples of GW, regularized G and FGW barycenters<a class="headerlink" href="#examples-of-gw-regularized-g-and-fgw-barycenters" title="Link to this heading"></a></h4>
<div class="sphx-glr-thumbnails"><div class="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation barycenter of labeled graphs using FGW [18]."><img alt="" src="_images/sphx_glr_plot_barycenter_fgw_thumb.png" />
<p><a class="reference internal" href="auto_examples/gromov/plot_barycenter_fgw.html#sphx-glr-auto-examples-gromov-plot-barycenter-fgw-py"><span class="std std-ref">Plot graphs barycenter using FGW</span></a></p>
<div class="sphx-glr-thumbnail-title">Plot graphs barycenter using FGW</div>
</div></div></section>
</section>
</section>
<section id="other-applications">
<h2>Other applications<a class="headerlink" href="#other-applications" title="Link to this heading"></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>
<section id="wasserstein-discriminant-analysis">