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.

0
votes
1answer
18 views

Set of transport plans is closed in the weak topology

Suppose $X$ and $Y$ are Polish spaces and $\mu$ and $\nu$ are probability measures respectively on $X$ and $Y$. Define $$ \Gamma(\mu, \nu) = \{ \pi \in \mathcal{P}(X \times Y) \mid \pi(A \times Y) = \...
0
votes
0answers
12 views

Lp Wasserstein Distance for two distributions which have equivalent partial marginals

Consider two distributions $p(x_1,x_2)$ and $q(x_1,x_2)$ which have equivalent partial marginals, say $p(x_1)=q(x_1)$. I am wondering if there is any relationship between two Wasserstein ditances $W_{...
0
votes
0answers
10 views

Large Deviation, Optimal Transport and Machine Learning Reference

I am looking for references (books/sites/articles) on the following three subjects: Large Deviation, Optimal Transport and Machine Learning References. I would like works which involve any of them ...
2
votes
0answers
16 views

Stability of optimal transference mappings (Exercise 2.17 in Villani's Topics in Optimal Transportaiton)

I'm really stuck on the first part of this exercise. I've tried to type it up in a fashion that is as self-contained as possible, but some background in optimal transport is likely required to read ...
0
votes
0answers
10 views

Example of curve of probabilities in Wasserstein space

I'm trying to read chapter 8 of the book on gradient flows by Ambrosio-Gigli-Savaré. In this context, I think I don't really understand the definition of a curve being absolutely continuous with ...
1
vote
0answers
12 views

Euler-Lagrange Equation for Kantorovich Dual Problem

Given two probability measures $\mu$ and $\nu$, the Kantorovich Dual problem for quadratic cost is to $$ \text{minimize} \quad \int \phi(x)d\mu + \int \psi(y)d\nu $$ over pairs $(\phi,\psi)\in L^1(d\...
3
votes
1answer
28 views

Problem on the proof of Moreau-Yosida regularization Theorem

I do not understand some steps of the proof of the following theorem Theorem (Moreau-Yosida regularization). Let $X$ be a metric space, $f:X\longrightarrow\mathbb{R}\cup\{+\infty\}$ be a function ...
2
votes
1answer
75 views

Multivariate Kolmogorov distance bounded by Wasserstein distance

I'm trying to find a bound for the multivariate Kolmogorov distance in terms of the Wasserstein distance. Denoting by $F$ and $G$ two cumulative distribution functions (cdf) on $\mathbb{R}^n$ the ...
0
votes
0answers
16 views

Wasserstein distance between centered Gaussian mixtures

We use $\mathcal{W}_2(\cdot, \cdot)$ to denote the quadratic Wasserstien distance as defined here. Now, let $X,Y = \mathcal{N}(0,1)$ be two standard normal random variables and for $ a \in[0,1]$ let $...
0
votes
0answers
23 views

Wassertein and symmetry

So here's a scenario: I have points $(\mu_1^j,\mu_2^j)$ and I associated them the following distribution $$\rho_j=1/2\delta_{\mu_1^j}+1/2\delta_{\mu_2^j}$$ These have symmetry (exchanging $\mu_1^j$ ...
2
votes
1answer
47 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
14 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
32 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
33 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
18 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
46 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
26 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
36 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
12 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 ...
2
votes
0answers
22 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
18 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
43 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
28 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
23 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
21 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
102 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
54 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
28 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
14 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
48 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
53 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
335 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
27 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
153 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
22 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
68 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
28 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
32 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
35 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 ...
3
votes
1answer
173 views

Exercise 1.21 of Villani Topics in Optimal Transportation

I'm stuck on this exercise, can you please help me? 1.2.2. Transshipment. The Kantorovich-Rubinstein theorem implies that the total cost only depends on the difference $\mu-\nu$ . Thus, when the ...
2
votes
1answer
32 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
49 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$ ...
2
votes
0answers
98 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
80 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
258 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
137 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
43 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
30 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
97 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
92 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(\...