API and modules

ot:

lp

Solvers for the original linear program OT problem

bregman

Bregman projections solvers for entropic regularized OT

smooth

Smooth and Sparse Optimal Transport solvers (KL an L2 reg.)

gromov

Gromov-Wasserstein and Fused-Gromov-Wasserstein solvers

optim

Generic solvers for regularized OT

da

Domain adaptation with optimal transport

gpu

GPU implementation for several OT solvers and utility functions.

dr

Dimension reduction with OT

utils

Various useful functions

datasets

Simple example datasets

plot

Functions for plotting OT matrices

stochastic

Stochastic solvers for regularized OT.

unbalanced

Regularized Unbalanced OT solvers

partial

Partial OT solvers

sliced

Sliced Wasserstein Distance.

Warning

The list of automatically imported sub-modules is as follows: ot.lp, ot.bregman, ot.optim ot.utils, ot.datasets, ot.gromov, ot.smooth ot.stochastic

The following sub-modules are not imported due to additional dependencies:

  • ot.dr : depends on pymanopt and autograd.

  • ot.gpu : depends on cupy and a CUDA GPU.

  • ot.plot : depends on matplotlib

ot.barycenter(A, M, reg, weights=None, method='sinkhorn', numItermax=10000, stopThr=0.0001, verbose=False, log=False, **kwargs)[source]

Compute the entropic regularized wasserstein barycenter of distributions A

The function solves the following optimization problem:

\[\mathbf{a} = arg\min_\mathbf{a} \sum_i W_{reg}(\mathbf{a},\mathbf{a}_i)\]

where :

  • \(W_{reg}(\cdot,\cdot)\) is the entropic regularized Wasserstein distance (see ot.bregman.sinkhorn)

  • \(\mathbf{a}_i\) are training distributions in the columns of matrix \(\mathbf{A}\)

  • reg and \(\mathbf{M}\) are respectively the regularization term and the cost matrix for OT

The algorithm used for solving the problem is the Sinkhorn-Knopp matrix scaling algorithm as proposed in [3]_

Parameters
  • A (ndarray, shape (dim, n_hists)) – n_hists training distributions a_i of size dim

  • M (ndarray, shape (dim, dim)) – loss matrix for OT

  • reg (float) – Regularization term > 0

  • method (str (optional)) – method used for the solver either ‘sinkhorn’ or ‘sinkhorn_stabilized’

  • weights (ndarray, shape (n_hists,)) – Weights of each histogram a_i on the simplex (barycentric coodinates)

  • numItermax (int, optional) – Max number of iterations

  • stopThr (float, optional) – Stop threshol on error (>0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

Returns

  • a ((dim,) ndarray) – Wasserstein barycenter

  • log (dict) – log dictionary return only if log==True in parameters

References

3

Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015). Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2), A1111-A1138.

ot.barycenter_unbalanced(A, M, reg, reg_m, method='sinkhorn', weights=None, numItermax=1000, stopThr=1e-06, verbose=False, log=False, **kwargs)[source]

Compute the entropic unbalanced wasserstein barycenter of A.

The function solves the following optimization problem with a

\[\mathbf{a} = arg\min_\mathbf{a} \sum_i Wu_{reg}(\mathbf{a},\mathbf{a}_i)\]

where :

  • \(Wu_{reg}(\cdot,\cdot)\) is the unbalanced entropic regularized

Wasserstein distance (see ot.unbalanced.sinkhorn_unbalanced) - \(\mathbf{a}_i\) are training distributions in the columns of matrix \(\mathbf{A}\) - reg and \(\mathbf{M}\) are respectively the regularization term and the cost matrix for OT - reg_mis the marginal relaxation hyperparameter The algorithm used for solving the problem is the generalized Sinkhorn-Knopp matrix scaling algorithm as proposed in [10]_

Parameters
  • A (np.ndarray (dim, n_hists)) – n_hists training distributions a_i of dimension dim

  • M (np.ndarray (dim, dim)) – ground metric matrix for OT.

  • reg (float) – Entropy regularization term > 0

  • reg_m (float) – Marginal relaxation term > 0

  • weights (np.ndarray (n_hists,) optional) – Weight of each distribution (barycentric coodinates) If None, uniform weights are used.

  • numItermax (int, optional) – Max number of iterations

  • stopThr (float, optional) – Stop threshol on error (> 0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

Returns

  • a ((dim,) ndarray) – Unbalanced Wasserstein barycenter

  • log (dict) – log dictionary return only if log==True in parameters

References

3

Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015). Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2), A1111-A1138.

10

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprin arXiv:1607.05816.

ot.dist(x1, x2=None, metric='sqeuclidean')[source]

Compute distance between samples in x1 and x2 using function scipy.spatial.distance.cdist

Parameters
  • x1 (ndarray, shape (n1,d)) – matrix with n1 samples of size d

  • x2 (array, shape (n2,d), optional) – matrix with n2 samples of size d (if None then x2=x1)

  • metric (str | callable, optional) – Name of the metric to be computed (full list in the doc of scipy), If a string, the distance function can be ‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘wminkowski’, ‘yule’.

Returns

M – distance matrix computed with given metric

Return type

np.array (n1,n2)

ot.emd(a, b, M, numItermax=100000, log=False, center_dual=True)[source]

Solves the Earth Movers distance problem and returns the OT matrix

\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma <\gamma,M>_F\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the metric cost matrix

  • a and b are the sample weights

Warning

Note that the M matrix needs to be a C-order numpy.array in float64 format.

Uses the algorithm proposed in [1]_

Parameters
  • a ((ns,) numpy.ndarray, float64) – Source histogram (uniform weight if empty list)

  • b ((nt,) numpy.ndarray, float64) – Target histogram (uniform weight if empty list)

  • M ((ns,nt) numpy.ndarray, float64) – Loss matrix (c-order array with type float64)

  • numItermax (int, optional (default=100000)) – The maximum number of iterations before stopping the optimization algorithm if it has not converged.

  • log (bool, optional (default=False)) – If True, returns a dictionary containing the cost and dual variables. Otherwise returns only the optimal transportation matrix.

  • center_dual (boolean, optional (default=True)) – If True, centers the dual potential using function center_ot_dual.

Returns

  • gamma ((ns x nt) numpy.ndarray) – Optimal transportation matrix for the given parameters

  • log (dict) – If input log is true, a dictionary containing the cost and dual variables and exit status

Examples

Simple example with obvious solution. The function emd accepts lists and perform automatic conversion to numpy arrays

>>> import ot
>>> a=[.5,.5]
>>> b=[.5,.5]
>>> M=[[0.,1.],[1.,0.]]
>>> ot.emd(a,b,M)
array([[0.5, 0. ],
       [0. , 0.5]])

References

1

Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, December). Displacement interpolation using Lagrangian mass transport. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.

See also

ot.bregman.sinkhorn

Entropic regularized OT

ot.optim.cg

General regularized OT

ot.emd2(a, b, M, processes=36, numItermax=100000, log=False, return_matrix=False, center_dual=True)[source]

Solves the Earth Movers distance problem and returns the loss

\[ \begin{align}\begin{aligned}\min_\gamma <\gamma,M>_F\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the metric cost matrix

  • a and b are the sample weights

Warning

Note that the M matrix needs to be a C-order numpy.array in float64 format.

Uses the algorithm proposed in [1]_

Parameters
  • a ((ns,) numpy.ndarray, float64) – Source histogram (uniform weight if empty list)

  • b ((nt,) numpy.ndarray, float64) – Target histogram (uniform weight if empty list)

  • M ((ns,nt) numpy.ndarray, float64) – Loss matrix (c-order array with type float64)

  • processes (int, optional (default=nb cpu)) – Nb of processes used for multiple emd computation (not used on windows)

  • numItermax (int, optional (default=100000)) – The maximum number of iterations before stopping the optimization algorithm if it has not converged.

  • log (boolean, optional (default=False)) – If True, returns a dictionary containing the cost and dual variables. Otherwise returns only the optimal transportation cost.

  • return_matrix (boolean, optional (default=False)) – If True, returns the optimal transportation matrix in the log.

  • center_dual (boolean, optional (default=True)) – If True, centers the dual potential using function center_ot_dual.

Returns

  • gamma ((ns x nt) ndarray) – Optimal transportation matrix for the given parameters

  • log (dictnp) – If input log is true, a dictionary containing the cost and dual variables and exit status

Examples

Simple example with obvious solution. The function emd accepts lists and perform automatic conversion to numpy arrays

>>> import ot
>>> a=[.5,.5]
>>> b=[.5,.5]
>>> M=[[0.,1.],[1.,0.]]
>>> ot.emd2(a,b,M)
0.0

References

1

Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, December). Displacement interpolation using Lagrangian mass transport. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.

See also

ot.bregman.sinkhorn

Entropic regularized OT

ot.optim.cg

General regularized OT

ot.emd2_1d(x_a, x_b, a=None, b=None, metric='sqeuclidean', p=1.0, dense=True, log=False)[source]

Solves the Earth Movers distance problem between 1d measures and returns the loss

\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma \sum_i \sum_j \gamma_{ij} d(x_a[i], x_b[j])\\s.t. \gamma 1 = a, \gamma^T 1= b, \gamma\geq 0\end{aligned}\end{align} \]

where :

  • d is the metric

  • x_a and x_b are the samples

  • a and b are the sample weights

When ‘minkowski’ is used as a metric, \(d(x, y) = |x - y|^p\).

Uses the algorithm detailed in [1]_

Parameters
  • x_a ((ns,) or (ns, 1) ndarray, float64) – Source dirac locations (on the real line)

  • x_b ((nt,) or (ns, 1) ndarray, float64) – Target dirac locations (on the real line)

  • a ((ns,) ndarray, float64, optional) – Source histogram (default is uniform weight)

  • b ((nt,) ndarray, float64, optional) – Target histogram (default is uniform weight)

  • metric (str, optional (default='sqeuclidean')) – Metric to be used. Only strings listed in ot.dist() are accepted. Due to implementation details, this function runs faster when ‘sqeuclidean’, ‘minkowski’, ‘cityblock’, or ‘euclidean’ metrics are used.

  • p (float, optional (default=1.0)) – The p-norm to apply for if metric=’minkowski’

  • dense (boolean, optional (default=True)) – If True, returns math:gamma as a dense ndarray of shape (ns, nt). Otherwise returns a sparse representation using scipy’s coo_matrix format. Only used if log is set to True. Due to implementation details, this function runs faster when dense is set to False.

  • log (boolean, optional (default=False)) – If True, returns a dictionary containing the transportation matrix. Otherwise returns only the loss.

Returns

  • loss (float) – Cost associated to the optimal transportation

  • log (dict) – If input log is True, a dictionary containing the Optimal transportation matrix for the given parameters

Examples

Simple example with obvious solution. The function emd2_1d accepts lists and performs automatic conversion to numpy arrays

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> x_a = [2., 0.]
>>> x_b = [0., 3.]
>>> ot.emd2_1d(x_a, x_b, a, b)
0.5
>>> ot.emd2_1d(x_a, x_b)
0.5

References

1

Peyré, G., & Cuturi, M. (2017). “Computational Optimal Transport”, 2018.

See also

ot.lp.emd2

EMD for multidimensional distributions

ot.lp.emd_1d

EMD for 1d distributions (returns the transportation matrix instead of the cost)

ot.emd_1d(x_a, x_b, a=None, b=None, metric='sqeuclidean', p=1.0, dense=True, log=False)[source]

Solves the Earth Movers distance problem between 1d measures and returns the OT matrix

\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma \sum_i \sum_j \gamma_{ij} d(x_a[i], x_b[j])\\s.t. \gamma 1 = a, \gamma^T 1= b, \gamma\geq 0\end{aligned}\end{align} \]

where :

  • d is the metric

  • x_a and x_b are the samples

  • a and b are the sample weights

When ‘minkowski’ is used as a metric, \(d(x, y) = |x - y|^p\).

Uses the algorithm detailed in [1]_

Parameters
  • x_a ((ns,) or (ns, 1) ndarray, float64) – Source dirac locations (on the real line)

  • x_b ((nt,) or (ns, 1) ndarray, float64) – Target dirac locations (on the real line)

  • a ((ns,) ndarray, float64, optional) – Source histogram (default is uniform weight)

  • b ((nt,) ndarray, float64, optional) – Target histogram (default is uniform weight)

  • metric (str, optional (default='sqeuclidean')) – Metric to be used. Only strings listed in ot.dist() are accepted. Due to implementation details, this function runs faster when ‘sqeuclidean’, ‘cityblock’, or ‘euclidean’ metrics are used.

  • p (float, optional (default=1.0)) – The p-norm to apply for if metric=’minkowski’

  • dense (boolean, optional (default=True)) – If True, returns math:gamma as a dense ndarray of shape (ns, nt). Otherwise returns a sparse representation using scipy’s coo_matrix format. Due to implementation details, this function runs faster when ‘sqeuclidean’, ‘minkowski’, ‘cityblock’, or ‘euclidean’ metrics are used.

  • log (boolean, optional (default=False)) – If True, returns a dictionary containing the cost. Otherwise returns only the optimal transportation matrix.

Returns

  • gamma ((ns, nt) ndarray) – Optimal transportation matrix for the given parameters

  • log (dict) – If input log is True, a dictionary containing the cost

Examples

Simple example with obvious solution. The function emd_1d accepts lists and performs automatic conversion to numpy arrays

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> x_a = [2., 0.]
>>> x_b = [0., 3.]
>>> ot.emd_1d(x_a, x_b, a, b)
array([[0. , 0.5],
       [0.5, 0. ]])
>>> ot.emd_1d(x_a, x_b)
array([[0. , 0.5],
       [0.5, 0. ]])

References

1

Peyré, G., & Cuturi, M. (2017). “Computational Optimal Transport”, 2018.

See also

ot.lp.emd

EMD for multidimensional distributions

ot.lp.emd2_1d

EMD for 1d distributions (returns cost instead of the transportation matrix)

ot.sinkhorn(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, **kwargs)[source]

Solve the entropic regularization optimal transport problem and return the OT matrix

The function solves the following optimization problem:

\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma)\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the (dim_a, dim_b) metric cost matrix

  • \(\Omega\) is the entropic regularization term \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

  • a and b are source and target weights (histograms, both sum to 1)

The algorithm used for solving the problem is the Sinkhorn-Knopp matrix scaling algorithm as proposed in [2]_

Parameters
  • a (ndarray, shape (dim_a,)) – samples weights in the source domain

  • b (ndarray, shape (dim_b,) or ndarray, shape (dim_b, n_hists)) – samples in the target domain, compute sinkhorn with multiple targets and fixed M if b is a matrix (return OT loss + dual variables in log)

  • M (ndarray, shape (dim_a, dim_b)) – loss matrix

  • reg (float) – Regularization term >0

  • method (str) – method used for the solver either ‘sinkhorn’, ‘greenkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_epsilon_scaling’, see those function for specific parameters

  • numItermax (int, optional) – Max number of iterations

  • stopThr (float, optional) – Stop threshol on error (>0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

  • a Sinkhorn solver** (**Choosing) –

  • default and when using a regularization parameter that is not too small (By) –

  • default sinkhorn solver should be enough. If you need to use a small (the) –

  • to get sharper OT matrices (regularization) –

  • should use the (you) –

:param ot.bregman.sinkhorn_stabilized solver that will avoid numerical: :param errors. This last solver can be very slow in practice and might not even: :param converge to a reasonable OT matrix in a finite time. This is why: :param ot.bregman.sinkhorn_epsilon_scaling that relie on iterating the value: :param of the regularization (and using warm start) sometimes leads to better: :param solutions. Note that the greedy version of the sinkhorn: :param ot.bregman.greenkhorn can also lead to a speedup and the screening: :param version of the sinkhorn ot.bregman.screenkhorn aim a providing a: :param fast approximation of the Sinkhorn problem.:

Returns

  • gamma (ndarray, shape (dim_a, dim_b)) – Optimal transportation matrix for the given parameters

  • log (dict) – log dictionary return only if log==True in parameters

Examples

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> M=[[0., 1.], [1., 0.]]
>>> ot.sinkhorn(a, b, M, 1)
array([[0.36552929, 0.13447071],
       [0.13447071, 0.36552929]])

References

2
  1. Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013

9

Schmitzer, B. (2016). Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems. arXiv preprint arXiv:1610.06519.

10

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprint arXiv:1607.05816.

See also

ot.lp.emd

Unregularized OT

ot.optim.cg

General regularized OT

ot.bregman.sinkhorn_knopp

Classic Sinkhorn [2]

ot.bregman.sinkhorn_stabilized

Stabilized sinkhorn [9][10]

ot.bregman.sinkhorn_epsilon_scaling

Sinkhorn with epslilon scaling [9][10]

ot.sinkhorn2(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, **kwargs)[source]

Solve the entropic regularization optimal transport problem and return the loss

The function solves the following optimization problem:

\[ \begin{align}\begin{aligned}W = \min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma)\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the (dim_a, dim_b) metric cost matrix

  • \(\Omega\) is the entropic regularization term \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

  • a and b are source and target weights (histograms, both sum to 1)

The algorithm used for solving the problem is the Sinkhorn-Knopp matrix scaling algorithm as proposed in [2]_

Parameters
  • a (ndarray, shape (dim_a,)) – samples weights in the source domain

  • b (ndarray, shape (dim_b,) or ndarray, shape (dim_b, n_hists)) – samples in the target domain, compute sinkhorn with multiple targets and fixed M if b is a matrix (return OT loss + dual variables in log)

  • M (ndarray, shape (dim_a, dim_b)) – loss matrix

  • reg (float) – Regularization term >0

  • method (str) – method used for the solver either ‘sinkhorn’, ‘sinkhorn_stabilized’, see those function for specific parameters

  • numItermax (int, optional) – Max number of iterations

  • stopThr (float, optional) – Stop threshol on error (>0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

  • a Sinkhorn solver** (**Choosing) –

  • default and when using a regularization parameter that is not too small (By) –

  • default sinkhorn solver should be enough. If you need to use a small (the) –

  • to get sharper OT matrices (regularization) –

  • should use the (you) –

:param ot.bregman.sinkhorn_stabilized solver that will avoid numerical: :param errors. This last solver can be very slow in practice and might not even: :param converge to a reasonable OT matrix in a finite time. This is why: :param ot.bregman.sinkhorn_epsilon_scaling that relie on iterating the value: :param of the regularization (and using warm start) sometimes leads to better: :param solutions. Note that the greedy version of the sinkhorn: :param ot.bregman.greenkhorn can also lead to a speedup and the screening: :param version of the sinkhorn ot.bregman.screenkhorn aim a providing a: :param fast approximation of the Sinkhorn problem.:

Returns

  • W ((n_hists) ndarray) – Optimal transportation loss for the given parameters

  • log (dict) – log dictionary return only if log==True in parameters

Examples

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> M=[[0., 1.], [1., 0.]]
>>> ot.sinkhorn2(a, b, M, 1)
array([0.26894142])

References

2
  1. Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013

9

Schmitzer, B. (2016). Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems. arXiv preprint arXiv:1610.06519.

10

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprint arXiv:1607.05816.

[21] Altschuler J., Weed J., Rigollet P. : Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, Advances in Neural Information Processing Systems (NIPS) 31, 2017

See also

ot.lp.emd

Unregularized OT

ot.optim.cg

General regularized OT

ot.bregman.sinkhorn_knopp

Classic Sinkhorn [2]

ot.bregman.greenkhorn

Greenkhorn [21]

ot.bregman.sinkhorn_stabilized

Stabilized sinkhorn [9][10]

ot.sinkhorn_lpl1_mm(a, labels_a, b, M, reg, eta=0.1, numItermax=10, numInnerItermax=200, stopInnerThr=1e-09, verbose=False, log=False)[source]

Solve the entropic regularization optimal transport problem with nonconvex group lasso regularization

The function solves the following optimization problem:

\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega_e(\gamma) + \eta \Omega_g(\gamma)\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the (ns,nt) metric cost matrix

  • \(\Omega_e\) is the entropic regularization term \(\Omega_e (\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

  • \(\Omega_g\) is the group lasso regularization term \(\Omega_g(\gamma)=\sum_{i,c} \|\gamma_{i,\mathcal{I}_c}\|^{1/2}_1\) where \(\mathcal{I}_c\) are the index of samples from class c in the source domain.

  • a and b are source and target weights (sum to 1)

The algorithm used for solving the problem is the generalized conditional gradient as proposed in 5 7

Parameters
  • a (np.ndarray (ns,)) – samples weights in the source domain

  • labels_a (np.ndarray (ns,)) – labels of samples in the source domain

  • b (np.ndarray (nt,)) – samples weights in the target domain

  • M (np.ndarray (ns,nt)) – loss matrix

  • reg (float) – Regularization term for entropic regularization >0

  • eta (float, optional) – Regularization term for group lasso regularization >0

  • numItermax (int, optional) – Max number of iterations

  • numInnerItermax (int, optional) – Max number of iterations (inner sinkhorn solver)

  • stopInnerThr (float, optional) – Stop threshold on error (inner sinkhorn solver) (>0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

Returns

  • gamma ((ns x nt) ndarray) – Optimal transportation matrix for the given parameters

  • log (dict) – log dictionary return only if log==True in parameters

References

5

N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, “Optimal Transport for Domain Adaptation,” in IEEE Transactions on Pattern Analysis and Machine Intelligence , vol.PP, no.99, pp.1-1

7

Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). Generalized conditional gradient: analysis of convergence and applications. arXiv preprint arXiv:1510.06567.

See also

ot.lp.emd

Unregularized OT

ot.bregman.sinkhorn

Entropic regularized OT

ot.optim.cg

General regularized OT

ot.sinkhorn_unbalanced(a, b, M, reg, reg_m, method='sinkhorn', numItermax=1000, stopThr=1e-06, verbose=False, log=False, **kwargs)[source]

Solve the unbalanced entropic regularization optimal transport problem and return the OT plan

The function solves the following optimization problem:

\[ \begin{align}\begin{aligned}W = \min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + reg_m KL(\gamma 1, a) + reg_m KL(\gamma^T 1, b)\\s.t. \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the (dim_a, dim_b) metric cost matrix

  • \(\Omega\) is the entropic regularization

    term \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

  • a and b are source and target unbalanced distributions

  • KL is the Kullback-Leibler divergence

The algorithm used for solving the problem is the generalized

Sinkhorn-Knopp matrix scaling algorithm as proposed in [10, 23]_

Parameters
  • a (np.ndarray (dim_a,)) – Unnormalized histogram of dimension dim_a

  • b (np.ndarray (dim_b,) or np.ndarray (dim_b, n_hists)) – One or multiple unnormalized histograms of dimension dim_b If many, compute all the OT distances (a, b_i)

  • M (np.ndarray (dim_a, dim_b)) – loss matrix

  • reg (float) – Entropy regularization term > 0

  • reg_m (float) – Marginal relaxation term > 0

  • method (str) – method used for the solver either ‘sinkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_reg_scaling’, see those function for specific parameters

  • numItermax (int, optional) – Max number of iterations

  • stopThr (float, optional) – Stop threshol on error (>0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

Returns

  • if n_hists == 1

    gamma(dim_a x dim_b) ndarray

    Optimal transportation matrix for the given parameters

    logdict

    log dictionary returned only if log is True

  • else

    ot_distance(n_hists,) ndarray

    the OT distance between a and each of the histograms b_i

    logdict

    log dictionary returned only if log is True

Examples

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> M=[[0., 1.], [1., 0.]]
>>> ot.sinkhorn_unbalanced(a, b, M, 1, 1)
array([[0.51122823, 0.18807035],
       [0.18807035, 0.51122823]])

References

2

M. Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013

9

Schmitzer, B. (2016). Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems. arXiv preprint arXiv:1610.06519.

10

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprint arXiv:1607.05816.

25

Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. : Learning with a Wasserstein Loss, Advances in Neural Information Processing Systems (NIPS) 2015

See also

ot.unbalanced.sinkhorn_knopp_unbalanced

Unbalanced Classic Sinkhorn [10]

ot.unbalanced.sinkhorn_stabilized_unbalanced

Unbalanced Stabilized sinkhorn [9][10]

ot.unbalanced.sinkhorn_reg_scaling_unbalanced

Unbalanced Sinkhorn with epslilon scaling [9][10]

ot.sinkhorn_unbalanced2(a, b, M, reg, reg_m, method='sinkhorn', numItermax=1000, stopThr=1e-06, verbose=False, log=False, **kwargs)[source]

Solve the entropic regularization unbalanced optimal transport problem and return the loss

The function solves the following optimization problem:

\[ \begin{align}\begin{aligned}W = \min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + reg_m KL(\gamma 1, a) + reg_m KL(\gamma^T 1, b)\\s.t. \gamma\geq 0\end{aligned}\end{align} \]

where :

  • M is the (dim_a, dim_b) metric cost matrix

  • \(\Omega\) is the entropic regularization term

    \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

  • a and b are source and target unbalanced distributions

  • KL is the Kullback-Leibler divergence

The algorithm used for solving the problem is the generalized Sinkhorn-Knopp matrix scaling algorithm as proposed in [10, 23]_

Parameters
  • a (np.ndarray (dim_a,)) – Unnormalized histogram of dimension dim_a

  • b (np.ndarray (dim_b,) or np.ndarray (dim_b, n_hists)) – One or multiple unnormalized histograms of dimension dim_b If many, compute all the OT distances (a, b_i)

  • M (np.ndarray (dim_a, dim_b)) – loss matrix

  • reg (float) – Entropy regularization term > 0

  • reg_m (float) – Marginal relaxation term > 0

  • method (str) – method used for the solver either ‘sinkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_reg_scaling’, see those function for specific parameters

  • numItermax (int, optional) – Max number of iterations

  • stopThr (float, optional) – Stop threshol on error (>0)

  • verbose (bool, optional) – Print information along iterations

  • log (bool, optional) – record log if True

Returns

  • ot_distance ((n_hists,) ndarray) – the OT distance between a and each of the histograms b_i

  • log (dict) – log dictionary returned only if log is True

Examples

>>> import ot
>>> a=[.5, .10]
>>> b=[.5, .5]
>>> M=[[0., 1.],[1., 0.]]
>>> ot.unbalanced.sinkhorn_unbalanced2(a, b, M, 1., 1.)
array([0.31912866])

References

2

M. Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013

9

Schmitzer, B. (2016). Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems. arXiv preprint arXiv:1610.06519.

10

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprint arXiv:1607.05816.

25

Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. : Learning with a Wasserstein Loss, Advances in Neural Information Processing Systems (NIPS) 2015

See also

ot.unbalanced.sinkhorn_knopp

Unbalanced Classic Sinkhorn [10]

ot.unbalanced.sinkhorn_stabilized

Unbalanced Stabilized sinkhorn [9][10]

ot.unbalanced.sinkhorn_reg_scaling

Unbalanced Sinkhorn with epslilon scaling [9][10]

ot.sliced_wasserstein_distance(X_s, X_t, a=None, b=None, n_projections=50, seed=None, log=False)[source]

Computes a Monte-Carlo approximation of the 2-Sliced Wasserstein distance

\[\mathcal{SWD}_2(\mu, \nu) = \underset{\theta \sim \mathcal{U}(\mathbb{S}^{d-1})}{\mathbb{E}}[\mathcal{W}_2^2(\theta_\# \mu, \theta_\# \nu)]^{\frac{1}{2}}\]

where :

  • \(\theta_\# \mu\) stands for the pushforwars of the projection \(\mathbb{R}^d \ni X \mapsto \langle \theta, X \rangle\)

Parameters
  • X_s (ndarray, shape (n_samples_a, dim)) – samples in the source domain

  • X_t (ndarray, shape (n_samples_b, dim)) – samples in the target domain

  • a (ndarray, shape (n_samples_a,), optional) – samples weights in the source domain

  • b (ndarray, shape (n_samples_b,), optional) – samples weights in the target domain

  • n_projections (int, optional) – Number of projections used for the Monte-Carlo approximation

  • seed (int or RandomState or None, optional) – Seed used for numpy random number generator

  • log (bool, optional) – if True, sliced_wasserstein_distance returns the projections used and their associated EMD.

Returns

  • cost (float) – Sliced Wasserstein Cost

  • log (dict, optional) – log dictionary return only if log==True in parameters

Examples

>>> n_samples_a = 20
>>> reg = 0.1
>>> X = np.random.normal(0., 1., (n_samples_a, 5))
>>> sliced_wasserstein_distance(X, X, seed=0)  
0.0

References

31

Bonneel, Nicolas, et al. “Sliced and radon wasserstein barycenters of measures.” Journal of Mathematical Imaging and Vision 51.1 (2015): 22-45

ot.tic()[source]

Python implementation of Matlab tic() function

ot.toc(message='Elapsed time : {} s')[source]

Python implementation of Matlab toc() function

ot.toq()[source]

Python implementation of Julia toc() function

ot.unif(n)[source]

return a uniform histogram of length n (simplex)

Parameters

n (int) – number of bins in the histogram

Returns

h – histogram of length n such that h_i=1/n for all i

Return type

np.array (n,)

ot.wasserstein_1d(x_a, x_b, a=None, b=None, p=1.0)[source]

Solves the p-Wasserstein distance problem between 1d measures and returns the distance

\[ \begin{align}\begin{aligned}\min_\gamma \left( \sum_i \sum_j \gamma_{ij} \|x_a[i] - x_b[j]\|^p \right)^{1/p}\\s.t. \gamma 1 = a, \gamma^T 1= b, \gamma\geq 0\end{aligned}\end{align} \]

where :

  • x_a and x_b are the samples

  • a and b are the sample weights

Uses the algorithm detailed in [1]_

Parameters
  • x_a ((ns,) or (ns, 1) ndarray, float64) – Source dirac locations (on the real line)

  • x_b ((nt,) or (ns, 1) ndarray, float64) – Target dirac locations (on the real line)

  • a ((ns,) ndarray, float64, optional) – Source histogram (default is uniform weight)

  • b ((nt,) ndarray, float64, optional) – Target histogram (default is uniform weight)

  • p (float, optional (default=1.0)) – The order of the p-Wasserstein distance to be computed

Returns

dist – p-Wasserstein distance

Return type

float

Examples

Simple example with obvious solution. The function wasserstein_1d accepts lists and performs automatic conversion to numpy arrays

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> x_a = [2., 0.]
>>> x_b = [0., 3.]
>>> ot.wasserstein_1d(x_a, x_b, a, b)
0.5
>>> ot.wasserstein_1d(x_a, x_b)
0.5

References

1

Peyré, G., & Cuturi, M. (2017). “Computational Optimal Transport”, 2018.

See also

ot.lp.emd_1d

EMD for 1d distributions