Stack Exchange Network

Stack Exchange network consists of 174 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
0answers
20 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
8 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
18 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
1answer
73 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
30 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
0answers
11 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 ...
0
votes
0answers
8 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
33 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
46 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
56 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
19 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
134 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
20 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
39 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
20 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
23 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
141 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
29 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
35 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
59 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
76 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
107 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
79 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
34 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
80 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
77 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
229 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(...
0
votes
1answer
66 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
150 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
32 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
23 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
52 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
145 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
154 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
98 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 ...
1
vote
1answer
63 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)$...
1
vote
0answers
104 views

Optimal transport for point sets

I have been examining the literature on optimal transport, and typically it is introduced as an arbitrary number of probability measures $\mu_0, \mu_1, \cdots$ on an n-dimensional manifold $N$. The ...
5
votes
1answer
120 views

Derivation of the weak transport equation

Let $\rho$ be a density on some space $M$. For all practical purposes some subspace of $\mathbb R^n$. Let $v$ be a smooth vector field with flow $\Phi_t$. The transport equation, as far as I ...
0
votes
1answer
73 views

question regarding disintegration

Let $\gamma$ be a positive measure on $(\mathbb R^2)^n$ and define a measure $\omega=\sum_{i=1}^n proj^i_\#\gamma$ on $\mathbb R^2$. Notice that $\omega= \int_{p \in(\mathbb R\times\mathbb R)^n} \...
1
vote
0answers
21 views

How can we show that $H_i$ is convex and lower semicontinuous? (Paper by Agueh, Carlier)

I am reading the following paper and was wondering how to show that $H(f) = -\int_{\mathbb{R}^d}\inf_{y \in \mathbb{R}^d}\{\frac{\lambda}{2}|x-y|^2- f(y)\} \text{d}\nu(x)$ is convex and lower ...
3
votes
0answers
116 views

Question about transportation-entropy inequality (From Villani's book: Optimal Transport, Old and New)

I was reading Villani's book: Optimal Transportation, Old and New. From page 80-83, he introduced some results about dual formulation of transport inequality. Assume $C(\mu,\nu)$ is the optimal ...
1
vote
0answers
58 views

Gauss map and Minkowski functionals

Let $K$ be a convex body and let $\| \cdot \|_{K}$ be the correspoding Minkowski functional $$\| x \|_{K} = \inf\{\lambda > 0 : x \in \lambda K \}$$ Let us consider the following map $f: K \...
1
vote
0answers
34 views

The graph associated with transportation tableau is a spanning tree

The transportation problem in linear programming is solved by a kind of simplex method in which we use a transportation tableau which corresponds to a basic solution. (See page 5 of the given link) ...
3
votes
1answer
346 views

Is the expectation value Lipschitz for the Wasserstein metric?

Consider the space $M$ of Borel measures on the real unit interval $[0,1]$, equipped with the 1-Wasserstein metric $d_W$ (or "Earth mover's distance"). The expected value is then a map $M\to [0,1]$ ...
3
votes
1answer
581 views

Wasserstein distances metrize weak convergence

Let $(X,d)$ be a metric space. Let $P(X)$ denote the space of probability measures on $X$. The (first) Wasserstein distance is a distance on $P(X)$ given by: $$ d_W(p,q):= \inf_{m\in\Gamma(p,q)} \int_{...
2
votes
0answers
70 views

Kantorovich translocation of masses 1942 paper

I would appreciate help understanding Kantorovich's 1942 paper on translocation on masses. The English translation can be found here: http://web.eecs.umich.edu/~pettie/matching/Kantorovitch-...
2
votes
1answer
54 views

Kantorovich-Rubinstein in case of quasi-metric

Consider the classical Kantorovich-Rubinstein Duality Theorem, \begin{align*} \inf_{\{\pi \mid \pi|_{X\times pt}=\mu, \pi|_{pt\times X}=\nu \}} \int_{X^2} d(x,y)\pi(x,y) = \sup_{l\in Lip_1(X)} \int_X ...
0
votes
1answer
160 views

How to show, that the set of density functions with compact support is compact wrt. Wasserstein Metric?

In an Optimal Transport Math project we are currently working on we want to show that the Infimum of a Functional $\inf_{~f\in\overline{\mathcal{P}_{ac,2}(\Omega)}}H[f]$ is reached, where $\mathcal{P}...