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

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’ 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

W ((n_hists) ndarray or float) – 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

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.bregman.sinkhorn_epsilon_scaling: Sinkhorn with epslilon scaling [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