ExactOptimalTransport.jl

emd(μ, ν, C, optimizer)

Compute the optimal transport plan γ for the Monge-Kantorovich problem with source histogram μ, target histogram ν, and cost matrix C of size (length(μ), length(ν)) which solves

\[\inf_{γ ∈ Π(μ, ν)} \langle γ, C \rangle.\]

The corresponding linear programming problem is solved with the user-provided optimizer. Possible choices are Tulip.Optimizer() and Clp.Optimizer() in the Tulip and Clp packages, respectively.

emd2(μ, ν, C, optimizer; plan=nothing)

Compute the optimal transport cost (a scalar) for the Monge-Kantorovich problem with source histogram μ, target histogram ν, and cost matrix C of size (length(μ), length(ν)) which is given by

\[\inf_{γ ∈ Π(μ, ν)} \langle γ, C \rangle.\]

The corresponding linear programming problem is solved with the user-provided optimizer. Possible choices are Tulip.Optimizer() and Clp.Optimizer() in the Tulip and Clp packages, respectively.

A pre-computed optimal transport plan may be provided.

ot_plan(c, μ, ν; kwargs...)

Compute the optimal transport plan for the Monge-Kantorovich problem with source and target marginals μ and ν and cost c.

The optimal transport plan solves

\[\inf_{\gamma \in \Pi(\mu, \nu)} \int c(x, y) \, \mathrm{d}\gamma(x, y)\]

where $\Pi(\mu, \nu)$ denotes the couplings of $\mu$ and $\nu$.

See also: ot_cost

ot_plan(c, μ::ContinuousUnivariateDistribution, ν::UnivariateDistribution)

Compute the optimal transport plan for the Monge-Kantorovich problem with univariate distributions μ and ν as source and target marginals and cost function c of the form $c(x, y) = h(|x - y|)$ where $h$ is a convex function.

In this setting, the optimal transport plan is the Monge map

\[T = F_\nu^{-1} \circ F_\mu\]

where $F_\mu$ is the cumulative distribution function of μ and $F_\nu^{-1}$ is the quantile function of ν.

See also: ot_cost, emd

ot_plan(c, μ::DiscreteNonParametric, ν::DiscreteNonParametric)

Compute the optimal transport cost for the Monge-Kantorovich problem with univariate discrete distributions μ and ν as source and target marginals and cost function c of the form $c(x, y) = h(|x - y|)$ where $h$ is a convex function.

In this setting, the optimal transport plan can be computed analytically. It is returned as a sparse matrix.

See also: ot_cost, emd

ot_plan(::SqEuclidean, μ::Normal, ν::Normal)

Compute the optimal transport plan for the Monge-Kantorovich problem with normal distributions μ and ν as source and target marginals and cost function $c(x, y) = \|x - y\|_2^2$.

See also: ot_cost, emd

ot_plan(::SqEuclidean, μ::MvNormal, ν::MvNormal)

Compute the optimal transport plan for the Monge-Kantorovich problem with multivariate normal distributions μ and ν as source and target marginals and cost function $c(x, y) = \|x - y\|_2^2$.

In this setting, for $\mu = \mathcal{N}(m_\mu, \Sigma_\mu)$ and $\nu = \mathcal{N}(m_\nu, \Sigma_\nu)$, the optimal transport plan is the Monge map

\[T \colon x \mapsto m_\nu + \Sigma_\mu^{-1/2} {\big(\Sigma_\mu^{1/2} \Sigma_\nu \Sigma_\mu^{1/2}\big)}^{1/2}\Sigma_\mu^{-1/2} (x - m_\mu).\]

See also: ot_cost, emd

ot_cost(c, μ, ν; kwargs...)

Compute the optimal transport cost for the Monge-Kantorovich problem with source and target marginals μ and ν and cost c.

The optimal transport cost is the scalar value

\[\inf_{\gamma \in \Pi(\mu, \nu)} \int c(x, y) \, \mathrm{d}\gamma(x, y)\]

where $\Pi(\mu, \nu)$ denotes the couplings of $\mu$ and $\nu$.

See also: ot_plan

ot_cost(
    c, μ::ContinuousUnivariateDistribution, ν::UnivariateDistribution; plan=nothing
)

Compute the optimal transport cost for the Monge-Kantorovich problem with univariate distributions μ and ν as source and target marginals and cost function c of the form $c(x, y) = h(|x - y|)$ where $h$ is a convex function.

In this setting, the optimal transport cost can be computed as

\[\int_0^1 c(F_\mu^{-1}(x), F_\nu^{-1}(x)) \mathrm{d}x\]

where $F_\mu^{-1}$ and $F_\nu^{-1}$ are the quantile functions of μ and ν, respectively.

A pre-computed optimal transport plan may be provided.

See also: ot_plan, emd2

ot_cost(
    c, μ::DiscreteNonParametric, ν::DiscreteNonParametric; plan=nothing
)

Compute the optimal transport cost for the Monge-Kantorovich problem with discrete univariate distributions μ and ν as source and target marginals and cost function c of the form $c(x, y) = h(|x - y|)$ where $h$ is a convex function.

In this setting, the optimal transport cost can be computed analytically.

A pre-computed optimal transport plan may be provided.

See also: ot_plan, emd2

ot_cost(::SqEuclidean, μ::Normal, ν::Normal)

Compute the squared 2-Wasserstein distance between univariate normal distributions μ and ν as source and target marginals.

See also: ot_plan, emd2

ot_cost(::SqEuclidean, μ::MvNormal, ν::MvNormal)

Compute the squared 2-Wasserstein distance between normal distributions μ and ν as source and target marginals.

In this setting, the optimal transport cost can be computed as

\[W_2^2(\mu, \nu) = \|m_\mu - m_\nu \|^2 + \mathcal{B}(\Sigma_\mu, \Sigma_\nu)^2,\]

where $\mu = \mathcal{N}(m_\mu, \Sigma_\mu)$, $\nu = \mathcal{N}(m_\nu, \Sigma_\nu)$, and $\mathcal{B}$ is the Bures metric.

See also: ot_plan, emd2

wasserstein(μ, ν; metric=Euclidean(), p=Val(1), kwargs...)

Compute the p-Wasserstein distance with respect to the metric between measures μ and ν.

Order p can be provided as a scalar of type Real or as a parameter of a value type Val(p). For certain combinations of metric and p, such as metric=Euclidean() and p=Val(2), the computations are more efficient if p is specified as a value type. The remaining keyword arguments are forwarded to ot_cost.

See also: squared2wasserstein, ot_cost

squared2wasserstein(μ, ν; metric=Euclidean(), kwargs...)

Compute the squared 2-Wasserstein distance with respect to the metric between measures μ and ν.

The remaining keyword arguments are forwarded to ot_cost.

See also: wasserstein, ot_cost

discretemeasure(
    support::AbstractVector,
    probs::AbstractVector{<:Real}=FillArrays.Fill(inv(length(support)), length(support)),
)

Construct a finite discrete probability measure with support and corresponding probabilities. If the probability vector argument is not passed, then equal probability is assigned to each entry in the support.

Examples

using KernelFunctions
# rows correspond to samples
μ = discretemeasure(RowVecs(rand(7,3)), normalize!(rand(10),1))

# columns correspond to samples, each with equal probability
ν = discretemeasure(ColVecs(rand(3,12)))