Uh oh!
There was an error while loading. Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathquickstart.html
More file actions
Latest commit
1503 lines (1465 loc) · 153 KB
/
Copy pathquickstart.html
File metadata and controls
1503 lines (1465 loc) · 153 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>
<htmlclass="writer-html5" lang="en" data-content_root="./">
<head>
<metacharset="utf-8" /><metaname="viewport" content="width=device-width, initial-scale=1" />
<metaname="viewport" content="width=device-width, initial-scale=1.0" />
<title>Quick start guide — POT Python Optimal Transport 0.9.5 documentation</title>
<linkrel="stylesheet" type="text/css" href="_static/pygments.css?v=80d5e7a1" />
<linkrel="stylesheet" type="text/css" href="_static/css/theme.css?v=e59714d7" />
<linkrel="stylesheet" type="text/css" href="_static/sg_gallery.css?v=d2d258e8" />
<linkrel="stylesheet" type="text/css" href="_static/sg_gallery-binder.css?v=f4aeca0c" />
<linkrel="stylesheet" type="text/css" href="_static/sg_gallery-dataframe.css?v=2082cf3c" />
<linkrel="stylesheet" type="text/css" href="_static/sg_gallery-rendered-html.css?v=1277b6f3" />
<scriptsrc="_static/jquery.js?v=5d32c60e"></script>
<scriptsrc="_static/_sphinx_javascript_frameworks_compat.js?v=2cd50e6c"></script>
<scriptsrc="_static/documentation_options.js?v=61b282d3"></script>
<scriptsrc="_static/doctools.js?v=9bcbadda"></script>
<scriptsrc="_static/sphinx_highlight.js?v=dc90522c"></script>
<scriptasync="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<scriptsrc="_static/js/theme.js"></script>
<linkrel="index" title="Index" href="genindex.html" />
<linkrel="search" title="Search" href="search.html" />
<linkrel="next" title="API and modules" href="all.html" />
<linkrel="prev" title="POT: Python Optimal Transport" href="index.html" />
</head>
<bodyclass="wy-body-for-nav">
<divclass="wy-grid-for-nav">
<navdata-toggle="wy-nav-shift" class="wy-nav-side">
<divclass="wy-side-scroll">
<divclass="wy-side-nav-search" >
<ahref="index.html" class="icon icon-home">
POT Python Optimal Transport
<imgsrc="_static/logo_dark.svg" class="logo" alt="Logo"/>
</a>
<divrole="search">
<formid="rtd-search-form" class="wy-form" action="search.html" method="get">
<inputtype="text" name="q" placeholder="Search docs" aria-label="Search docs" />
<inputtype="hidden" name="check_keywords" value="yes" />
<inputtype="hidden" name="area" value="default" />
</form>
</div>
</div><divclass="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<ulclass="current">
<liclass="toctree-l1"><aclass="reference internal" href="index.html">POT: Python Optimal Transport</a></li>
<liclass="toctree-l1 current"><aclass="current reference internal" href="#">Quick start guide</a><ul>
<liclass="toctree-l2"><aclass="reference internal" href="#why-optimal-transport">Why Optimal Transport ?</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#when-to-use-ot">When to use OT</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#wasserstein-distance-between-distributions">Wasserstein distance between distributions</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#ot-for-mapping-estimation">OT for mapping estimation</a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#when-to-use-pot">When to use POT</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#when-not-to-use-pot">When not to use POT</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#optimal-transport-and-wasserstein-distance">Optimal transport and Wasserstein distance</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#solving-optimal-transport">Solving optimal transport</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-use-for-ot-emd">Examples of use for <codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.emd</span></code></a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#computing-wasserstein-distance">Computing Wasserstein distance</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-use-for-ot-emd2">Examples of use for <codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.emd2</span></code></a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#special-cases">Special cases</a></li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#regularized-optimal-transport">Regularized Optimal Transport</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#entropic-regularized-ot">Entropic regularized OT</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-use-for-ot-sinkhorn">Examples of use for <codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.sinkhorn</span></code></a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-use-for-ot-sinkhorn2">Examples of use for <codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.sinkhorn2</span></code></a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#other-regularizations">Other regularizations</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#quadratic-regularization">Quadratic regularization</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-use-of-quadratic-regularization">Examples of use of quadratic regularization</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#group-lasso-regularization">Group Lasso regularization</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-group-lasso-regularization">Examples of group Lasso regularization</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#generic-solvers">Generic solvers</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-the-generic-solvers">Examples of the generic solvers</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#wasserstein-barycenters">Wasserstein Barycenters</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#barycenters-with-fixed-support">Barycenters with fixed support</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-wasserstein-and-regularized-wasserstein-barycenters">Examples of Wasserstein and regularized Wasserstein barycenters</a></li>
<liclass="toctree-l4"><aclass="reference internal" href="#an-example-of-convolutional-barycenter-ot-bregman-convolutional-barycenter2d-computation">An example of convolutional barycenter (<codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.bregman.convolutional_barycenter2d</span></code>) computation</a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#barycenters-with-free-support">Barycenters with free support</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-free-support-barycenter-estimation">Examples of free support barycenter estimation</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#monge-mapping-and-domain-adaptation">Monge mapping and Domain adaptation</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#monge-mapping-estimation">Monge Mapping estimation</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#domain-adaptation-classes">Domain adaptation classes</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-the-use-of-otda-classes">Examples of the use of OTDA classes</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#unbalanced-and-partial-ot">Unbalanced and partial OT</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#unbalanced-optimal-transport">Unbalanced optimal transport</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-unbalanced-ot">Examples of Unbalanced OT</a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#unbalanced-barycenters">Unbalanced Barycenters</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-unbalanced-ot-barycenters">Examples of Unbalanced OT barycenters</a></li>
</ul>
</li>
<liclass="toctree-l3"><aclass="reference internal" href="#partial-optimal-transport">Partial optimal transport</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-partial-ot">Examples of Partial OT</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#gromov-wasserstein-and-extensions">Gromov Wasserstein and extensions</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#gromov-wasserstein-gw">Gromov Wasserstein(GW)</a><ul>
<liclass="toctree-l4"><aclass="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>
<liclass="toctree-l3"><aclass="reference internal" href="#gromov-wasserstein-barycenters">Gromov Wasserstein barycenters</a><ul>
<liclass="toctree-l4"><aclass="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>
<liclass="toctree-l2"><aclass="reference internal" href="#other-applications">Other applications</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#wasserstein-discriminant-analysis">Wasserstein Discriminant Analysis</a><ul>
<liclass="toctree-l4"><aclass="reference internal" href="#examples-of-the-use-of-wda">Examples of the use of WDA</a></li>
</ul>
</li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#solving-ot-with-multiple-backends-on-cpu-gpu">Solving OT with Multiple backends on CPU/GPU</a><ul>
<liclass="toctree-l3"><aclass="reference internal" href="#how-it-works">How it works</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#gpu-acceleration">GPU acceleration</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#list-of-compatible-backends">List of compatible Backends</a></li>
<liclass="toctree-l3"><aclass="reference internal" href="#list-of-compatible-modules">List of compatible modules</a></li>
</ul>
</li>
<liclass="toctree-l2"><aclass="reference internal" href="#faq">FAQ</a></li>
<liclass="toctree-l2"><aclass="reference internal" href="#references">References</a></li>
</ul>
</li>
<liclass="toctree-l1"><aclass="reference internal" href="all.html">API and modules</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="auto_examples/index.html">Examples gallery</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="releases.html">Releases</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="contributors.html">Contributors</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="contributing.html">Contributing to POT</a></li>
<liclass="toctree-l1"><aclass="reference internal" href="code_of_conduct.html">Code of conduct</a></li>
</ul>
</div>
</div>
</nav>
<sectiondata-toggle="wy-nav-shift" class="wy-nav-content-wrap"><navclass="wy-nav-top" aria-label="Mobile navigation menu" >
<idata-toggle="wy-nav-top" class="fa fa-bars"></i>
<ahref="index.html">POT Python Optimal Transport</a>
</nav>
<divclass="wy-nav-content">
<divclass="rst-content">
<divrole="navigation" aria-label="Page navigation">
<ulclass="wy-breadcrumbs">
<li><ahref="index.html" class="icon icon-home" aria-label="Home"></a></li>
<liclass="breadcrumb-item active">Quick start guide</li>
<liclass="wy-breadcrumbs-aside">
<ahref="_sources/quickstart.rst.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<divrole="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<divitemprop="articleBody">
<sectionid="quick-start-guide">
<h1>Quick start guide<aclass="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>
<divclass="admonition note">
<pclass="admonition-title">Note</p>
<p>For a good introduction to numerical optimal transport we refer the reader
to <aclass="reference external" href="https://arxiv.org/pdf/1803.00567.pdf">the book</a> by Peyré and Cuturi
<aclass="footnote-reference brackets" href="#id66" id="id1" role="doc-noteref"><spanclass="fn-bracket">[</span>15<spanclass="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 <aclass="reference external" href="https://remi.flamary.com/cours/tuto_otml.html">OTML tutorial</a>.</p>
</div>
<divclass="admonition note">
<pclass="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
<aclass="reference external" href="#solving-ot-with-multiple-backends">Backend section</a> .</p>
</div>
<sectionid="why-optimal-transport">
<h2>Why Optimal Transport ?<aclass="headerlink" href="#why-optimal-transport" title="Link to this heading"></a></h2>
<sectionid="when-to-use-ot">
<h3>When to use OT<aclass="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 <spanclass="math notranslate nohighlight">\(\mu_s\)</span> and <spanclass="math notranslate nohighlight">\(\mu_t\)</span> as</p>
<divclass="math notranslate nohighlight">
\[\min_{m, m \# \mu_s = \mu_t} \int c(x,m(x))d\mu_s(x) ,\]</div>
<p>where <spanclass="math notranslate nohighlight">\(c(\cdot,\cdot)\)</span> is the ground cost and the constraint
<spanclass="math notranslate nohighlight">\(m \# \mu_s = \mu_t\)</span> ensures that <spanclass="math notranslate nohighlight">\(\mu_s\)</span> is completely transported to <spanclass="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 <spanclass="math notranslate nohighlight">\(m\)</span> is replaced by a joint distribution
(OT matrix expressed in the next section) (see <aclass="reference internal" href="#kantorovitch-solve"><spanclass="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>
<ulclass="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>
<sectionid="wasserstein-distance-between-distributions">
<h4>Wasserstein distance between distributions<aclass="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 <aclass="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 <aclass="reference external" href="https://arxiv.org/pdf/1608.08063.pdf">discriminant</a> or
<aclass="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 <aclass="reference external" href="http://proceedings.mlr.press/v37/kusnerb15.pdf">similarity between word
embeddings of documents</a> or
between <aclass="reference external" href="https://www.math.ucdavis.edu/~saito/data/acha.read.s19/kolouri-etal_optimal-mass-transport.pdf">signals</a>
or <aclass="reference external" href="https://arxiv.org/pdf/1609.09799.pdf">spectra</a>.</p>
</section>
<sectionid="ot-for-mapping-estimation">
<h4>OT for mapping estimation<aclass="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
<aclass="reference external" href="https://arxiv.org/pdf/1307.5551.pdf">color transfer between images</a> or in
the context of <aclass="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 <aclass="reference external" href="https://arxiv.org/pdf/1809.00013.pdf">word embeddings</a>.</p>
</section>
</section>
<sectionid="when-to-use-pot">
<h3>When to use POT<aclass="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 <aclass="reference internal" href="gen_modules/ot.optim.html#id0" title="ot.optim.cg"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id80" id="id2" role="doc-noteref"><spanclass="fn-bracket">[</span>30<spanclass="fn-bracket">]</span></a>.</p>
<sectionid="when-not-to-use-pot">
<h4>When not to use POT<aclass="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 <spanclass="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 <spanclass="math notranslate nohighlight">\(\mathcal{O}(n^3\log(n))\)</span> and the Sinkhorn solver has been
proven to be nearly <spanclass="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 <aclass="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 <aclass="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
<aclass="reference external" href="https://arxiv.org/pdf/1910.04091.pdf">statistical properties</a>.</p>
</section>
</section>
</section>
<sectionid="optimal-transport-and-wasserstein-distance">
<h2>Optimal transport and Wasserstein distance<aclass="headerlink" href="#optimal-transport-and-wasserstein-distance" title="Link to this heading"></a></h2>
<divclass="admonition note">
<pclass="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 <aclass="reference internal" href="all.html#ot.emd" title="ot.emd"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd</span></code></a> returns the OT matrix and <aclass="reference internal" href="all.html#ot.emd2" title="ot.emd2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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>
<sectionid="solving-optimal-transport">
<spanid="kantorovitch-solve"></span><h3>Solving optimal transport<aclass="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>
<divclass="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><ulclass="simple">
<li><p><spanclass="math notranslate nohighlight">\(M\in\mathbb{R}_+^{m\times n}\)</span> is the metric cost matrix defining the cost to move mass from bin <spanclass="math notranslate nohighlight">\(a_i\)</span> to bin <spanclass="math notranslate nohighlight">\(b_j\)</span>.</p></li>
<li><p><spanclass="math notranslate nohighlight">\(a\)</span> and <spanclass="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 <aclass="reference internal" href="all.html#ot.emd" title="ot.emd"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd</span></code></a>
that will return the optimal transport matrix <spanclass="math notranslate nohighlight">\(\gamma^*\)</span>:</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="c1"># a and b are 1D histograms (sum to 1 and positive)</span>
<spanclass="c1"># M is the ground cost matrix</span>
<spanclass="n">T</span><spanclass="o">=</span><spanclass="n">ot</span><spanclass="o">.</span><spanclass="n">emd</span><spanclass="p">(</span><spanclass="n">a</span><spanclass="p">,</span><spanclass="n">b</span><spanclass="p">,</span><spanclass="n">M</span><spanclass="p">)</span><spanclass="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 <aclass="footnote-reference brackets" href="#id53" id="id3" role="doc-noteref"><spanclass="fn-bracket">[</span>1<spanclass="fn-bracket">]</span></a>. It has a complexity of <spanclass="math notranslate nohighlight">\(O(n^3)\)</span> but the
solver is quite efficient and uses sparsity of the solution.</p>
<sectionid="examples-of-use-for-ot-emd">
<h4>Examples of use for <aclass="reference internal" href="all.html#ot.emd" title="ot.emd"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd</span></code></a><aclass="headerlink" href="#examples-of-use-for-ot-emd" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="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]."><imgalt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><spanclass="std std-ref">Regularized OT with generic solver</span></a></p>
<divclass="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_OT_2D_samples_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_OT_2D_samples.html#sphx-glr-auto-examples-plot-ot-2d-samples-py"><spanclass="std std-ref">Optimal Transport between 2D empirical distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">Optimal Transport between 2D empirical distributions</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="2D OT on empirical distribution with different ground metric."><imgalt="" src="_images/sphx_glr_plot_OT_L1_vs_L2_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_OT_L1_vs_L2.html#sphx-glr-auto-examples-plot-ot-l1-vs-l2-py"><spanclass="std std-ref">Optimal Transport with different ground metrics</span></a></p>
<divclass="sphx-glr-thumbnail-title">Optimal Transport with different ground metrics</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example gives an introduction on how to use Optimal Transport in Python."><imgalt="" src="_images/sphx_glr_plot_Intro_OT_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_Intro_OT.html#sphx-glr-auto-examples-plot-intro-ot-py"><spanclass="std std-ref">Introduction to Optimal Transport with Python</span></a></p>
<divclass="sphx-glr-thumbnail-title">Introduction to Optimal Transport with Python</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example first illustrates the computation of FGW for 1D measures estimated using a Conditional Gradient solver [24]."><imgalt="" src="_images/sphx_glr_plot_fgw_thumb.png" />
<p><aclass="reference internal" href="auto_examples/gromov/plot_fgw.html#sphx-glr-auto-examples-gromov-plot-fgw-py"><spanclass="std std-ref">Plot Fused-Gromov-Wasserstein</span></a></p>
<divclass="sphx-glr-thumbnail-title">Plot Fused-Gromov-Wasserstein</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_WeakOT_VS_OT_thumb.png" />
<p><aclass="reference internal" href="auto_examples/others/plot_WeakOT_VS_OT.html#sphx-glr-auto-examples-others-plot-weakot-vs-ot-py"><spanclass="std std-ref">Weak Optimal Transport VS exact Optimal Transport</span></a></p>
<divclass="sphx-glr-thumbnail-title">Weak Optimal Transport VS exact Optimal Transport</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="Illustration of the factored coupling OT between 2D empirical distributions"><imgalt="" src="_images/sphx_glr_plot_factored_coupling_thumb.png" />
<p><aclass="reference internal" href="auto_examples/others/plot_factored_coupling.html#sphx-glr-auto-examples-others-plot-factored-coupling-py"><spanclass="std std-ref">Optimal transport with factored couplings</span></a></p>
<divclass="sphx-glr-thumbnail-title">Optimal transport with factored couplings</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="In this example we plot the logo of the POT toolbox."><imgalt="" src="_images/sphx_glr_plot_logo_thumb.png" />
<p><aclass="reference internal" href="auto_examples/others/plot_logo.html#sphx-glr-auto-examples-others-plot-logo-py"><spanclass="std std-ref">Logo of the POT toolbox</span></a></p>
<divclass="sphx-glr-thumbnail-title">Logo of the POT toolbox</div>
</div></div></section>
</section>
<sectionid="computing-wasserstein-distance">
<h3>Computing Wasserstein distance<aclass="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>
<divclass="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
<codeclass="code docutils literal notranslate"><spanclass="pre">np.sum(T*M)</span></code> or directly with the function <aclass="reference internal" href="all.html#ot.emd2" title="ot.emd2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd2</span></code></a>.</p>
<divclass="highlight-python notranslate"><divclass="highlight"><pre><span></span><spanclass="c1"># a and b are 1D histograms (sum to 1 and positive)</span>
<spanclass="c1"># M is the ground cost matrix</span>
<spanclass="n">W</span><spanclass="o">=</span><spanclass="n">ot</span><spanclass="o">.</span><spanclass="n">emd2</span><spanclass="p">(</span><spanclass="n">a</span><spanclass="p">,</span><spanclass="n">b</span><spanclass="p">,</span><spanclass="n">M</span><spanclass="p">)</span><spanclass="c1"># Wasserstein distance / EMD value</span>
</pre></div>
</div>
<p>Note that the well known <aclass="reference external" href="https://en.wikipedia.org/wiki/Wasserstein_metric">Wasserstein distance</a> between distributions a and
b is defined as</p>
<blockquote>
<div><divclass="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 <spanclass="math notranslate nohighlight">\(W_2\)</span> you need to compute the
square root of <aclass="reference internal" href="all.html#ot.emd2" title="ot.emd2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd2</span></code></a> when providing
<codeclass="code docutils literal notranslate"><spanclass="pre">M</span><spanclass="pre">=</span><spanclass="pre">ot.dist(xs,</span><spanclass="pre">xt)</span></code>, that uses the squared euclidean distance by default. Computing
the <spanclass="math notranslate nohighlight">\(W_1\)</span> Wasserstein distance can be done directly with <aclass="reference internal" href="all.html#ot.emd2" title="ot.emd2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd2</span></code></a>
when providing <codeclass="code docutils literal notranslate"><spanclass="pre">M</span><spanclass="pre">=</span><spanclass="pre">ot.dist(xs,</span><spanclass="pre">xt,</span><spanclass="pre">metric='euclidean')</span></code> to use the Euclidean
distance.</p>
<sectionid="examples-of-use-for-ot-emd2">
<h4>Examples of use for <aclass="reference internal" href="all.html#ot.emd2" title="ot.emd2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd2</span></code></a><aclass="headerlink" href="#examples-of-use-for-ot-emd2" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="Shows how to compute multiple Wasserstein and Sinkhorn with two different ground metrics and plot their values for different distributions."><imgalt="" src="_images/sphx_glr_plot_compute_emd_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_compute_emd.html#sphx-glr-auto-examples-plot-compute-emd-py"><spanclass="std std-ref">OT distances in 1D</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT distances in 1D</div>
</div><divclass="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:"><imgalt="" src="_images/sphx_glr_plot_unmix_optim_torch_thumb.png" />
<p><aclass="reference internal" href="auto_examples/backends/plot_unmix_optim_torch.html#sphx-glr-auto-examples-backends-plot-unmix-optim-torch-py"><spanclass="std std-ref">Wasserstein unmixing with PyTorch</span></a></p>
<divclass="sphx-glr-thumbnail-title">Wasserstein unmixing with PyTorch</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="In this example we train a Wasserstein GAN using Wasserstein 2 on minibatches as a distribution fitting term."><imgalt="" src="_images/sphx_glr_plot_wass2_gan_torch_thumb.png" />
<p><aclass="reference internal" href="auto_examples/backends/plot_wass2_gan_torch.html#sphx-glr-auto-examples-backends-plot-wass2-gan-torch-py"><spanclass="std std-ref">Wasserstein 2 Minibatch GAN with PyTorch</span></a></p>
<divclass="sphx-glr-thumbnail-title">Wasserstein 2 Minibatch GAN with PyTorch</div>
</div></div></section>
</section>
<sectionid="special-cases">
<h3>Special cases<aclass="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
<spanclass="math notranslate nohighlight">\(O(n\log(n))\)</span> by using a simple sorting. In this case we provide the
function <aclass="reference internal" href="all.html#ot.emd_1d" title="ot.emd_1d"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd_1d</span></code></a> and <aclass="reference internal" href="all.html#ot.emd2_1d" title="ot.emd2_1d"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.emd2_1d</span></code></a> to return respectively the OT
matrix and value. Note that since the solution is very sparse the <codeclass="code docutils literal notranslate"><spanclass="pre">sparse</span></code>
parameter of <aclass="reference internal" href="all.html#ot.emd_1d" title="ot.emd_1d"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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 <spanclass="math notranslate nohighlight">\(W_p\)</span>
Wasserstein distance in 1D we provide the function <aclass="reference internal" href="all.html#ot.wasserstein_1d" title="ot.wasserstein_1d"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.wasserstein_1d</span></code></a> that
takes <codeclass="code docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id66" id="id4" role="doc-noteref"><spanclass="fn-bracket">[</span>15<spanclass="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 <aclass="reference internal" href="gen_modules/ot.gaussian.html#id21" title="ot.gaussian.bures_wasserstein_mapping"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gaussian.bures_wasserstein_mapping</span></code></a> that returns the parameters for the
Monge mapping.</p>
</section>
</section>
<sectionid="regularized-optimal-transport">
<h2>Regularized Optimal Transport<aclass="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>
<divclass="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>
<ulclass="simple">
<li><p><spanclass="math notranslate nohighlight">\(M\in\mathbb{R}_+^{m\times n}\)</span> is the metric cost matrix defining the cost to move mass from bin <spanclass="math notranslate nohighlight">\(a_i\)</span> to bin <spanclass="math notranslate nohighlight">\(b_j\)</span>.</p></li>
<li><p><spanclass="math notranslate nohighlight">\(a\)</span> and <spanclass="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><spanclass="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>
<sectionid="entropic-regularized-ot">
<h3>Entropic regularized OT<aclass="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 <aclass="footnote-reference brackets" href="#id54" id="id5" role="doc-noteref"><spanclass="fn-bracket">[</span>2<spanclass="fn-bracket">]</span></a>. This
regularization has the following expression</p>
<divclass="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 <aclass="footnote-reference brackets" href="#id54" id="id6" role="doc-noteref"><spanclass="fn-bracket">[</span>2<spanclass="fn-bracket">]</span></a> or L-BFGS (see
<aclass="reference internal" href="gen_modules/ot.smooth.html#module-ot.smooth" title="ot.smooth"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="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>
<divclass="math notranslate nohighlight">
\[\gamma_\lambda^*=\text{diag}(u)K\text{diag}(v)\]</div>
<p>where <spanclass="math notranslate nohighlight">\(u\)</span> and <spanclass="math notranslate nohighlight">\(v\)</span> are vectors and <spanclass="math notranslate nohighlight">\(K=\exp(-M/\lambda)\)</span> where
the <spanclass="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 <aclass="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn</span></code></a> and
<aclass="reference internal" href="all.html#ot.sinkhorn2" title="ot.sinkhorn2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn2</span></code></a> that return respectively the OT matrix and the value of the
linear term. Note that the regularization parameter <spanclass="math notranslate nohighlight">\(\lambda\)</span> in the
equation above is given to those functions with the parameter <codeclass="code docutils literal notranslate"><spanclass="pre">reg</span></code>.</p>
<divclass="doctest highlight-default notranslate"><divclass="highlight"><pre><span></span><spanclass="gp">>>> </span><spanclass="kn">import</span><spanclass="nn">ot</span>
<spanclass="gp">>>> </span><spanclass="n">a</span><spanclass="o">=</span><spanclass="p">[</span><spanclass="mf">.5</span><spanclass="p">,</span><spanclass="mf">.5</span><spanclass="p">]</span>
<spanclass="gp">>>> </span><spanclass="n">b</span><spanclass="o">=</span><spanclass="p">[</span><spanclass="mf">.5</span><spanclass="p">,</span><spanclass="mf">.5</span><spanclass="p">]</span>
<spanclass="gp">>>> </span><spanclass="n">M</span><spanclass="o">=</span><spanclass="p">[[</span><spanclass="mf">0.</span><spanclass="p">,</span><spanclass="mf">1.</span><spanclass="p">],</span><spanclass="p">[</span><spanclass="mf">1.</span><spanclass="p">,</span><spanclass="mf">0.</span><spanclass="p">]]</span>
<spanclass="gp">>>> </span><spanclass="n">ot</span><spanclass="o">.</span><spanclass="n">sinkhorn</span><spanclass="p">(</span><spanclass="n">a</span><spanclass="p">,</span><spanclass="n">b</span><spanclass="p">,</span><spanclass="n">M</span><spanclass="p">,</span><spanclass="mi">1</span><spanclass="p">)</span>
<spanclass="go">array([[ 0.36552929, 0.13447071],</span>
<spanclass="go"> [ 0.13447071, 0.36552929]])</span>
</pre></div>
</div>
<p>More details about the algorithms used are given in the following note.</p>
<divclass="admonition note">
<pclass="admonition-title">Note</p>
<p>The main function to solve entropic regularized OT is <aclass="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn</span></code></a>.
This function is a wrapper and the parameter <codeclass="code docutils literal notranslate"><spanclass="pre">method</span></code> allows you to select
the actual algorithm used to solve the problem:</p>
<ulclass="simple">
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn'</span></code> calls <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_knopp" title="ot.bregman.sinkhorn_knopp"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.sinkhorn_knopp</span></code></a> the
classic algorithm <aclass="footnote-reference brackets" href="#id54" id="id7" role="doc-noteref"><spanclass="fn-bracket">[</span>2<spanclass="fn-bracket">]</span></a>.</p></li>
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn_log'</span></code> calls <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_log" title="ot.bregman.sinkhorn_log"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.sinkhorn_log</span></code></a> the
sinkhorn algorithm in log space <aclass="footnote-reference brackets" href="#id54" id="id8" role="doc-noteref"><spanclass="fn-bracket">[</span>2<spanclass="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><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn_stabilized'</span></code> calls <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_stabilized" title="ot.bregman.sinkhorn_stabilized"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.sinkhorn_stabilized</span></code></a> the
log stabilized version of the algorithm <aclass="footnote-reference brackets" href="#id60" id="id9" role="doc-noteref"><spanclass="fn-bracket">[</span>9<spanclass="fn-bracket">]</span></a>.</p></li>
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn_epsilon_scaling'</span></code> calls
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_epsilon_scaling" title="ot.bregman.sinkhorn_epsilon_scaling"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.sinkhorn_epsilon_scaling</span></code></a> the epsilon scaling version
of the algorithm <aclass="footnote-reference brackets" href="#id60" id="id10" role="doc-noteref"><spanclass="fn-bracket">[</span>9<spanclass="fn-bracket">]</span></a>.</p></li>
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='greenkhorn'</span></code> calls <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.greenkhorn" title="ot.bregman.greenkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.greenkhorn</span></code></a> the
greedy Sinkhorn version of the algorithm <aclass="footnote-reference brackets" href="#id73" id="id11" role="doc-noteref"><spanclass="fn-bracket">[</span>22<spanclass="fn-bracket">]</span></a>.</p></li>
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='screenkhorn'</span></code> calls <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.screenkhorn" title="ot.bregman.screenkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.screenkhorn</span></code></a> the
screening sinkhorn version of the algorithm <aclass="footnote-reference brackets" href="#id77" id="id12" role="doc-noteref"><spanclass="fn-bracket">[</span>26<spanclass="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
<aclass="reference internal" href="gen_modules/ot.smooth.html#module-ot.smooth" title="ot.smooth"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="pre">ot.smooth</span></code></a>. This solver uses the <aclass="reference external" href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html#scipy.optimize.minimize" title="(in SciPy v1.14.1)"><codeclass="xref any docutils literal notranslate"><spanclass="pre">scipy.optimize.minimize</span></code></a>
function to solve the smooth problem with <codeclass="code docutils literal notranslate"><spanclass="pre">L-BFGS-B</span></code> algorithm. Tu use
this solver, use functions <aclass="reference internal" href="gen_modules/ot.smooth.html#id27" title="ot.smooth.smooth_ot_dual"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.smooth.smooth_ot_dual</span></code></a> or
<aclass="reference internal" href="gen_modules/ot.smooth.html#id32" title="ot.smooth.smooth_ot_semi_dual"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.smooth.smooth_ot_semi_dual</span></code></a> with parameter <codeclass="code docutils literal notranslate"><spanclass="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
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_stabilized" title="ot.bregman.sinkhorn_stabilized"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_epsilon_scaling" title="ot.bregman.sinkhorn_epsilon_scaling"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.greenkhorn" title="ot.bregman.greenkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.greenkhorn</span></code></a> can also lead to a speedup and the screening
version of the Sinkhorn <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.screenkhorn" title="ot.bregman.screenkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.sinkhorn_log" title="ot.bregman.sinkhorn_log"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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. <aclass="footnote-reference brackets" href="#id74" id="id13" role="doc-noteref"><spanclass="fn-bracket">[</span>23<spanclass="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 <codeclass="code docutils literal notranslate"><spanclass="pre">M</span></code> matrix)
the Sinkhorn divergence for empirical distributions in
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.empirical_sinkhorn_divergence" title="ot.bregman.empirical_sinkhorn_divergence"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.empirical_sinkhorn_divergence</span></code></a>. Similarly one can compute the
OT matrix and loss for empirical distributions with respectively
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.empirical_sinkhorn" title="ot.bregman.empirical_sinkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.empirical_sinkhorn</span></code></a> and <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.empirical_sinkhorn2" title="ot.bregman.empirical_sinkhorn2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.empirical_sinkhorn2</span></code></a>.</p>
<p>Finally note that we also provide in <aclass="reference internal" href="gen_modules/ot.stochastic.html#module-ot.stochastic" title="ot.stochastic"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="pre">ot.stochastic</span></code></a> several implementation
of stochastic solvers for entropic regularized OT <aclass="footnote-reference brackets" href="#id69" id="id14" role="doc-noteref"><spanclass="fn-bracket">[</span>18<spanclass="fn-bracket">]</span></a><aclass="footnote-reference brackets" href="#id70" id="id15" role="doc-noteref"><spanclass="fn-bracket">[</span>19<spanclass="fn-bracket">]</span></a>. Those pure Python
implementations are not optimized for speed but provide a robust implementation
of algorithms in <aclass="footnote-reference brackets" href="#id69" id="id16" role="doc-noteref"><spanclass="fn-bracket">[</span>18<spanclass="fn-bracket">]</span></a><aclass="footnote-reference brackets" href="#id70" id="id17" role="doc-noteref"><spanclass="fn-bracket">[</span>19<spanclass="fn-bracket">]</span></a>.</p>
<sectionid="examples-of-use-for-ot-sinkhorn">
<h4>Examples of use for <aclass="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn</span></code></a><aclass="headerlink" href="#examples-of-use-for-ot-sinkhorn" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of EMD and Sinkhorn transport plans and their visualization."><imgalt="" src="_images/sphx_glr_plot_OT_1D_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_OT_1D.html#sphx-glr-auto-examples-plot-ot-1d-py"><spanclass="std std-ref">Optimal Transport for 1D distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">Optimal Transport for 1D distributions</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_OT_2D_samples_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_OT_2D_samples.html#sphx-glr-auto-examples-plot-ot-2d-samples-py"><spanclass="std std-ref">Optimal Transport between 2D empirical distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">Optimal Transport between 2D empirical distributions</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example gives an introduction on how to use Optimal Transport in Python."><imgalt="" src="_images/sphx_glr_plot_Intro_OT_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_Intro_OT.html#sphx-glr-auto-examples-plot-intro-ot-py"><spanclass="std std-ref">Introduction to Optimal Transport with Python</span></a></p>
<divclass="sphx-glr-thumbnail-title">Introduction to Optimal Transport with Python</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example introduces a target shift problem with two 2D source and 1 target domain."><imgalt="" src="_images/sphx_glr_plot_otda_jcpot_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_jcpot.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-jcpot-py"><spanclass="std std-ref">OT for multi-source target shift</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for multi-source target shift</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_stochastic_thumb.png" />
<p><aclass="reference internal" href="auto_examples/others/plot_stochastic.html#sphx-glr-auto-examples-others-plot-stochastic-py"><spanclass="std std-ref">Stochastic examples</span></a></p>
<divclass="sphx-glr-thumbnail-title">Stochastic examples</div>
</div></div></section>
<sectionid="examples-of-use-for-ot-sinkhorn2">
<h4>Examples of use for <aclass="reference internal" href="all.html#ot.sinkhorn2" title="ot.sinkhorn2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn2</span></code></a><aclass="headerlink" href="#examples-of-use-for-ot-sinkhorn2" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="Shows how to compute multiple Wasserstein and Sinkhorn with two different ground metrics and plot their values for different distributions."><imgalt="" src="_images/sphx_glr_plot_compute_emd_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_compute_emd.html#sphx-glr-auto-examples-plot-compute-emd-py"><spanclass="std std-ref">OT distances in 1D</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT distances in 1D</div>
</div></div></section>
</section>
<sectionid="other-regularizations">
<h3>Other regularizations<aclass="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 <aclass="reference internal" href="gen_modules/ot.optim.html#module-ot.optim" title="ot.optim"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="pre">ot.optim</span></code></a> two generic solvers
that allows solving any smooth regularization in practice.</p>
<sectionid="quadratic-regularization">
<h4>Quadratic regularization<aclass="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>
<divclass="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 <spanclass="math notranslate nohighlight">\(\lambda>0\)</span><aclass="footnote-reference brackets" href="#id68" id="id18" role="doc-noteref"><spanclass="fn-bracket">[</span>17<spanclass="fn-bracket">]</span></a>. This problem can be
solved with POT using solvers from <aclass="reference internal" href="gen_modules/ot.smooth.html#module-ot.smooth" title="ot.smooth"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="pre">ot.smooth</span></code></a>, more specifically
functions <aclass="reference internal" href="gen_modules/ot.smooth.html#id27" title="ot.smooth.smooth_ot_dual"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.smooth.smooth_ot_dual</span></code></a> or
<aclass="reference internal" href="gen_modules/ot.smooth.html#id32" title="ot.smooth.smooth_ot_semi_dual"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.smooth.smooth_ot_semi_dual</span></code></a> with parameter <codeclass="code docutils literal notranslate"><spanclass="pre">reg_type='l2'</span></code> to
choose the quadratic regularization.</p>
</section>
<sectionid="examples-of-use-of-quadratic-regularization">
<h4>Examples of use of quadratic regularization<aclass="headerlink" href="#examples-of-use-of-quadratic-regularization" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="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]."><imgalt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><spanclass="std std-ref">Regularized OT with generic solver</span></a></p>
<divclass="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_OT_1D_smooth_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_OT_1D_smooth.html#sphx-glr-auto-examples-plot-ot-1d-smooth-py"><spanclass="std std-ref">Smooth and sparse OT example</span></a></p>
<divclass="sphx-glr-thumbnail-title">Smooth and sparse OT example</div>
</div></div></section>
<sectionid="group-lasso-regularization">
<h4>Group Lasso regularization<aclass="headerlink" href="#group-lasso-regularization" title="Link to this heading"></a></h4>
<p>Another regularization that has been used in recent years <aclass="footnote-reference brackets" href="#id56" id="id19" role="doc-noteref"><spanclass="fn-bracket">[</span>5<spanclass="fn-bracket">]</span></a> is the group Lasso
regularization</p>
<divclass="math notranslate nohighlight">
\[\Omega(\gamma)=\sum_{j,G\in\mathcal{G}} \|\gamma_{G,j}\|_q^p\]</div>
<p>where <spanclass="math notranslate nohighlight">\(\mathcal{G}\)</span> contains non-overlapping groups of lines in the OT
matrix. This regularization proposed in <aclass="footnote-reference brackets" href="#id56" id="id20" role="doc-noteref"><spanclass="fn-bracket">[</span>5<spanclass="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 <codeclass="code docutils literal notranslate"><spanclass="pre">p</span></code> and <codeclass="code docutils literal notranslate"><spanclass="pre">q</span></code>, the problem can be solved with different
approaches. When <codeclass="code docutils literal notranslate"><spanclass="pre">q=1</span></code> and <codeclass="code docutils literal notranslate"><spanclass="pre">p<1</span></code> the problem is non-convex but can
be solved using an efficient majoration minimization approach with
<aclass="reference internal" href="all.html#ot.sinkhorn_lpl1_mm" title="ot.sinkhorn_lpl1_mm"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn_lpl1_mm</span></code></a>. When <codeclass="code docutils literal notranslate"><spanclass="pre">q=2</span></code> and <codeclass="code docutils literal notranslate"><spanclass="pre">p=1</span></code> we recover the
convex group lasso and we provide a solver using generalized conditional
gradient algorithm <aclass="footnote-reference brackets" href="#id58" id="id21" role="doc-noteref"><spanclass="fn-bracket">[</span>7<spanclass="fn-bracket">]</span></a> in function <aclass="reference internal" href="gen_modules/ot.da.html#id137" title="ot.da.sinkhorn_l1l2_gl"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.da.sinkhorn_l1l2_gl</span></code></a>.</p>
</section>
<sectionid="examples-of-group-lasso-regularization">
<h4>Examples of group Lasso regularization<aclass="headerlink" href="#examples-of-group-lasso-regularization" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and the 4 OTDA approaches currently supported in POT."><imgalt="" src="_images/sphx_glr_plot_otda_classes_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_classes.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-classes-py"><spanclass="std std-ref">OT for domain adaptation</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for domain adaptation</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and the 4 OTDA approaches currently supported in POT."><imgalt="" src="_images/sphx_glr_plot_otda_classes_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_classes.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-classes-py"><spanclass="std std-ref">OT for domain adaptation</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for domain adaptation</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_otda_d2_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_d2.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-d2-py"><spanclass="std std-ref">OT for domain adaptation on empirical distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for domain adaptation on empirical distributions</div>
</div></div></section>
<sectionid="generic-solvers">
<h4>Generic solvers<aclass="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>
<divclass="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 <aclass="reference internal" href="gen_modules/ot.optim.html#id0" title="ot.optim.cg"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.optim.cg</span></code></a> that will use a conditional gradient as
proposed in <aclass="footnote-reference brackets" href="#id57" id="id22" role="doc-noteref"><spanclass="fn-bracket">[</span>6<spanclass="fn-bracket">]</span></a> . You need to provide the regularization function as parameter
<codeclass="docutils literal notranslate"><spanclass="pre">f</span></code> and its gradient as parameter <codeclass="docutils literal notranslate"><spanclass="pre">df</span></code>. Note that the conditional gradient relies on
iterative solving of a linearization of the problem using the exact
<aclass="reference internal" href="all.html#ot.emd" title="ot.emd"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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>
<divclass="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 <spanclass="math notranslate nohighlight">\(\Omega_e\)</span> is the entropic regularization. In this case we use a
generalized conditional gradient <aclass="footnote-reference brackets" href="#id58" id="id23" role="doc-noteref"><spanclass="fn-bracket">[</span>7<spanclass="fn-bracket">]</span></a> implemented in <aclass="reference internal" href="gen_modules/ot.optim.html#id22" title="ot.optim.gcg"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.optim.gcg</span></code></a> that
does not linearize the entropic term but
relies on <aclass="reference internal" href="all.html#ot.sinkhorn" title="ot.sinkhorn"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn</span></code></a> for its iterations.</p>
</section>
<sectionid="examples-of-the-generic-solvers">
<h4>Examples of the generic solvers<aclass="headerlink" href="#examples-of-the-generic-solvers" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="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]."><imgalt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><spanclass="std std-ref">Regularized OT with generic solver</span></a></p>
<divclass="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div><divclass="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]."><imgalt="" src="_images/sphx_glr_plot_optim_OTreg_thumb.png" />
<p><aclass="reference internal" href="auto_examples/plot_optim_OTreg.html#sphx-glr-auto-examples-plot-optim-otreg-py"><spanclass="std std-ref">Regularized OT with generic solver</span></a></p>
<divclass="sphx-glr-thumbnail-title">Regularized OT with generic solver</div>
</div></div></section>
</section>
</section>
<sectionid="wasserstein-barycenters">
<h2>Wasserstein Barycenters<aclass="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 <aclass="footnote-reference brackets" href="#id67" id="id24" role="doc-noteref"><spanclass="fn-bracket">[</span>16<spanclass="fn-bracket">]</span></a>. It corresponds to minimizing the
following problem by searching a distribution <spanclass="math notranslate nohighlight">\(\mu\)</span> such that</p>
<divclass="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>
<divclass="math notranslate nohighlight">
\[\mu=\sum_{i=1}^n a_i\delta_{x_i}\]</div>
<p>where <spanclass="math notranslate nohighlight">\(a\)</span> is an histogram on the simplex and the <spanclass="math notranslate nohighlight">\(\{x_i\}\)</span> are the
position of the support. We can clearly see here that optimizing <spanclass="math notranslate nohighlight">\(\mu\)</span> can
be done by searching for optimal weights <spanclass="math notranslate nohighlight">\(a\)</span> or optimal support
<spanclass="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>
<sectionid="barycenters-with-fixed-support">
<h3>Barycenters with fixed support<aclass="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>
<divclass="math notranslate nohighlight">
\[\min_a \quad \sum_{k} w_k W(a,b_k)\]</div>
<p>where <spanclass="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 <aclass="reference internal" href="gen_modules/ot.lp.html#ot.lp.barycenter" title="ot.lp.barycenter"><codeclass="xref py py-meth docutils literal notranslate"><spanclass="pre">ot.lp.barycenter()</span></code></a> that relies on generic LP solvers. By default the
function uses <aclass="reference external" href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html#scipy.optimize.linprog" title="(in SciPy v1.14.1)"><codeclass="xref any docutils literal notranslate"><spanclass="pre">scipy.optimize.linprog</span></code></a>, but more efficient LP solvers from
<cite>cvxopt</cite> can be also used by changing parameter <codeclass="code docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id55" id="id25" role="doc-noteref"><spanclass="fn-bracket">[</span>3<spanclass="fn-bracket">]</span></a>. This
algorithm is provided in function <aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.barycenter" title="ot.bregman.barycenter"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.barycenter</span></code></a> also available as
<aclass="reference internal" href="all.html#ot.barycenter" title="ot.barycenter"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id72" id="id26" role="doc-noteref"><spanclass="fn-bracket">[</span>21<spanclass="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
<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.convolutional_barycenter2d" title="ot.bregman.convolutional_barycenter2d"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.convolutional_barycenter2d</span></code></a>.</p>
<sectionid="examples-of-wasserstein-and-regularized-wasserstein-barycenters">
<h4>Examples of Wasserstein and regularized Wasserstein barycenters<aclass="headerlink" href="#examples-of-wasserstein-and-regularized-wasserstein-barycenters" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of regularized Wasserstein Barycenter as proposed in [3]."><imgalt="" src="_images/sphx_glr_plot_barycenter_1D_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_barycenter_1D.html#sphx-glr-auto-examples-barycenters-plot-barycenter-1d-py"><spanclass="std std-ref">1D Wasserstein barycenter demo</span></a></p>
<divclass="sphx-glr-thumbnail-title">1D Wasserstein barycenter demo</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of the debiased Sinkhorn barycenter as proposed in [37]_."><imgalt="" src="_images/sphx_glr_plot_debiased_barycenter_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_debiased_barycenter.html#sphx-glr-auto-examples-barycenters-plot-debiased-barycenter-py"><spanclass="std std-ref">Debiased Sinkhorn barycenter demo</span></a></p>
<divclass="sphx-glr-thumbnail-title">Debiased Sinkhorn barycenter demo</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_barycenter_lp_vs_entropic_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_barycenter_lp_vs_entropic.html#sphx-glr-auto-examples-barycenters-plot-barycenter-lp-vs-entropic-py"><spanclass="std std-ref">1D Wasserstein barycenter: exact LP vs entropic regularization</span></a></p>
<divclass="sphx-glr-thumbnail-title">1D Wasserstein barycenter: exact LP vs entropic regularization</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_barycenter_lp_vs_entropic_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_barycenter_lp_vs_entropic.html#sphx-glr-auto-examples-barycenters-plot-barycenter-lp-vs-entropic-py"><spanclass="std std-ref">1D Wasserstein barycenter: exact LP vs entropic regularization</span></a></p>
<divclass="sphx-glr-thumbnail-title">1D Wasserstein barycenter: exact LP vs entropic regularization</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_dmmot_thumb.png" />
<p><aclass="reference internal" href="auto_examples/others/plot_dmmot.html#sphx-glr-auto-examples-others-plot-dmmot-py"><spanclass="std std-ref">Computing d-dimensional Barycenters via d-MMOT</span></a></p>
<divclass="sphx-glr-thumbnail-title">Computing d-dimensional Barycenters via d-MMOT</div>
</div></div></section>
<sectionid="an-example-of-convolutional-barycenter-ot-bregman-convolutional-barycenter2d-computation">
<h4>An example of convolutional barycenter (<aclass="reference internal" href="gen_modules/ot.bregman.html#ot.bregman.convolutional_barycenter2d" title="ot.bregman.convolutional_barycenter2d"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.bregman.convolutional_barycenter2d</span></code></a>) computation<aclass="headerlink" href="#an-example-of-convolutional-barycenter-ot-bregman-convolutional-barycenter2d-computation" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example is designed to illustrate how the Convolutional Wasserstein Barycenter function of POT works."><imgalt="" src="_images/sphx_glr_plot_convolutional_barycenter_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_convolutional_barycenter.html#sphx-glr-auto-examples-barycenters-plot-convolutional-barycenter-py"><spanclass="std std-ref">Convolutional Wasserstein Barycenter example</span></a></p>
<divclass="sphx-glr-thumbnail-title">Convolutional Wasserstein Barycenter example</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of the debiased Sinkhorn barycenter as proposed in [37]_."><imgalt="" src="_images/sphx_glr_plot_debiased_barycenter_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_debiased_barycenter.html#sphx-glr-auto-examples-barycenters-plot-debiased-barycenter-py"><spanclass="std std-ref">Debiased Sinkhorn barycenter demo</span></a></p>
<divclass="sphx-glr-thumbnail-title">Debiased Sinkhorn barycenter demo</div>
</div></div></section>
</section>
<sectionid="barycenters-with-free-support">
<h3>Barycenters with free support<aclass="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>
<divclass="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 <aclass="footnote-reference brackets" href="#id71" id="id27" role="doc-noteref"><spanclass="fn-bracket">[</span>20<spanclass="fn-bracket">]</span></a> in
<aclass="reference internal" href="gen_modules/ot.lp.html#id24" title="ot.lp.free_support_barycenter"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.lp.free_support_barycenter</span></code></a>. This function minimize the problem and
return a locally optimal support <spanclass="math notranslate nohighlight">\(\{x_i\}\)</span> for uniform or given weights
<spanclass="math notranslate nohighlight">\(a\)</span>.</p>
<sectionid="examples-of-free-support-barycenter-estimation">
<h4>Examples of free support barycenter estimation<aclass="headerlink" href="#examples-of-free-support-barycenter-estimation" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="Illustration of 2D Wasserstein and Sinkhorn barycenters if distributions are weighted sum of Diracs."><imgalt="" src="_images/sphx_glr_plot_free_support_barycenter_thumb.png" />
<p><aclass="reference internal" href="auto_examples/barycenters/plot_free_support_barycenter.html#sphx-glr-auto-examples-barycenters-plot-free-support-barycenter-py"><spanclass="std std-ref">2D free support Wasserstein barycenters of distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">2D free support Wasserstein barycenters of distributions</div>
</div></div></section>
</section>
</section>
<sectionid="monge-mapping-and-domain-adaptation">
<h2>Monge mapping and Domain adaptation<aclass="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 <aclass="reference external" href="https://who.rocq.inria.fr/Jean-David.Benamou/demiheure.pdf">theorem</a>. We provide in
<aclass="reference internal" href="gen_modules/ot.da.html#module-ot.da" title="ot.da"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="pre">ot.da</span></code></a> several solvers for smooth Monge mapping estimation and domain
adaptation from discrete distributions.</p>
<sectionid="monge-mapping-estimation">
<h3>Monge Mapping estimation<aclass="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 <aclass="footnote-reference brackets" href="#id65" id="id28" role="doc-noteref"><spanclass="fn-bracket">[</span>14<spanclass="fn-bracket">]</span></a> of the form <spanclass="math notranslate nohighlight">\(T(x)=Ax+b\)</span> . In this case we provide the function
<aclass="reference internal" href="gen_modules/ot.gaussian.html#id21" title="ot.gaussian.bures_wasserstein_mapping"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gaussian.bures_wasserstein_mapping</span></code></a> that returns the operator <spanclass="math notranslate nohighlight">\(A\)</span> and vector
<spanclass="math notranslate nohighlight">\(b\)</span>. Note that if the number of samples is too small there is a parameter
<codeclass="code docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id57" id="id29" role="doc-noteref"><spanclass="fn-bracket">[</span>6<spanclass="fn-bracket">]</span></a>. It is implemented in the class <aclass="reference internal" href="gen_modules/ot.da.html#id53" title="ot.da.EMDTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.EMDTransport</span></code></a> and
other transport-based classes in <aclass="reference internal" href="gen_modules/ot.da.html#module-ot.da" title="ot.da"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id59" id="id30" role="doc-noteref"><spanclass="fn-bracket">[</span>8<spanclass="fn-bracket">]</span></a> that estimates a continuous mapping approximating the
barycentric mapping is provided in <codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.da.joint_OT_mapping_linear</span></code> for
linear mapping and <codeclass="xref any docutils literal notranslate"><spanclass="pre">ot.da.joint_OT_mapping_kernel</span></code> for non-linear mapping.</p>
</section>
<sectionid="domain-adaptation-classes">
<h3>Domain adaptation classes<aclass="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 <aclass="footnote-reference brackets" href="#id56" id="id31" role="doc-noteref"><spanclass="fn-bracket">[</span>5<spanclass="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 <aclass="reference internal" href="gen_modules/ot.da.html#id0" title="ot.da.BaseTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="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 <aclass="reference internal" href="gen_modules/ot.da.html#id38" title="ot.da.BaseTransport.fit"><codeclass="xref any py py-meth docutils literal notranslate"><spanclass="pre">ot.da.BaseTransport.fit</span></code></a>. Finally one can map the
samples from source to target with <aclass="reference internal" href="gen_modules/ot.da.html#id42" title="ot.da.BaseTransport.transform"><codeclass="xref any py py-meth docutils literal notranslate"><spanclass="pre">ot.da.BaseTransport.transform</span></code></a> and
from target to source with <aclass="reference internal" href="gen_modules/ot.da.html#id40" title="ot.da.BaseTransport.inverse_transform"><codeclass="xref any py py-meth docutils literal notranslate"><spanclass="pre">ot.da.BaseTransport.inverse_transform</span></code></a>.</p>
<p>Here is an example for class <aclass="reference internal" href="gen_modules/ot.da.html#id53" title="ot.da.EMDTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.EMDTransport</span></code></a>:</p>
<divclass="highlight-default notranslate"><divclass="highlight"><pre><span></span><spanclass="n">ot_emd</span><spanclass="o">=</span><spanclass="n">ot</span><spanclass="o">.</span><spanclass="n">da</span><spanclass="o">.</span><spanclass="n">EMDTransport</span><spanclass="p">()</span>
<spanclass="n">ot_emd</span><spanclass="o">.</span><spanclass="n">fit</span><spanclass="p">(</span><spanclass="n">Xs</span><spanclass="o">=</span><spanclass="n">Xs</span><spanclass="p">,</span><spanclass="n">Xt</span><spanclass="o">=</span><spanclass="n">Xt</span><spanclass="p">)</span>
<spanclass="n">Xs_mapped</span><spanclass="o">=</span><spanclass="n">ot_emd</span><spanclass="o">.</span><spanclass="n">transform</span><spanclass="p">(</span><spanclass="n">Xs</span><spanclass="o">=</span><spanclass="n">Xs</span><spanclass="p">)</span>
</pre></div>
</div>
<p>A list of the provided implementation is given in the following note.</p>
<divclass="admonition note">
<pclass="admonition-title">Note</p>
<p>Here is a list of the OT mapping classes inheriting from
<aclass="reference internal" href="gen_modules/ot.da.html#id0" title="ot.da.BaseTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.BaseTransport</span></code></a></p>
<ulclass="simple">
<li><p><aclass="reference internal" href="gen_modules/ot.da.html#id53" title="ot.da.EMDTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.EMDTransport</span></code></a>: Barycentric mapping with EMD transport</p></li>
<li><p><aclass="reference internal" href="gen_modules/ot.da.html#id113" title="ot.da.SinkhornTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.SinkhornTransport</span></code></a>: Barycentric mapping with Sinkhorn transport</p></li>
<li><p><aclass="reference internal" href="gen_modules/ot.da.html#id98" title="ot.da.SinkhornL1l2Transport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.SinkhornL1l2Transport</span></code></a>: Barycentric mapping with Sinkhorn +
group Lasso regularization <aclass="footnote-reference brackets" href="#id56" id="id32" role="doc-noteref"><spanclass="fn-bracket">[</span>5<spanclass="fn-bracket">]</span></a></p></li>
<li><p><aclass="reference internal" href="gen_modules/ot.da.html#id106" title="ot.da.SinkhornLpl1Transport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.SinkhornLpl1Transport</span></code></a>: Barycentric mapping with Sinkhorn +
non convex group Lasso regularization <aclass="footnote-reference brackets" href="#id56" id="id33" role="doc-noteref"><spanclass="fn-bracket">[</span>5<spanclass="fn-bracket">]</span></a></p></li>
<li><p><aclass="reference internal" href="gen_modules/ot.da.html#id76" title="ot.da.LinearTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.LinearTransport</span></code></a>: Linear mapping estimation between Gaussians
<aclass="footnote-reference brackets" href="#id65" id="id34" role="doc-noteref"><spanclass="fn-bracket">[</span>14<spanclass="fn-bracket">]</span></a></p></li>
<li><p><aclass="reference internal" href="gen_modules/ot.da.html#id83" title="ot.da.MappingTransport"><codeclass="xref any py py-class docutils literal notranslate"><spanclass="pre">ot.da.MappingTransport</span></code></a>: Nonlinear mapping estimation <aclass="footnote-reference brackets" href="#id59" id="id35" role="doc-noteref"><spanclass="fn-bracket">[</span>8<spanclass="fn-bracket">]</span></a></p></li>
</ul>
</div>
<sectionid="examples-of-the-use-of-otda-classes">
<h4>Examples of the use of OTDA classes<aclass="headerlink" href="#examples-of-the-use-of-otda-classes" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="Linear OT mapping estimation"><imgalt="" src="_images/sphx_glr_plot_otda_linear_mapping_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_linear_mapping.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-linear-mapping-py"><spanclass="std std-ref">Linear OT mapping estimation</span></a></p>
<divclass="sphx-glr-thumbnail-title">Linear OT mapping estimation</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and OTDA approach with Laplacian regularization."><imgalt="" src="_images/sphx_glr_plot_otda_laplacian_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_laplacian.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-laplacian-py"><spanclass="std std-ref">OT with Laplacian regularization for domain adaptation</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT with Laplacian regularization for domain adaptation</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example presents a way of transferring colors between two images with Optimal Transport as introduced in [6]"><imgalt="" src="_images/sphx_glr_plot_otda_color_images_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_color_images.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-color-images-py"><spanclass="std std-ref">OT for image color adaptation</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for image color adaptation</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="OT for domain adaptation with image color adaptation [6] with mapping estimation [8]."><imgalt="" src="_images/sphx_glr_plot_otda_mapping_colors_images_thumb.png" />
<p><aclass="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"><spanclass="std std-ref">OT for image color adaptation with mapping estimation</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for image color adaptation with mapping estimation</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_otda_semi_supervised_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_semi_supervised.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-semi-supervised-py"><spanclass="std std-ref">OTDA unsupervised vs semi-supervised setting</span></a></p>
<divclass="sphx-glr-thumbnail-title">OTDA unsupervised vs semi-supervised setting</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example introduces a domain adaptation in a 2D setting and the 4 OTDA approaches currently supported in POT."><imgalt="" src="_images/sphx_glr_plot_otda_classes_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_classes.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-classes-py"><spanclass="std std-ref">OT for domain adaptation</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for domain adaptation</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_otda_d2_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_d2.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-d2-py"><spanclass="std std-ref">OT for domain adaptation on empirical distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for domain adaptation on empirical distributions</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example introduces a target shift problem with two 2D source and 1 target domain."><imgalt="" src="_images/sphx_glr_plot_otda_jcpot_thumb.png" />
<p><aclass="reference internal" href="auto_examples/domain-adaptation/plot_otda_jcpot.html#sphx-glr-auto-examples-domain-adaptation-plot-otda-jcpot-py"><spanclass="std std-ref">OT for multi-source target shift</span></a></p>
<divclass="sphx-glr-thumbnail-title">OT for multi-source target shift</div>
</div></div></section>
</section>
</section>
<sectionid="unbalanced-and-partial-ot">
<h2>Unbalanced and partial OT<aclass="headerlink" href="#unbalanced-and-partial-ot" title="Link to this heading"></a></h2>
<sectionid="unbalanced-optimal-transport">
<h3>Unbalanced optimal transport<aclass="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 <aclass="footnote-reference brackets" href="#id76" id="id36" role="doc-noteref"><spanclass="fn-bracket">[</span>25<spanclass="fn-bracket">]</span></a><aclass="footnote-reference brackets" href="#id61" id="id37" role="doc-noteref"><spanclass="fn-bracket">[</span>10<spanclass="fn-bracket">]</span></a>:</p>
<divclass="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 <aclass="footnote-reference brackets" href="#id61" id="id38" role="doc-noteref"><spanclass="fn-bracket">[</span>10<spanclass="fn-bracket">]</span></a>. We provide a solver for unbalanced OT
in <aclass="reference internal" href="gen_modules/ot.unbalanced.html#module-ot.unbalanced" title="ot.unbalanced"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="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 <aclass="reference internal" href="all.html#ot.sinkhorn_unbalanced" title="ot.sinkhorn_unbalanced"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn_unbalanced</span></code></a> and <aclass="reference internal" href="all.html#ot.sinkhorn_unbalanced2" title="ot.sinkhorn_unbalanced2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn_unbalanced2</span></code></a>
that return respectively the OT matrix and the value of the
linear term.</p>
<divclass="admonition note">
<pclass="admonition-title">Note</p>
<p>The main function to solve entropic regularized UOT is <aclass="reference internal" href="all.html#ot.sinkhorn_unbalanced" title="ot.sinkhorn_unbalanced"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.sinkhorn_unbalanced</span></code></a>.
This function is a wrapper and the parameter <codeclass="code docutils literal notranslate"><spanclass="pre">method</span></code> helps you select
the actual algorithm used to solve the problem:</p>
<ulclass="simple">
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn'</span></code> calls <aclass="reference internal" href="gen_modules/ot.unbalanced.html#ot.unbalanced.sinkhorn_knopp_unbalanced" title="ot.unbalanced.sinkhorn_knopp_unbalanced"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.unbalanced.sinkhorn_knopp_unbalanced</span></code></a>
the generalized Sinkhorn algorithm <aclass="footnote-reference brackets" href="#id76" id="id39" role="doc-noteref"><spanclass="fn-bracket">[</span>25<spanclass="fn-bracket">]</span></a><aclass="footnote-reference brackets" href="#id61" id="id40" role="doc-noteref"><spanclass="fn-bracket">[</span>10<spanclass="fn-bracket">]</span></a>.</p></li>
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn_stabilized'</span></code> calls <aclass="reference internal" href="gen_modules/ot.unbalanced.html#ot.unbalanced.sinkhorn_stabilized_unbalanced" title="ot.unbalanced.sinkhorn_stabilized_unbalanced"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.unbalanced.sinkhorn_stabilized_unbalanced</span></code></a>
the log stabilized version of the algorithm <aclass="footnote-reference brackets" href="#id61" id="id41" role="doc-noteref"><spanclass="fn-bracket">[</span>10<spanclass="fn-bracket">]</span></a>.</p></li>
</ul>
</div>
<sectionid="examples-of-unbalanced-ot">
<h4>Examples of Unbalanced OT<aclass="headerlink" href="#examples-of-unbalanced-ot" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of Unbalanced Optimal transport using a Kullback-Leibler relaxation."><imgalt="" src="_images/sphx_glr_plot_UOT_1D_thumb.png" />
<p><aclass="reference internal" href="auto_examples/unbalanced-partial/plot_UOT_1D.html#sphx-glr-auto-examples-unbalanced-partial-plot-uot-1d-py"><spanclass="std std-ref">1D Unbalanced optimal transport</span></a></p>
<divclass="sphx-glr-thumbnail-title">1D Unbalanced optimal transport</div>
</div><divclass="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."><imgalt="" src="_images/sphx_glr_plot_conv_sinkhorn_ti_thumb.png" />
<p><aclass="reference internal" href="auto_examples/unbalanced-partial/plot_conv_sinkhorn_ti.html#sphx-glr-auto-examples-unbalanced-partial-plot-conv-sinkhorn-ti-py"><spanclass="std std-ref">Translation Invariant Sinkhorn for Unbalanced Optimal Transport</span></a></p>
<divclass="sphx-glr-thumbnail-title">Translation Invariant Sinkhorn for Unbalanced Optimal Transport</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="UOT aims at solving the following optimization problem:"><imgalt="" src="_images/sphx_glr_plot_unbalanced_OT_thumb.png" />
<p><aclass="reference internal" href="auto_examples/unbalanced-partial/plot_unbalanced_OT.html#sphx-glr-auto-examples-unbalanced-partial-plot-unbalanced-ot-py"><spanclass="std std-ref">2D examples of exact and entropic unbalanced optimal transport</span></a></p>
<divclass="sphx-glr-thumbnail-title">2D examples of exact and entropic unbalanced optimal transport</div>
</div></div></section>
</section>
<sectionid="unbalanced-barycenters">
<h3>Unbalanced Barycenters<aclass="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><divclass="math notranslate nohighlight">
\[\min_{\mu} \quad \sum_{k} w_kW_u(\mu,\mu_k)\]</div>
</div></blockquote>
<p>where <spanclass="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 <aclass="reference internal" href="all.html#ot.barycenter_unbalanced" title="ot.barycenter_unbalanced"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.barycenter_unbalanced</span></code></a>.</p>
<divclass="admonition note">
<pclass="admonition-title">Note</p>
<p>The main function to compute UOT barycenters is <aclass="reference internal" href="all.html#ot.barycenter_unbalanced" title="ot.barycenter_unbalanced"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.barycenter_unbalanced</span></code></a>.
This function is a wrapper and the parameter <codeclass="code docutils literal notranslate"><spanclass="pre">method</span></code> helps you select
the actual algorithm used to solve the problem:</p>
<ulclass="simple">
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn'</span></code> calls <codeclass="xref py py-meth docutils literal notranslate"><spanclass="pre">ot.unbalanced.barycenter_unbalanced_sinkhorn_unbalanced()</span></code>
the generalized Sinkhorn algorithm <aclass="footnote-reference brackets" href="#id61" id="id42" role="doc-noteref"><spanclass="fn-bracket">[</span>10<spanclass="fn-bracket">]</span></a>.</p></li>
<li><p><codeclass="code docutils literal notranslate"><spanclass="pre">method='sinkhorn_stabilized'</span></code> calls <aclass="reference internal" href="gen_modules/ot.unbalanced.html#ot.unbalanced.barycenter_unbalanced_stabilized" title="ot.unbalanced.barycenter_unbalanced_stabilized"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.unbalanced.barycenter_unbalanced_stabilized</span></code></a>
the log stabilized version of the algorithm <aclass="footnote-reference brackets" href="#id61" id="id43" role="doc-noteref"><spanclass="fn-bracket">[</span>10<spanclass="fn-bracket">]</span></a>.</p></li>
</ul>
</div>
<sectionid="examples-of-unbalanced-ot-barycenters">
<h4>Examples of Unbalanced OT barycenters<aclass="headerlink" href="#examples-of-unbalanced-ot-barycenters" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation of regularized Wasserstein Barycenter as proposed in [10] for Unbalanced inputs."><imgalt="" src="_images/sphx_glr_plot_UOT_barycenter_1D_thumb.png" />
<p><aclass="reference internal" href="auto_examples/unbalanced-partial/plot_UOT_barycenter_1D.html#sphx-glr-auto-examples-unbalanced-partial-plot-uot-barycenter-1d-py"><spanclass="std std-ref">1D Wasserstein barycenter demo for Unbalanced distributions</span></a></p>
<divclass="sphx-glr-thumbnail-title">1D Wasserstein barycenter demo for Unbalanced distributions</div>
</div></div></section>
</section>
<sectionid="partial-optimal-transport">
<h3>Partial optimal transport<aclass="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 <aclass="footnote-reference brackets" href="#id78" id="id44" role="doc-noteref"><spanclass="fn-bracket">[</span>28<spanclass="fn-bracket">]</span></a>:</p>
<divclass="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 <aclass="footnote-reference brackets" href="#id79" id="id45" role="doc-noteref"><spanclass="fn-bracket">[</span>29<spanclass="fn-bracket">]</span></a>. We provide a solver for partial OT
in <aclass="reference internal" href="gen_modules/ot.partial.html#module-ot.partial" title="ot.partial"><codeclass="xref any py py-mod docutils literal notranslate"><spanclass="pre">ot.partial</span></code></a>. The exact resolution of the problem is computed in <aclass="reference internal" href="gen_modules/ot.partial.html#id34" title="ot.partial.partial_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.partial.partial_wasserstein</span></code></a>
and <aclass="reference internal" href="gen_modules/ot.partial.html#id37" title="ot.partial.partial_wasserstein2"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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 <aclass="reference internal" href="gen_modules/ot.partial.html#id21" title="ot.partial.entropic_partial_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.partial.entropic_partial_wasserstein</span></code></a>
(see <aclass="footnote-reference brackets" href="#id55" id="id46" role="doc-noteref"><spanclass="fn-bracket">[</span>3<spanclass="fn-bracket">]</span></a>).</p>
<p>The partial Gromov-Wasserstein formulation of the problem</p>
<divclass="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 <aclass="reference internal" href="gen_modules/ot.partial.html#id28" title="ot.partial.partial_gromov_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.partial.partial_gromov_wasserstein</span></code></a> and in
<aclass="reference internal" href="gen_modules/ot.partial.html#id0" title="ot.partial.entropic_partial_gromov_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.partial.entropic_partial_gromov_wasserstein</span></code></a> when considering the entropic
regularization of the problem.</p>
<sectionid="examples-of-partial-ot">
<h4>Examples of Partial OT<aclass="headerlink" href="#examples-of-partial-ot" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="UOT aims at solving the following optimization problem:"><imgalt="" src="_images/sphx_glr_plot_unbalanced_OT_thumb.png" />
<p><aclass="reference internal" href="auto_examples/unbalanced-partial/plot_unbalanced_OT.html#sphx-glr-auto-examples-unbalanced-partial-plot-unbalanced-ot-py"><spanclass="std std-ref">2D examples of exact and entropic unbalanced optimal transport</span></a></p>
<divclass="sphx-glr-thumbnail-title">2D examples of exact and entropic unbalanced optimal transport</div>
</div><divclass="sphx-glr-thumbcontainer" tooltip="This example is designed to show how to use the Partial (Gromov-)Wasserstein distance computation in POT."><imgalt="" src="_images/sphx_glr_plot_partial_wass_and_gromov_thumb.png" />
<p><aclass="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"><spanclass="std std-ref">Partial Wasserstein and Gromov-Wasserstein example</span></a></p>
<divclass="sphx-glr-thumbnail-title">Partial Wasserstein and Gromov-Wasserstein example</div>
</div></div></section>
</section>
</section>
<sectionid="gromov-wasserstein-and-extensions">
<h2>Gromov Wasserstein and extensions<aclass="headerlink" href="#gromov-wasserstein-and-extensions" title="Link to this heading"></a></h2>
<sectionid="gromov-wasserstein-gw">
<h3>Gromov Wasserstein(GW)<aclass="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 <aclass="footnote-reference brackets" href="#id64" id="id47" role="doc-noteref"><spanclass="fn-bracket">[</span>13<spanclass="fn-bracket">]</span></a>. In this case one cannot compute distance between samples
from the two distributions. <aclass="footnote-reference brackets" href="#id64" id="id48" role="doc-noteref"><spanclass="fn-bracket">[</span>13<spanclass="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>
<divclass="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 :<spanclass="math notranslate nohighlight">\(C1\)</span> is the distance matrix between samples in the source
distribution and <spanclass="math notranslate nohighlight">\(C2\)</span> the one between samples in the target,
<spanclass="math notranslate nohighlight">\(L(C1_{i,k},C2_{j,l})\)</span> is a measure of similarity between
<spanclass="math notranslate nohighlight">\(C1_{i,k}\)</span> and <spanclass="math notranslate nohighlight">\(C2_{j,l}\)</span> often chosen as
<spanclass="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 <aclass="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.gromov_wasserstein" title="ot.gromov.gromov_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gromov.gromov_wasserstein</span></code></a>.
There also exists an entropic regularized variant of GW that has been proposed in
<aclass="footnote-reference brackets" href="#id63" id="id49" role="doc-noteref"><spanclass="fn-bracket">[</span>12<spanclass="fn-bracket">]</span></a> and we provide an implementation of their algorithm in
<aclass="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.entropic_gromov_wasserstein" title="ot.gromov.entropic_gromov_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gromov.entropic_gromov_wasserstein</span></code></a>.</p>
<sectionid="examples-of-computation-of-gw-regularized-g-and-fgw">
<h4>Examples of computation of GW, regularized G and FGW<aclass="headerlink" href="#examples-of-computation-of-gw-regularized-g-and-fgw" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="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)."><imgalt="" src="_images/sphx_glr_plot_gromov_thumb.png" />
<p><aclass="reference internal" href="auto_examples/gromov/plot_gromov.html#sphx-glr-auto-examples-gromov-plot-gromov-py"><spanclass="std std-ref">Gromov-Wasserstein example</span></a></p>
<divclass="sphx-glr-thumbnail-title">Gromov-Wasserstein example</div>
</div></div></section>
</section>
<sectionid="gromov-wasserstein-barycenters">
<h3>Gromov Wasserstein barycenters<aclass="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>
<divclass="math notranslate nohighlight">
\[\min_{C\geq 0} \quad \sum_{k} w_k GW(C,Ck)\]</div>
<p>where <spanclass="math notranslate nohighlight">\(Ck\)</span> is the distance matrix between samples in distribution
<spanclass="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
<aclass="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.gromov_barycenters" title="ot.gromov.gromov_barycenters"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gromov.gromov_barycenters</span></code></a> and
<aclass="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.entropic_gromov_barycenters" title="ot.gromov.entropic_gromov_barycenters"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="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 <aclass="footnote-reference brackets" href="#id75" id="id50" role="doc-noteref"><spanclass="fn-bracket">[</span>24<spanclass="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
<aclass="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.fused_gromov_wasserstein" title="ot.gromov.fused_gromov_wasserstein"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gromov.fused_gromov_wasserstein</span></code></a> and <aclass="reference internal" href="gen_modules/ot.gromov.html#ot.gromov.fgw_barycenters" title="ot.gromov.fgw_barycenters"><codeclass="xref any py py-func docutils literal notranslate"><spanclass="pre">ot.gromov.fgw_barycenters</span></code></a>.</p>
<sectionid="examples-of-gw-regularized-g-and-fgw-barycenters">
<h4>Examples of GW, regularized G and FGW barycenters<aclass="headerlink" href="#examples-of-gw-regularized-g-and-fgw-barycenters" title="Link to this heading"></a></h4>
<divclass="sphx-glr-thumbnails"><divclass="sphx-glr-thumbcontainer" tooltip="This example illustrates the computation barycenter of labeled graphs using FGW [18]."><imgalt="" src="_images/sphx_glr_plot_barycenter_fgw_thumb.png" />
<p><aclass="reference internal" href="auto_examples/gromov/plot_barycenter_fgw.html#sphx-glr-auto-examples-gromov-plot-barycenter-fgw-py"><spanclass="std std-ref">Plot graphs barycenter using FGW</span></a></p>