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.
368
questions
0
votes
0
answers
19
views
Equivalent condition on marginals
Let $\mu$ be a probability measure on $X$ (compact), $v$ a probability measure on $Y$ (compact), and let $\gamma$ be a probability measure on $X \times Y$: if
$$\forall \psi \in C(X), \int_X \psi(x)d\...
- 23
2
votes
0
answers
30
views
Distance between a distribution and an empirical distribution of samples
Looking for a reference on what I think is a standard result.
For a measure $\mu \in P(\mathbb{R}^n)$, let $y_1, \dots, y_N \sim \mu$ be independent samples.
The empirical distribution associated with ...
- 1,792
0
votes
0
answers
11
views
how to solve for wasserstein duality easily in a special case when 2-Wasserstein inequality constraint is binding
I was going through this nice paper ” A Simple and General Duality Proof for
Wasserstein Distributionally Robust Optimization”, and one quick qu on applying Theorem 1 to my poject:
What if in my ...
- 61
1
vote
0
answers
40
views
Optimal Transport of radial measures
This is the exercise
i). Find a transport map between $d\mu_d=\frac{1}{\pi}\mathbb{I}_{B_1(0)}dxdy$ and $d\mu_c=\frac{1}{8\pi}\left(4-|x|^2\right)_+dxdy$.
ii) Compute $C^K_{\rho}(\mu_d,\mu_c)$ where ...
- 35
0
votes
0
answers
80
views
Solve $y=\operatorname{erf}(x+c)+\operatorname{erf}(x-c)$ for $x$
$\newcommand{\erf}{\operatorname{erf}}\newcommand{\erfc}{\operatorname{erfc}}$
Is there a closed form solution for $y=\erf(x+c)+\erf(x-c)$?
More specifically, I want to solve
$$\erf(\frac{y}{\sqrt{2}})...
- 11.2k
0
votes
0
answers
46
views
What is the conventional definition of $d(x,y)^{p}$?
In Optimal transportation, and more precisely in
"Optimal Transport: Old and New" (Definition. 6.1, on page 106 - actually on page 111 out of 998, in this link), the Wasserstein distance $...
- 255
0
votes
1
answer
96
views
Optimal Transport Theory: Find a sequence of functions that converge weakly to 1/2 [closed]
I'm trying solve the following problem:
Find a sequence $T_n$ of transport maps from $\mathbb{I}_{[0,1]}dx$ to $\mathbb{I}_{[0,1]}dx$ such that $T_n$ converges weakly to $\frac{1}{2}$. Deduce that the ...
- 35
0
votes
1
answer
21
views
Discrete Monge optimal transport
Here is the problem
Let $\mu$ and $\nu$ be defined by
$$
\begin{aligned}
\mu&=\sum_{i=1}^{N_{\mu}}\alpha_i\delta_{x_i},\\
\nu&=\sum_{j=1}^{N_{\nu}}\beta_j\delta_{y_j},
\end{aligned}
$$
where $\...
- 79
0
votes
1
answer
66
views
Does the subdifferential of a convex function admit a measurable selection?
For a convex function $\varphi: \mathbb{R}^n \to \mathbb{R},$ the subdifferential is defined as
$$\partial \varphi (x) = \{z \in \mathbb{R}^n \mid \forall y \in \mathbb{R}^n, \varphi(y) \geq \varphi(x)...
- 133
1
vote
0
answers
54
views
How to derive the $W_1$ Wasserstein distance written with the quantile functions (i.e. with inverse cumulative distribution functions) [closed]
INTRODUCTION. Either downloading the slides on Optimal Transport (OT) from the Marco Cuturi website (go to section "Teaching ENSAE --> OT --> Optimal Transport (Spring 2023)
[slides]" ...
- 255
1
vote
1
answer
82
views
Why is this probability $1$?
Let's consider two metric spaces $X$ and $Y$.
Definition: Given $\phi: X \to \mathbb{R}\cup\{+\infty,-\infty\}$ and $c:X \times Y \to \mathbb{R}$ we define $\phi^c(y)=\inf\limits_{x \in X} c(x,y)-\phi(...
- 2,706
0
votes
0
answers
13
views
Optimal Mass Distribution Minimizing Average 2-Wasserstein Distance to a Set of Mass Distributions
Given a fixed set of $n$ points in 2D (Earth Movers distance Prpblem), $P = \{p_1, p_2, ..., p_n\}$, I am trying to find the mass distribution $\bar{M}$ that minimizes the average 2-Wasserstein ...
- 595
0
votes
0
answers
69
views
Derive the $d=1$ form of the Wasserstein distance
QUESTION
Given
How to pass from the general definition of the Wasserstein distance (let's call it Equation (1)):
to the closed forms with d=1, here below (let's call them Equation (2) and Equation(3)...
- 255
1
vote
1
answer
55
views
Why do we choose the maximum value instead of minimum?
Vogel's method selects the corresponding variable through a penalty. There is a penalty for each row and column and is the subtraction between the two lowest costs (in absolute value).
We must select ...
- 11
1
vote
0
answers
21
views
Does there exist $f$ such that $f(X) \overset{D}{=} Q$?
Motivation: Let $X$ be a continuous real random variable and let $Q$ be a continuous distribution. Does there exist $f$ such that $f(X)\overset{D}{=}Q$? that is, transformation of $X$ has distribution ...
- 675
1
vote
0
answers
22
views
Upper-bound on the L2 norm of joint density given marginals
Let $X$ and $Y$ be two real random variables with smooth densities $m_X$ and $m_Y$.
Is there a natural condition on $m_X$, $m_Y$ and the dependencies of $X$ and $Y$ such that $(X, Y)$ has a joint ...
- 11
0
votes
0
answers
55
views
Why is optimal transport theory so relevant?
I see plenty of papers published with "optimal transport" in their title and I know that at least 2 Fields medal in the last 10 years were assigned for something related to optimal transport ...
- 77
0
votes
0
answers
24
views
Algorithms to Calculate Wasserstein Distance Between 2-Dimensional Continuous Probability Distributions
Say I've got two probability distributions $p_1(x,y)$ and $p_2(x,y)$ defined for all $x,y\in[-1,1]$, and now I want to calculate the Wasserstein distance between the two. Is there a closed-form ...
- 121
0
votes
0
answers
20
views
the relations between the pushfoward of a random vector and the pushfoward of the linear projections of the random vector
Let $([0,1]^n, \mathcal{B}, P)$ be a probability space where $\mathcal{B}$ is the Borel $\sigma$-algebra and $P$ is a probability measure.
Let $f:[0,1]^n\to \mathbb R^n$ be a measurable function (a ...
- 121
2
votes
0
answers
31
views
A geometrical intuition for Bayes 's posterior
Given two probabilistic distributions (red and blue) it is well known that a linear interpolation between them is well defined (see this).
For example, by the Wasserstein metric we have the following ...
0
votes
1
answer
47
views
Regularity of Kantorovich potentials
I'm looking for a reference of a result in Optimal Transport. I know that if $\Omega$ is a compact subset of $\mathbb R^n$ and $c\in C^1$ (the transportation cost), then $c$ is Lipschitz continuous on ...
- 679
1
vote
1
answer
66
views
Is Optimal Transport Injective?
The Kantorovich formulation of optimal transport:
Let $\mu = \{\mu_1, \mu_2, \ldots, \mu_m\}$ and $\nu = \{\nu_1, \nu_2, \ldots, \nu_n\}$ be two probability measures, we aim to find a transport plan $\...
- 35
0
votes
0
answers
19
views
Are there algorithms for 3d partial retrieval?
Suppose that $\{ P_i \}$ is a dataset of point clouds(PCDs), i.e., set of collections of 3-d real vectors. I have a query PCD $Q$ and I want to find all $P_i$ such that $P_i$ contains a subset (which ...
- 1
3
votes
1
answer
231
views
Boundedness of $\dfrac{W_2(\mu_1+\varepsilon (\mu_2-\mu_1),\mu_1)}{\varepsilon}$ for 2 -Wasserstein metric
Let $\mathcal{P}_2(\mathbb{R}^{n})$ the space of Borel probability measures of finite second moment in $\mathbb{R}^{n}$ equipped with the $2$-Wasserstein metric $W_2$. Let $\mu_1$, $\mu_2 \in \mathcal{...
- 567
0
votes
0
answers
32
views
Solve $\inf_{\mu_0=\mu,\mu_1=\nu}\{\int_0^1\|v_t\|_{L^2(\mathbb{R}^d)}|\partial_t\mu_t+\text{div}(\mu_tv_t)=0\}.$
Let $\mathcal{P}_{2,ac}(\mathbb{R}^d)$ be the space of all probability measures on $\mathbb{R}^d$ with finite 2nd momentum and absoulute continuous w.r.t. the Lesbegue measure. It is known that if we ...
- 97
1
vote
0
answers
50
views
Brenier theorem on manifold
Let $W(\mu,\nu)^2_2$ be the 2-wasserstein distance between probability distributions $\mu,\nu$ over $\mathbb{R}^d$ such that $d\mu,d\nu\ll\text{dVol}$:
$$ W(\mu,\nu)^2_2=\inf_{\pi\in\Pi(\mu,\nu)} \...
- 83
0
votes
0
answers
34
views
How to Correctly Write the Wasserstein (Kantorovich) Distance between Transition Probability Densities of two Markov Processes
I am exploring an idea which is based on computing the Wasserstein (Kantorovich) distance between the empirical transition probability densities of two Itô diffusion processes.
Following from this ...
- 1,089
2
votes
0
answers
56
views
Can certain Convex Optimization Problems be interpreted as Optimal Transport Problems?
The theory of optimal transport considers the problem of transporting utilities distributed acoording to a probability measure $\mu$ on $X$ to "targets" distributed according to a ...
- 1,820
0
votes
0
answers
27
views
Kantorovich problem for compact spaces and continuous cost function
I want to prove the existence of a solution to a special case of the Kantorovich problem:
Let $(X,\mu)$ and $(Y,\nu)$ be compact probability spaces, i.e. $X$ and $Y$ are compact metric spaces and $\mu$...
- 342
0
votes
1
answer
103
views
Decomposition of probability measures with a bounded total variation distance
Fix a probability space $(\Omega, \mathcal{F})$. Let $P$ and $Q$ be two probability measures on $(\Omega, \mathcal{F})$ such that there exist $\varepsilon$ and $\delta$ that for every $A \in \mathcal{...
- 648
0
votes
0
answers
30
views
McCann interpolation on circle
We consider optimal transport on the circle $\mathbb{T}= \mathbb{R}/(2\pi\mathbb{Z})$ equipped with the metric $d(x,y) = \min_{k\in\mathbb{Z}}|x-y-2\pi k|$.
For two probability measures $\mu,\nu$ on $\...
- 45
0
votes
0
answers
44
views
What is the difference between discrete optimal transport and linear programming?
How unique minima are guaranteed to exist in optimal transport. Why such a thing is not possible in general linear programming problems. What theorem guarantees the existence of unique minima to exist ...
- 338
0
votes
0
answers
51
views
Convergence of $\mathbb{E}|\int X(\omega,x) (m_k(dx)-m(dx))|^2$ when $m_k(x)dx$ tends to $mdx$ in Wasserstein 2 distance
In $\mathbb{R}^n$, we suppose that $m_k$, $m$ are probability densities with finite second moment such that $m_k(x)dx$ tends to $mdx$ in Wasserstein 2 distance as $k \to \infty$. If $X(\omega,x)$ is a ...
- 567
1
vote
0
answers
21
views
optimal transport on marginals
Let $\mathcal{M}_1(\mathbb{R}^{n})$ be the space of probability measures on $\mathbb{R}^{n}$.
Given two probability distributions $\mu,\nu$ on $\mathbb{R}^{2n}$, let their marginals be denoted $\mu_i,\...
- 41
1
vote
0
answers
52
views
Relationship between optimal transport and gaussian kernel
Let's say P and Q be two different dirac delta probability measure, and suppose that $K_\sigma$ is a gaussian kernel. Let D be the wasserstein-2 distance.
It is known that $D(P,Q)=D(K_\sigma *P, K_\...
1
vote
1
answer
42
views
Class of transport maps is not closed in space of all measurable maps?
I am trying to understand the following:
Definition:
Map $t:X \to Y$ is called a transport map if it is measurable and $t_{\#}\mu=\nu$ where $\mu$ is a measure on $X$ and $\nu$ is a measure on $Y$.
...
2
votes
1
answer
54
views
Does the reverse triangle inequality holds for Wasserstein-1 distance?
Let $(X,d)$ be a separable metric space with associated Borel $\sigma$-algebra $\mathcal{B}(X)$ and the set of Borel probability measures $\mathcal{P}(X)$. For $\mu,\mu'\in\mathcal{P}(X)$ Wasserstein-...
- 21
3
votes
1
answer
93
views
Does set-wise convergence of probability measures imply convergence of moments?
Let $(S, d)$ be a complete separable metric space and consider the corresponding Borel $\sigma$-algebra $\mathcal{B}(S)$. Let $\mu$ and $\mu_n$, $n \in \mathbb{N}$, be probability measures on $\...
- 1,487
1
vote
1
answer
200
views
Wasserstein distance inequality
Suppose $(\Omega, \mathcal F, \mathbb P)$ is a probability space. Suppose $X, X', Y, Y'$ are random variables.
Denote $W_1$ the Wasserstein-2 distance between $\mathbb P_X$ and $\mathbb P_{X'}$
and $...
- 93
0
votes
1
answer
45
views
I have a question about wasserstein distance
Given the wasserstein distance of order two,
$$d(\mu_{1},\mu_{2})^{2}=inf_{p\in P(\mu_{1},\mu_{2})}\int_{R^{n}\times R^{n}}|x-y|^{2}p(dxdy)$$
Is there $d(\mu_{1},\mu_{2})=d(\mu_{2},\mu_{1})$ or $d(\...
- 1
1
vote
0
answers
49
views
Question on Conditional Probabilities, Joint Probabilities and Optimal Transport Distances
I am working on a data-driven problem, where I want to measure an optimal transport distance (Wasserstein distance) between two empirical multi-dimensional probability distributions. Then I want to ...
- 1,089
3
votes
1
answer
87
views
Scaling property of the Wasserstein metric
I would need help with this example.
Let $(S, ||\cdot||)$ denote a normed vector space over $K =\mathbb R$ or $K =\mathbb C$. Let $X$ and $Y$ be $S$-valued random vectors with $E~[~||X||~] < \infty$...
- 61
3
votes
0
answers
55
views
Reference request: relationship between c-convexity and geodesic convexity on manifolds
I am interested in a characterization of c-convex/c-concave functions (as in Definition 5.2 and Definition 5.7 in Cédric Villani's book, 'Optimal transport, old and new') on manifolds in the case when ...
- 317
2
votes
0
answers
44
views
Compute functional from its first variation
Adopting the philosophy that the first variation of a functional (as defined e.g. here) is like the gradient of a function, is there a way to test whether a given function is the first variation of ...
- 71
0
votes
0
answers
46
views
Integration with product measure
So far, I have come across some definition of product measure like this one:
$$d\pi(x,y) = d\mu(x)\delta(y),$$
where $\pi$ is a product measure on the produt space $(X,Y)$, and $\mu$ is a measure on $...
- 542
1
vote
1
answer
134
views
Optimal Transport between two Gaussians
Consider the optimal transport map $T$ between $N(\mu_0,\Sigma_0)$ and $N(\mu_1,\Sigma_1)$. I believed that the optimal transport was given by:
$$ T(x) = \mu_1 + \Sigma_1^{1/2} \Sigma_0^{-1/2}(x-\mu_0)...
- 78
0
votes
0
answers
101
views
Optimal Transport map between two uniform distribution
Let $\mu$ be a uniform distribution over the interval $[0,1]$, $\nu$ be a uniform distribution over the set $[-1/2,0] \cup [3/2,2]$. What is the optimal transport map from $\mu$ to $\nu$ with ...
- 1
0
votes
0
answers
47
views
Derivative of sequence of measures
Let $\mathcal{P}_2(\mathbb{R})$ be the space of probability measures with finite second moment on $\mathbb{R}$, and $(\mu_t)_{t\geq 0}\subseteq \mathcal{P}_2(\mathbb{R})^{\mathbb{R}^{\geq0 }}$ be a ...
- 1,187
0
votes
0
answers
31
views
When does there exist a map $T$ such that $(X,Y)$ and $(X,T(X))$ have the same distribution?
Let $\mathcal X\subseteq \mathbb R^d$, $\mathcal Y\subseteq \mathbb R$ be equipped with their Borel sigma-algebras, and $X$ and $Y$ be two respectively $\mathcal X$ and $\mathcal Y$ valued random ...
1
vote
0
answers
49
views
Optimal transport map in $\mathbb{R}^n$ with any norm
In the last page of Villani's book "Optimal Transport, Old and New" there's written this: let $N=\Vert\cdot\Vert$ be a uniformly and smooth convex norm on $\mathbb{R}^n$ (i.e. $\exists\...
- 431