Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimal-transport]

The tag has no usage guidance.

2
votes
1answer
25 views

Relative Entropy and the Wasserstein distance

Can anyone give an informative example of two distributions which have a low Wasserstein distance but high relative entropy (or the other way around)? I find the Wasserstein defined (for some $p$) as ...
0
votes
0answers
11 views

Construction of optimal map

I am not able to show the last step in the proof of the following Theorem: Suppose $X$ and $Y$ are Polish spaces, $\pi$ is a probability measure on $X \times Y$ and $\mu$ is a probability measure on ...
2
votes
1answer
24 views

Generalized Rockafellar theorem

I am trying to understand the proof of the following Theorem Let $X, Y$ be metric spaces and $c: X \times Y \to \mathbb{R}$ be a continuous and bounded function and let $\Gamma \subset X \times Y$ be ...
1
vote
1answer
22 views

Two basic questions in Wasserstein spaces

We denote by $P (\mathbb{R}^{d})$ the space of probability measures on $\mathbb{R}^{d}$ and for $p\geqslant 1$ the Wasserstein space by \begin{equation*} P^p (\mathbb{R}^{d}) = \{ \mu \in P(\mathbb{R}...
0
votes
0answers
15 views

Wasserstein distance of two flat triangles

Is there a way to compute the Wasserstein distance of two flat triangles that share a commen edge? That is, assume you have two triangles in $\mathbb{R}^2$ that share a commen edge. Further, assume ...
1
vote
2answers
36 views

Wasserstein attains its infimum

let $(\mathcal{X},d)$ be a Polish space. For $p\geq1$ let $\mathcal{P}_p(\mathcal{X})$ be the space of all Borel probability measures $\mu$ on $\mathcal{X}$ such that \begin{equation} \mathbb{E}_\mu\...
1
vote
1answer
22 views

value function of optimal transport

Let $X = Y = \mathbb{R}^d$ and let $\nu$ be a probability measure on $\mathbb{R}^d$. Consider the collection of probability measure $\pi$ on $X\times Y$ such that $\pi$ has $y$-marginal $\nu$: $$ \Pi(...
1
vote
0answers
24 views

Monge-Ampère equation and optimal transport

I'm a beginer in optimal transport, I'm looking for a reference about solving Monge-Ampère for discrete measure. And if you have any reference for beginners, it's cool! My background : Actually ...
0
votes
0answers
8 views

Degeneracy transportation problem finding least cell

Transportation problem My question is precisely this: why are we choosing four in this case? This is not the smallest value in the table. I know that we have to choose unallocated cells and that we ...
1
vote
0answers
14 views

Wasserstein distance between hyperplane and cube

Let $\mu$ be the uniform measure on the cube $Q = [-1,1]^n$, and $\nu$ be the uniform measure on the surface $$ V = \{(x_1,\dots,x_n)\in Q \mid \sum x_i = 0\}. $$ I am curious about Wasserstein ...
1
vote
0answers
13 views

Uniqueness of transport maps

Does anyone know a proof of the following measure theory fact? Let $\mu$ be a finite measure on $\mathbb{R}^n$ and $T_i:\mathbb{R}^n\to\mathbb{R}^n$, $i=1,2,3$, measurable functions. If \begin{...
0
votes
0answers
21 views

Upper or lower bound of Wasserstein-2 metric on Gaussian distribution

I am constructing an iterative algorithm in which the Wasserstein-2 distance metric for continuous Gaussian distributions is being used. I am trying to find a general upper or lower bound of the ...
1
vote
0answers
22 views

Question about Coupling of Measures

Let $\pi$ be a coupling of probability measures $\mu,\nu.$ For measurable sets $A,B$ we have $$ \pi(A\times B) \leq \mu(A) $$ and $$ \pi(A^c \times B^c) \leq \mu(A^c), $$ Therefore we have $$ \pi(A\...
0
votes
0answers
19 views

Existence of a Certain Transport Map

Let $(X,d)$ be a Polish space. Let $$ \mu = \sum_{k=1}^\infty a_n \delta_{x_n}, $$ where $x_n \in X, a_n \in [0,1]$ and $$ \sum_{k=1}^\infty a_n =1. $$ Let $$ \nu = \sum_{k=1}^N b_k \delta_{x_k}, $...
1
vote
1answer
19 views

Help on application of Marton's transportation method (Bucheron-Lugosi-Massart)

I was trying to apply Marton's transportation inequality in the following exercise from Bucheron, Lugosi, Massart's text on concentration inequalities: Exercise 8.1. Use Marton's transportation ...
5
votes
2answers
98 views

What is the fastest route to drop off weight when time is proportional to weight x distance?

You have a lorry at the starting point which is carrying all the parcels for the day. $$\rm Time\ taken = Total\ Lorry\ Weight \times Distance\ travelled $$ After visiting each zone you have to ...
3
votes
0answers
37 views

Characterization of Wasserstein convergence

Let $(X,d)$ be a complete metric space and define $$\mathcal{P}_2(X) := \{ \mu \text{ Borel probability measure} \mid \int_X d^2(x,x_0) d\mu(x) < \infty \text{ for some } x_0 \in X \}$$ endowed ...
0
votes
1answer
24 views

Name for Monge-Kantorovich transportation problem variant with unequal total mass

I'm interested in a variant of the transportation problem and cannot find a reference for the problem I'm thinking of. In the original Monge-Kantorovich problem about continuous transport, the total ...
1
vote
0answers
12 views

Semi-discrete optimal transport between mixture of Gaussians and their centers

I have a question about bounding the Wasserstein loss between a continuous Gaussian mixture and a discrete uniform distribution of its centers. In particular, let $P=\frac 1 k \sum_{i=1}^k \mathcal{N}(...
0
votes
1answer
42 views

Optimal transport with relaxed constraint on terminal distribution

I have read the topic on relaxing constraint on relaxing marginal constraints Optimal transport with relaxed constraint on marginals, where the constraint is expressed as the difference of initial and ...
1
vote
0answers
49 views

Kantorovich duality with pseudometric

The usual framework for the Kantorovich duality in optimal transport theory uses Polish spaces as ground spaces for the distributions that should be transported. Are there results available that ...
0
votes
0answers
158 views

Obtain an optimal solution for transportation problem

Consider Problem 8.1-1 I did (a) and (b). For (c), should I solve using 1.minimum cost method and then method of multipliers ? or 2.Vogel method and then method of multipliers ? Is there an ...
2
votes
1answer
25 views

Optimality of Kantorovich potentials for the squared distance

This question comes from Villani's book, Optimal Transport: Old and New. Consider the cost function $c(x, y) = |x - y|^2$ on $X \times Y$, where $X$ is the right half of the unit ball, and $Y$ is the ...
0
votes
1answer
147 views

One redundant equation in linear program?

Consider the general linear programming formulation of the transportation problem (see Table 8.6). Verify that the set of $(m+n)$ functional constraint equations $(m$ supply constraints and $n$ demand ...
0
votes
0answers
21 views

Wasserstein penalization for time dependent measures

I have time dependant measures, say $\mu: [0,T] \rightarrow \mathcal{M}(\Omega)$ and I'm looking to define a penalization in this space that would measure the amount of displacement in space through ...
1
vote
0answers
58 views

Wasserstein Distance with Translations

I am studying this book about Optimal Transport, and in Remark 2.19 it talks about translation in Variance, where it is stated that a nice property of Wasserstein Distances is the ability to factor ...
2
votes
1answer
25 views

Derivative of a function from real number space to Wasserstein space

I'm not really having a good background in math, so please correct me if I say something very vague or even wrong. Suppose a function $\rho=f(\theta):\mathbb{R}\to\mathcal{W}_p(\mathbb{R}^d)$. I ...
1
vote
0answers
25 views

construct optimal transport plan from a dual optimizer

Consider the Kantorovich formulation of optimal transport: $$ \inf_{\pi\in\Pi(\mu,\nu)} \int c(x,y)d\pi $$ whose dual problem is $$ \sup_{\phi} \int \phi(x)d\mu + \int \phi^c(y) d\nu. $$ Now, ...
0
votes
1answer
31 views

An intriguing duality gap for Wasserstein distance for Gaussian distributions

Let $P=N(a,\sigma^2 I)$ and $Q=N(b, \sigma^2 I)$ be two Gaussian distributions in $\mathbb{R}^d$. We know that the Wasserstein distance $P$ and $Q$ is defined as $$ W_2^2(P,Q) \triangleq \inf_{\pi \in ...
1
vote
0answers
149 views

Exercise 1.21 of Villani Topics in Optimal Transportation

I'm stuck on this exercise, can you please help me? Since the text is a bit long I attach here below the the screen of the text. Following the notation of the book, $\Pi(\mu,\nu)$ is the set of ...
2
votes
1answer
30 views

Realize a coupling in the target space via a measure on the source space

Consider two product measurable spaces $\left(X \times Y,\mathcal{X} \otimes \mathcal{Y}\right)$, $\left(X' \times Y',\mathcal{X'} \otimes \mathcal{Y'}\right)$ with the usual product sigma-algebra, ...
1
vote
1answer
40 views

Coupling via push-forward from a source space

Consider a measurable function $g$ mapping a probability space $\left(\Omega,\mathcal{F},\mu\right)$ to a product measurable space $\left(T,\mathcal{T}\right)$ with cartesian product $T = X \times Y$ ...
1
vote
0answers
75 views

Computing 1- or 2- Wasserstein distance between collections of point masses

Is either $W_1$ or $W_2$ (the Wasserstein distances) available in closed form when comparing two collections of point masses? To be specific, let $p = \sum_{i=1}^n \delta_{x_i}$ and $q = \sum_{j=1}^...
2
votes
1answer
79 views

optimization loss due to misperceived probability

Suppose $a$ is chosen to maximize the expected value of $u(a,x)$ under a probability measure of $x$. Image the true distribution is $P(x)$, but the optimization may be conducted under a misperceived ...
0
votes
0answers
190 views

Negative cost coefficients in Transportation problem

I have a minimum transportation cost supply demand matrix which looks like this , I dont know how to handle negative cost coefficients, since negative costs dont make any sense , should I just ignore ...
0
votes
0answers
106 views

Example of a Minimum Cost Capacitated Flow Problem

I am struggling to find an example with a solution for a Minimum Cost Capacitated Flow problem. My network is defined as a graph G = (V, E), where each edge has a capacity c(u, v) > 0, a flow f(u, v) ...
0
votes
0answers
38 views

KL divergence for symmetric Gaussian mixtures

I have two symmetric Gaussian mixtures $P$ and $Q$ such that $$ P= \frac 1 2 \mathcal{N}(\mu_1,I) + \frac 1 2 \mathcal{N}(-\mu_1,I) $$ and $$ Q= \frac 1 2 \mathcal{N}(\mu_2,I) + \frac 1 2 \mathcal{N}(-...
1
vote
1answer
29 views

What was wrong with this argument?

As one knows, we have the duality theorem for $W_2^2$: \begin{align} W_2^2(P,Q) = \inf_{\pi} \mathbb{E}_{\pi, X \sim P, Y\sim Q} |X-Y|^2 = \sup_{\phi,\psi \in C_b, \phi(x) + \psi(y)\leq (x-y)^2} \int ...
1
vote
2answers
90 views

Choquet's and Birkhoff's theorem for min-max discrete optimization problems

Some context first: A very standard linear problem (LP) is to find $$\inf_P \left( \sum_{1 \leq i,j \leq n} P_{ij} C_{ij}^p \right)^\frac{1}{p}$$ under the constraint that $P$ is doubly stochastic (...
3
votes
1answer
82 views

Measurable selection of geodesics

Let $(X, d)$ be Polish and geodesic (i.e. for all $x,y \in X$ there exists a so called constant speed geodesic curve $\gamma :[0,1] \rightarrow X$, s.t. $$\gamma (0) = x, \gamma (1) = y$$ and $$d(\...
6
votes
1answer
233 views

The Lebesgue measure as energy minimizer?

Assume that $K:\mathbb{R}_{\geq0} \to\mathbb{R}_{\geq0}$ is a decreasing function. If $\nu$ is a probability measure on the unit circle, define its energy $$ \mathcal{E}(\nu):=\int K(|x-y|)d\nu(x)d\nu(...
1
vote
1answer
91 views

Monge and Kantorovich problem in optimal transport

It is well-known that in optimal transport, Kantorovich problem is a relaxation of the Monge problem, which always admits a solution. Let's write $$ M(\mu,\nu)=\inf_{T: T_\#\mu=\nu} \int c(x,T(x))d\mu ...
4
votes
0answers
197 views

Closed forms solutions to Optimal Transport/Wasserstein Distance

This paper https://math.nyu.edu/faculty/tabak/publications/M107495.pdf, mentions that: "closed-form solutions of the multidimensional optimal transport problems are relatively rare, a number of ...
0
votes
1answer
39 views

Lipschitz extension of affine function to whole space

Consider the metric linear space $(R^n, d)$. My question is whether for every $x_1,x_2 \in R^n$ there exists an affine function $\alpha : R^n \to R$ satisfying $\alpha(x_1) - \alpha(x_2) = d(x_1, ...
1
vote
0answers
27 views

density in Wasserstein spaces

I am wondering whether the following result is true: Let $\mathcal W_p(\mathbb R^d)$ be the Wasserstein space of order $p$ and let $\eta$ and $\gamma$ be two probability measures in $\mathcal W_p(\...
1
vote
1answer
58 views

About the square root in the geodesic distance

$\newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\R}{\mathbb R} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\C}{\mathbb C} \newcommand{\Pb}{\mathbb P} \newcommand{\D}{\mathcal{ ...
3
votes
0answers
173 views

Completeness of Wasserstein space

In this MO question it is said that: On a complete, non necessarily separable metric space $E$, the set $P_r(E)$ of all Radon probability measures with the Wasserstein-Kantorovich metric $W_d$ is ...
2
votes
1answer
169 views

Proof that the optimal transport cost is lower semicontinuous

In Chapter 6 of Villani's Optimal Transport: Old and New, it is stated that ... the Wasserstein distance is lower semicontinuous on $P(\mathcal{X})$ (just like the optimal transport cost $C$, for ...
5
votes
1answer
103 views

Name for a cardinality-constrained transportation problem variant

The transportation problem is a well-studied problem in operations research. Given sources $i\in\{1, \ldots, n\}$ and destinations $j\in\{1, \ldots, m\}$, we seek to minimize the total cost of ...
2
votes
1answer
71 views

Proof that the set of transference plans is closed in the weak topology

I am reading Villani's Optimal transport: Old and new. Theorem 4.1 concerns the existence of an optimal coupling between any two Polish probability spaces $(\mathcal{X}, \mu)$ and $(\mathcal{Y}, \nu)$...