Questions tagged [optimal-transport]

For questions related to the theory, applications, and computational aspects of optimal transport and related topics such as the Wasserstein (and other transportation cost) distances, the Monge-Ampere equation, metric gradient flows, martingale optimal transport, and optimal matching.

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Optimal objective of Static Schrodinger Bridge

I refer to notes about entropy-regularized optimal transport, at https://www.math.columbia.edu/~mnutz/docs/EOT_lecture_notes.pdf In Theorem 3.2, it says that the Schrodinger potentials achieve the ...
user avatar
0 votes
0 answers
22 views

Derivative of Kantorovic Potential wrt to Measure

The Kantorovich Dual of the 1-Wasserstein distance $W_1(p,q)$ between two densities $p(x), q(x)$ is given by $$W_1(p,q) = \sup_{|f|_L\leq 1} \int f(x)(p(x)-q(x))dx$$ with $|f|_L$ denoting the ...
user avatar
-1 votes
0 answers
15 views

Computational optimal transport [closed]

Let's say I have two piles of sand with the same amount of grains, but a different shape. Is there a way to "optimally transport" pile A to B in N steps by moving a handful of grains each ...
user avatar
0 votes
0 answers
31 views

Is the composition of two optimal transport maps still optimal (under some assumptions)?

Consider three absolutely continuous probability measures $\mu$, $u$, and $\nu$ on $\mathbb R^d$ ($d \geq 1$), all of which have finite second moments. A transport map from $\mu$ to $\nu$ is called ...
user avatar
  • 13
1 vote
1 answer
29 views

Embedding $X \ni x \mapsto \delta_x \in P_2(X)$ is totally convex

I am looking for a reference to a proof of the following result: Let $X$ be a compact, connected, smooth Riemannian manifold. Then, the embedding $$X \ni x \mapsto \delta_x \in P_2(X) $$ has totally ...
user avatar
2 votes
1 answer
71 views

What functions are continuous in the Wasserstein metric?

Consider the space $L_p(\mathbb{R})$ of probability measures on $\mathbb{R}$ with $p$th moments. This set is a metric space under the $p$-Wasserstein metric $$W_p(\mu,\nu)^p=\inf_{Z=(X,Y):X\sim\mu,Y\...
user avatar
-1 votes
1 answer
35 views

Construct the $c$-transform $(\overline \varphi, \overline \psi)$ of $(\varphi, \psi)$

Disclaimer This thread is meant to record. See: SE blog: Answer own Question and MSE meta: Answer own Question. Anyway, it is written as problem. Have fun! :) Let $X,Y$ be Polish spaces and $c:X \...
user avatar
  • 10.4k
0 votes
1 answer
19 views

If $c_n \nearrow c$ then $\lim_n \inf_{\pi \in \Pi(\mu, \nu)} \int c_n d\pi = \inf_{\pi \in \Pi(\mu, \nu)} \int c d\pi$

Disclaimer This thread is meant to record. See: SE blog: Answer own Question and MSE meta: Answer own Question. Anyway, it is written as problem. Have fun! :) Let $X,Y$ be Polish spaces and $c:X \...
user avatar
  • 10.4k
0 votes
1 answer
27 views

The projection of n-joint distribution onto 2-joint distribution

Let $P$ be a probability distribution on the product of Polish spaces $X_1\times \cdots \times X_N$. In particular, $X_N=X_j$. Suppose the marginal distribution of $P$ on $(X_i)$ are $(\mu_i)$, where $...
user avatar
0 votes
1 answer
33 views

Question on Kantorovich-Rubinstein Duality proof

I am currently working on understanding the Kantorovich-Rubinstein duality and Wassertein loss. The following part of these class notes: Collecting the terms algebraically we can rewrite the ...
user avatar
2 votes
1 answer
113 views

A proof of Kantorovich duality

Disclaimer This thread is meant to record. See: SE blog: Answer own Question and MSE meta: Answer own Question. Anyway, it is written as problem. Have fun! :) Let $X$ and $Y$ be Polish spaces. Let $P(...
user avatar
  • 10.4k
1 vote
0 answers
18 views

Topology on the set of transport maps

I have a question about the following: Given two Polish spaces $X$ and $Y$ with probability measures $\mu$ and $\nu$ defined on their Borel-$\sigma$-algebras, respectively. Why is there no possibility ...
user avatar
0 votes
0 answers
8 views

Using the monotone class argument to prove that the set of transport plans is closed in the weak topology

i'm having some problem understanding the first answer given to the following question: Proof that the set of transference plans is closed in the weak topology. In particular i can't prove the second ...
user avatar
0 votes
1 answer
22 views

Let $X,Y$ be Polish spaces and $\mu, \nu$ Borel probability measures on $X,Y$. Then the coupling $\Pi(\mu, \nu)$ is uniformly tight and weak* closed

I'm trying to prove this result in Optimal Transport. Could you verify if my attempt is fine? Let $X,Y$ be Polish spaces and $\mu, \nu$ Borel probability measures on $X,Y$ respectively. Let $\Pi(\mu, ...
user avatar
  • 1,437
0 votes
0 answers
49 views

Calculating the limit of a Wasserstein distance of two SDE's

I am trying to prove that: $\lim_{t \to \infty} W_2(\mu_t, \nu_t) = 0 $ where we have that $\mu_t = Law(X_t)$ and $\nu_t = Law(Z_t)$ with $$dX_t = -h(X_t)dt + \sqrt(\frac{2}{\beta})dB_t$$ $$dZ_t = -h(...
user avatar
0 votes
1 answer
76 views

Existence of joint optimal coupling

Given probability distributions $(\mu_1, \mu_2,\dots,\mu_n)$ on a sufficiently nice space $X$, does there always exist a random vector $(X_1,X_2\dots,X_n)$ such that any pair $(X_i,X_j)$ is an optimal ...
user avatar
  • 1,077
0 votes
0 answers
24 views

Continuity of Parabolic Evolution Equation

Let $\Omega\subset \mathbb{R}^d$ be a compact set with smooth boundary and $V$ be a (strongly) convex, smooth function. For the equation $$ \partial_t\rho_t = \nabla\cdot(\rho_t\nabla(\log\rho_t + V)) ...
user avatar
0 votes
0 answers
23 views

Optimal Transport and Domain Adapation

I'm reading Optimal Transport for Domain Adaptation as seen here: https://arxiv.org/abs/1507.00504 We assume that we have source domain $\Omega_S$ with variables $X^s$ and labels $Y^s$, and target ...
user avatar
  • 1,352
1 vote
0 answers
60 views

2-Wasserstein barycenter of uniform distribution on ellipsoid

Let $A$ be a positive-definite symmetric matrix. Consider the ellipsoid $E = \{ x \in \mathbb{R}^n \colon <x A^{-1} x> \leq 1 \}$. Now consider uniform distribution $\mu_1, \ldots, \mu_n$ on $...
user avatar
2 votes
0 answers
37 views

Optimal transport map between Lebesgue and Borel measures

Let $\mu$ be the Lebesgue measure on $[0, 1]$ and $\nu$ be the Borel measure defined on $[0, 1]$ by $$\int_{[0, 1]} f(y) \nu(dy) = (1 - \alpha) \int_{0}^{1} f(y) dy + \alpha f(1) ~~~~~ \forall f \in \...
user avatar
2 votes
1 answer
45 views

Optimal Transport and Entropic Regularization

We are working with discrete optimal transport. Let $P$ be a matrix and let $H(P) =- \sum_{i,j} P_{i,j} (\log(P_{i,j})-1)$. Let $C$ be the cost matrix. And $\langle C,P\rangle$ the Frobenius inner ...
user avatar
  • 1,352
3 votes
1 answer
99 views

Comparison between $L^1$ Wasserstein distance and total variation distance

Wasserstein$-k$ distance between two probability measures $\mu,\nu$ on $\mathbb{R}^d$ is defined as: $$W_k(\mu,\nu)=\left(\inf_{(X,Y)\in\mathcal{C}(\mu,\nu)}\mathbb{E}\left[\|X-Y \|^k \right]\right)^{...
user avatar
  • 3,146
1 vote
0 answers
42 views

Compactness in Kantorovich Duality Problem

I've been following along in https://lchizat.github.io/files2020ot/lecture1.pdf to learn about optimal transport theory and ran into some confusion in Chapter 4 "The dual problem"... Let $X,...
user avatar
  • 5,491
1 vote
0 answers
25 views

Optimal transport with 0-1 cost: some reference

I have started to study optimal transport, and it stuck me with the wealth of applications it opens up. In particular, I have been reading Villani's book Lecture Notes on Optimal Transport. There, in ...
user avatar
1 vote
0 answers
89 views

Closed form of Wasserstein distance in one dimension

On page 8 of this paper, it says that there is a closed form of 1-Wasserstein distance on $\mathbb{R}$: for any r.v.s $X,Y$ with CDF $F_X,F_Y$, we have $$W_1(X,Y)=\int|F_X(t)-F_Y(t)|dt$$ Why is this ...
user avatar
  • 957
1 vote
1 answer
32 views

Extension of Kantorovich-Rubinstein inequality.

Let $(\mathcal{X}, \Sigma)$ be a Polish metric space, endowed with the Borel $\sigma$-algebra. Let $\mathscr P$ be the space of probability measures on $\mathcal X$ and $\mathscr P^1$ be defined as $$\...
user avatar
  • 2,810
0 votes
0 answers
17 views

More examples for non-existent Monge maps

As stated very often, the Monge-Problem in Optimal Transport does not always admit a solution, for example when the start distribution $\mu$ is Dirac delta but the target distribution $\nu$ is not, ...
user avatar
  • 1,255
2 votes
1 answer
78 views

Pushforward of a measure under a given flow

I am reading a paper on the generalization of Caffarelli's contraction theorem. I came across following statements that is stated as obvious but I am not able to prove it. Let $V:\mathbb{R}^n\to \...
user avatar
  • 2,868
0 votes
0 answers
19 views

Estimate the smallest trace value among permutations of a random matrix

For a random matrix $X \in \mathbb{R}^{n\times n}$ where all elements follow normal distribution $X_{i,j}\sim \mathcal{N}(0,\sigma^2)$. Is there any way to approximate the following quantity? \begin{...
user avatar
  • 1
0 votes
0 answers
27 views

Transshipment problem with unbalanced demand and supply

Let's say we have: Two supply points - Houston and Dalas, which produce 160 and 200 products. Two transshipment points - Chicago and Los Angeles Two demand points - San Francisco and New York, which ...
user avatar
2 votes
0 answers
21 views

Sufficient condition for convex conjugates (does one imply the other?)

We say $(f_1,f_2,\cdots,f_N)$ a convex conjugate if for any $i=1,2,\cdots,N$ and any $x_i\in\Bbb R^d$, we have: $$f_i(x_i)=\sup\left\{\sum_{k=1}^{N}\sum_{j=k+1}^N x_k x_j - \sum_{j=1,j\neq i}^N f_j(...
user avatar
4 votes
1 answer
122 views

Maximiser of $W_1(\mu, \nu)$ can be changed outside of $\text{conv}(\text{supp}(\mu) \cap \text{supp}(\nu))$ (under additional assumptions)

Let $(X, \| \cdot \|)$ be a reflexive Banach space and $\mathbb{P}_n$, $\mathbb{P}_r$ be measures on $X$. Let the support of $\mathbb{P}_r$, $M := \text{supp}(\mathbb{P}_r)$ be a weakly compact set ...
user avatar
  • 4,281
0 votes
0 answers
42 views

how to build mathematic formulation for time violation?

I build a mathematical model to find a multi-objective model for the vehicle platooning problem. I am using the Gurobi optimization tool to build a mathematical model. The problem I am facing: Create ...
user avatar
1 vote
0 answers
29 views

Optimal transport on product spaces

Suppose to have an optimal transportation problem on the product of two Polish spaces $(X,d_X),(Y,d_Y)$ with cost on $Z:=X\times Y$ that is $c=\big(d_X^2-d_Y^2\big)^p$, where $p\in(0,1)$, i.e. you ...
user avatar
0 votes
0 answers
32 views

unique optimal plan in $\Gamma_o(\gamma,\nu)$?

Let $\gamma\in \mathcal{P}(X^2)$ (set of probability measures on $X^2$) and $\mu:=\pi^1_{\#}\gamma$ (first marginal of $\gamma$). Define $$\Gamma_o(\gamma,\nu):=\left\{\eta\in\mathcal{P}(X^3):(\pi^1,\...
user avatar
  • 3,848
0 votes
0 answers
33 views

Literature about the "opposite version" of the optimal transport

Is there any literature about a sort of "opposite version" of optimal transportation? Let me clarify: suppose to have a compact Polish space $(X,d)$, two probability measures $\mu,\nu$ and ...
user avatar
2 votes
0 answers
72 views

Energy Distance between Multivariate Gaussian Distributions

The square of energy Distance between CDFs $F$ and $G$, of $X$ and $Y$ resp., is defined here as $$d^2(F, G) = E||X-Y|| - E||X-X'|| - E||Y-Y'||$$ where $(X, X')$ and $(Y, Y')$ are IID pairs. I am ...
user avatar
1 vote
0 answers
42 views

How to prove the limit of minimizing sequence of measures is again absolutely continuous(w.r.t. Lebesgue) in the minimizing movement scheme?

I am considering the minimizing movement scheme related to the gradient of entropy functional in 2-Wasserstein space. The problem is to minimize the following functional for each fixed $\eta$ which is ...
user avatar
  • 957
0 votes
0 answers
27 views

Existence of minimizing point in the domain

Let $\Omega$ and $\Omega^*$ be bounded domains in $\mathbb{R}^n$. Let $c$ be a $C^4$ smooth function defined on $\mathbb{R}^n\times\mathbb{R}^n$. Let $u$ and $v$ be continuous functions in $\mathbb{R}^...
user avatar
1 vote
0 answers
55 views

Change of variables - Wasserstein distance

My question is how exactly the change of variable formula is applied in the second row of the equation?
user avatar
  • 1,255
5 votes
0 answers
101 views

The composition of optimal transport maps is no longer an optimal transport map

Let $X,Y,Z$ be metric spaces. Let $\mu,\nu,\omega$ be the probability measures on $X,Y,Z$, respectively. Moreover, assume all three measures vanish on small sets. Assume $T:X\to Y$ is the optimal ...
user avatar
0 votes
0 answers
19 views

Geometric interpretation of barycenter in Wasserstein-2 space

Given $\mathcal{X} \subset \mathbb{R}^d$. Let $\mu_k=\frac{1}{n}\sum_{i=1}^n x_{ki}$ for $k=1,\cdots, K$ be probability measures on $\mathcal{X}$. The Wasserstein-2 barycenter $\mu_1,\cdots, \mu_K$ is ...
user avatar
0 votes
1 answer
53 views

Composition of two transport maps and pushforward operator

Given two absolutely continuous probability measures $\mu,\sigma \in \mathcal P_2(\mathbb R^n)$ and two maps $T_1, T_2$ such that $$(T_1 \circ T_2)_\#\sigma =\mu$$ where $(\cdot)_{\#}$ denotes the ...
user avatar
  • 1,255
0 votes
1 answer
48 views

Equivalence Monge problem and Kantorovich problem in discrete spaces

In Thorpe's "Introduction to Optimal Transport" on page 18 in Theorem 2.7. we have that: $$ \sum_{i=1}^nc(x_{i},T(x_{i}))=\sum_{ij}c_{ij} \pi_{ij} \geq \sum_{ij}c_{ij} \pi^\dagger_{ij}=\sum_{...
user avatar
  • 551
1 vote
0 answers
18 views

Stability of transport maps implies continuity

In Villani's Optimal transport boo, it states the stability of transport maps: I have also read somewhere that this implies continuity. Intuitively, that makes sense to me, since as much as I ...
user avatar
  • 1,255
1 vote
0 answers
44 views

Transportation probem

The so-called transportation problem in mathematics asks about an optimal way to match demand and supply. Assume we have $m$ suppliers and $n$ factories demanding these supplies. There exists a cost $...
user avatar
  • 31
0 votes
0 answers
15 views

Proof in WASP: Scalable Bayes via barycenters of subset posteriors

In the paper WASP: Scalable Bayes via barycenters of subset posteriors see supplements via the link, the author claims that the barycenter of subset posterior converges to the $\delta_{\theta_0}$, ...
user avatar
1 vote
0 answers
46 views

Cost function requirements for Monge-Kantorovich existence and uniqueness

Let $\mu$ and $\nu$ be measures on Radon spaces $X$ and $Y$, respectively. The Monge-Kantorovich problem is stated as $$ \inf_{\gamma \in \Gamma(\mu,\nu)} \int_{X\times Y} c(x,y) d\gamma(x,y)$$ where $...
user avatar
  • 1,424
0 votes
0 answers
29 views

Partial order on matrix

In Barycenters in the Wasserstein space https://hal.archives-ouvertes.fr/hal-00637399/document section 6.3 The gaussian case Theorem 6.1, the authors used the order on the matrix ring by claiming the ...
user avatar
5 votes
0 answers
222 views

Understanding the velocity field in the Benamou–Brenier formulation

Disclaimer: theoretical physicists here! I apologize in advance for some sloppy terminology. I recently found an interest in optimal transport theory for some potential application to my research ...
user avatar
  • 51

1
2 3 4 5
7