Questions tagged [optimal-transportation]
The optimal-transportation tag has no usage guidance.
260 questions
2
votes
1
answer
114
views
Reweighting probability measures by convex potentials, and contraction in transport distance
Let $W: \mathbf{R}^d \to \mathbf{R}$ be a convex function such that $\int \exp(-W) = 1$, and define probability measures $\mu_y$ by
$$\mu_y (dx) = \exp( - W (x - y)) \,dx,$$
i.e. each $\mu_y$ is a ...
- 801
1
vote
0
answers
130
views
Orthogonality in Wasserstein tangent space for discrete measures with equal mass
Let say I have $N$ discrete probability measures $(\mu_1,...,\mu_N)$ where each of them has $n$ points in $\mathbb{R}^2$ of equal mass.
Let $P(\mathcal{X})$ be the space of these probability measures ...
- 19
0
votes
1
answer
267
views
Intersection of projection of sets
Suppose that we have two arbitrary sets $\mathcal{X}$, $\mathcal{Y}$ and are given a function $c : \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$
Consider the following inequality for ...
- 143
0
votes
0
answers
291
views
Convexity of a set of probability densities
Consider the space of probability densities $(P(\mathbb{R}^d), W_2)$ (probability measures on $\mathbb{R}^d$ with 2-Wasserstein distance).
How can we determine if a subset $Q$ is convex?
I know that a ...
- 153
0
votes
0
answers
95
views
Empirical estimation of Brenier map from data
Let $f:\mathbb R^d \to \mathbb R$ be a "nice" (say, continuous) function define $A = A_f := \{x \in \mathbb R^d \mid f(x) \ge 0\}$ and $B =B_f:= \{x \in \mathbb R^d \mid f(x) \le 0\}$, and ...
- 6,853
0
votes
1
answer
86
views
Is integration against an indicator Wasserstein-Continuous
Let $\mathcal{P}_p(X)$ denote the Wasserstein space over a compact metric space $X$, and $1\leq p<\infty$. Fix a non-empty closed subset $C\subseteq X$. Then is the map:
$$
\mathbb{P} \mapsto \...
- 5,405
8
votes
1
answer
386
views
How does Otto theory work in this example of Wasserstein a.c. curve of probabilities?
I'm trying to read chapter 8 of the book on gradient flows by Ambrosio-Gigli-Savaré. In this context, I would like to better understand how the theory works for the following specific example. Take ...
- 445
3
votes
2
answers
783
views
Relation between optimal transport cost and difference between topological invariants?
I was working on some mathematics of Wasserstein GAN and found out a seemingly interesting research problem but I am not quite sure whether it has already been studied in some recent literature of ...
2
votes
0
answers
123
views
Closure of finite support measures in the Wasserstein metric
This is a follow-up question to this question:
Closure Wasserstein for pointmasses
Let $(X,d)$ be a metric space, and let $W_1(X)$ be the space of probability measures $\mu$ on $X$ having finite first ...
- 11.1k
4
votes
2
answers
225
views
Are there alternative regularizations for optimal transport problems besides entropic regularization?
I see that most of the regularization done involves an entropy term.
Has there been any work done on other regularization methods? In particular, I'm wondering if anyone has done a regularization ...
- 383
2
votes
1
answer
1k
views
Wasserstein interpolation between two probability measures on a metric space
Question 1
Given probability measures $\mu$ and $\nu$ on the same metric space $X=(X,d)$, and $\alpha \in [0, 1]$, is it always possible to find another probability measure $\lambda_\alpha$ on $X$ ...
- 6,853
4
votes
1
answer
2k
views
Is an ambiguity set with Wasserstein distance of order 1 is convex?
I have a question about the convexity of an Wasserstein ambiguity set.
Let $W_1(\mu, \nu)$ be the Wasserstein distance of order 1 between $\mu$ and $\nu$, defined as
$$W_1(\mu, \nu) := \min\limits_{\...
- 51
1
vote
2
answers
889
views
Simplify Wasserstein distance between Gaussians with binary cost function
Let $\mu_1$ and $\mu_2$ be 1D gaussian distributions with means $m_1$ and $m_2$ respectively and common variance $\sigma$. Let $\Omega$ be a closed subset of $\mathbb R^2$, and consider the cost ...
- 6,853
2
votes
1
answer
228
views
Ideas on how to prove Pythagorean identity involving Wasserstein distances?
I conjectured earlier that if $P$ and $Q$ were two probability measures, then we could show
$$W^2(P,Q) = \min_{T} [d^2(P,T_{\#}P) + W^2(T_{\#}P,Q)]$$ where $W^2(P,Q)$ denotes the squared Wasserstein-2 ...
- 383
5
votes
2
answers
422
views
Bounding probability densities on a Wasserstein-2 geodesic
Consider two probability measures which are supported on a bounded domain $\Omega$ with density functions $p_0$ and $p_1$. It is well-known that for the Wasserstein-2 distance, there exists uniquely a ...
- 325
1
vote
0
answers
37
views
Sufficient condition for an $n$-tuple to be a convex conjugate
We say $(f_1,f_2,\dotsc,f_N)$ is a convex conjugate if for any $i=1,2,\dotsc,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(...
- 183
1
vote
0
answers
85
views
Producing a minimiser for the Kantorovich problem from a minimiser of the Beckmann flow problem
Notation: We denote by $\mathcal M$ the set of vector valued measures on $\mathbb R^d$ whose divergence is a scalar measure (in the weak sense).
Definitions: Consider the Beckmann flow minimisation ...
- 6,313
5
votes
0
answers
140
views
What kinds of gradient-flows on $\mathbb R^d$ preserve the log-concavity of the distribution $\mu_0$ of starting point $x_0$
Let $\mu_0$ be a log-concave distribution on $\mathbb R^d$ and let $f:\mathbb R^d \to \mathbb R$ be $C^2$. Let $x_0$ be sampled uniformly at random from a log-concave distribution $\mu_0$, meaning ...
- 6,853
1
vote
1
answer
270
views
Wasserstein space with strictly non-positive sectional curvature
Let $(X,d)$ be a (separable, complete) metric space with uniformly strictly non-positive curvature in the sense of Alexandrov, i.e. $(X,d)$ satisfies a $CAT(K)$ inequality for some $K<0$.
Does it ...
- 660
4
votes
1
answer
430
views
Optimal transport: find cost function given observed transport
Could you advise me please on what to read on the "inverse" problem: suppose I have a source measure, a target measure and I observe the solution to optimal transport problem -- can I "back out" the ...
- 41
3
votes
2
answers
734
views
Maximum cost optimal transport
Kantorovich's optimal transportation problem
\begin{equation}
\tau_c(\mu,\nu)=\min\limits_{\pi\in\Pi(\nu,\mu)} \int_{X\times Y}c(x,y)d\pi(x,y)
\end{equation}
where $\Pi(\mu,\nu) = \{\pi\in P(X\times ...
- 31
1
vote
0
answers
113
views
Statistical analysis of optimization solution involving Brenier potentials?
I'm reading the paper https://arxiv.org/pdf/1905.10812.pdf where strongly convex approximations to Brenier potentials are approximated.
Let $\mathcal{E}$ be a partition of $\mathbb{R}^{d}$ and $ 0\leq ...
- 383
3
votes
0
answers
82
views
Semiconcavity estimate for the squared distance on a compact Riemannian manifold
I am currently reading this paper on the Riemannian structure of the Wasserstein space over a compact Riemannian manifold (my question doesn't concern the Wasserstein metric), specifically Section 4.1,...
- 31
10
votes
1
answer
454
views
Open Questions about Wasserstein Space and PDE
While working on my thesis, I encountered the idea of OMT and started reading some more (like Villani's book). In particular, I came across a PhD thesis by Martial Agueh. I thought it was interesting ...
- 427
4
votes
2
answers
415
views
Effect of perturbing the atoms of a measure on the Wasserstein distance
Let $(X,d)$ be a metric space, $x_1,\ldots,x_N\in X$ and $x_1',\ldots,x_N'\in X$ be atoms, and $G=\sum_{i=1}^Np_i\delta_{x_i}$, $G'=\sum_{i=1}^Np_i'\delta_{x_i}$, and $G''=\sum_{i=1}^Np_i'\delta_{x_i'}...
- 710
8
votes
1
answer
623
views
Completion of spaces of measures w.r.t. weak norms
For the sake of concreteness denote by $M_0(X)$ the linear space of all signed Borel measures $\sigma$ with $\sigma(X)=0$ on some metric space $(X,d)$ and fix some base point $x_0\in X$. On this space ...
- 12.7k
6
votes
1
answer
580
views
Why is it difficult to solve the Monge problem directly?
I'm trying to understand something about the Monge problem. The Monge problem is:
Let $c(x,y): \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}^d$ and $$\mathcal{T}(\mu_1,\mu_2) = \{ T: \...
- 427
1
vote
0
answers
96
views
Relationship between Wasserstein projections and metric projections in a linear space
Let $(X,d)$ be a metric space, $x\in X$, and $Y\subset X$ is a closed set. Assume that $X$ is also a real vector space, so that we can form linear combinations over $\mathbb{R}$, but I do not assume ...
- 13
0
votes
0
answers
87
views
How does one define weak convergence of probability measures in $L^{\infty}(\Omega)$?
I am reading the following article and on page 9/17 (above Eqn (4.9)) the authors state that if $\gamma_{\epsilon_k}|\_G_{\delta}\times \Omega\to \gamma|\_G_{\delta}\times \Omega$ as $\epsilon_k\to 0$ ...
- 547
2
votes
1
answer
289
views
On semi-discrete Wasserstein distance
Let $\mu(dx)=\sum_{i=1}^np_i\delta_{x_i}(dx)$ and $\nu(dy)=\rho(y)dy$ be two probability measures on $\mathbb R^d$, where $\nu$ has a bounded support. Consider the $2-$Wasserstein distance below:
$$...
- 345
1
vote
0
answers
543
views
Variational derivative of Wasserstein distance using Benaumou-Brenier formulation
I learned from the gradient flow theory in Wasserstein space that an equation of gradient flow type
$$\partial_t \rho + \nabla \cdot (\rho \nabla \frac{\delta F}{\delta \rho})=0,$$
can be derived as ...
- 429
0
votes
1
answer
141
views
Arbitrarily bad rates of convergence in Wasserstein metric
Suppose $W_p(\mu_n,\mu)\to 0$ and $d(E(\mu_n),E(\mu))<r_n$. Here, $W_p$ is the $p$th-order Wasserstein distance (with respect to the metric $d$) and $\mu_n,\mu$ are probability measures on some ...
- 13
4
votes
0
answers
220
views
improved regularization for $\lambda$-convex gradient flows
It is well-known that gradient-flows of convex functionals are "parabolic" in some vague sense, and accordingly solutions tend to regularize instataneously. In the abstract context of gradient flows ...
- 5,380
2
votes
1
answer
571
views
Semi-discrete Wasserstein distance to uniform
Does the $p$-Wasserstein distance have a simpler expression when applied to these two distributions :
A uniform distribution on $[0,1]^d$
A discrete distribution with $N$ equally-weighted point mass ...
- 686
1
vote
1
answer
247
views
Scaling behavior of Wasserstein distances
Let $p>1$ and $\mu\neq \nu$ be two probability measures on $\Omega\subset \mathbb{R}^d$ a bounded set. For $\alpha \geq 0$, we let $$C_\alpha(\mu,\nu) = \inf_\sigma \frac{W_p(\mu+\sigma,\nu+\sigma)}...
- 83
0
votes
0
answers
72
views
Optimal transport mapping between sets with a common subset
What would the optimal transport mapping between two sets with a common subset be? The problem I'm thinking about is the following:
I'm in $\mathbb{C}^n$ and I have two distributions $\mu$ and $\nu$ ...
- 383
3
votes
1
answer
142
views
Is the Wasserstein kernel positive definite?
Define a point cloud $X=\{x_i\}_{1\leq i\leq n}$, for $x_i\in\mathbb R^d$. Define the Wasserstein kernel as $$W(X,Y)=\max_{T}\frac{1}{n}\sum_{kl}T_{kl}\langle x_k,y_l \rangle$$
where $T$ is any doubly ...
- 345
0
votes
1
answer
223
views
A problem with the dual form of semi-discrete optimal transport
Consider the uniform distribution $\lambda$ on $[0,1]$, and a point measure $\rho$ with density $\frac{1}{2} (\delta_{x_1} + \delta_{x_2})$, where we have $0\le x_1 \le x_2 < 1/2$.
If our cost is ...
2
votes
0
answers
101
views
$CD(K,N)$ condition for non complete metric measure spaces
That's basically it. I would like to know if it's possible to define the ${\sf CD}(K,N)$ condition for metric measure spaces that are not necessarily complete. The references I have found on this ...
- 21
5
votes
1
answer
396
views
Universal decay rate of the Fisher information along the heat flow
I'm looking for a reference for the following fact: In the torus $\mathbb T^d$ let me denote by $u_t=u(t,x)$ the (unique, distributional) solution of the heat equation
$$
\partial_t u=\Delta u
$$
...
- 5,380
4
votes
1
answer
596
views
Monge-Kantorovich duality with a $\{0,1\}$ cost function
Consider the usual Monge-Kantorovich transportation problem where $X$ and $Y$ are Polish spaces, $\mu$ and $\nu$ are probability measures on $X$ and $Y$, and $c:X\times Y \to \mathbb{R}^+ \cup \{+\...
- 4,049
1
vote
1
answer
1k
views
Monotonicity, Convexity, and Smoothness of the KL-Divergence between Two Brownian Motions with Different Initializers
We consider the two distributions
$$
p_t = p_0 * N(0, tI),\quad q_t = q_0 * N(0, t I),
$$
where $*$ denotes the convolution between two densities, while $p_0$ and $q_0$ have the same mean and ...
- 1,127
3
votes
0
answers
163
views
A new "adversarial" Wasserstein distance?
Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
- 555
8
votes
3
answers
936
views
Question about Wasserstein metric
Let $\mu$ and $\nu$ be two probability measures on $\mathbb R^n$ with finite first moment. Denote by $d:=W_1(\mu,\nu)$, where $W_1(\cdot,\cdot)$ stands for the Wasserstein distance of order $1$.
My ...
- 345
4
votes
0
answers
107
views
Upper bound $\tau_C := \int_{\|x\| \le 1}(vol(C \cap (x + C))/vol(C))dx$ for a convex body $C \subseteq \mathbb R^n$, by reducing to a ball
Let $C$ be a convex body in $\mathbb R^n$, i.e a bounded convex subset of $\mathbb R^n$ which has nonempty interior, and which is (A) open, or (B) closed (I'm not sure one makes more sense; choose the ...
- 6,853
3
votes
2
answers
165
views
continuity/ measurablity of optimal transport
given polish space $(X,d)$, consider weak* topology of probability. optimal transport of probability $u,v$ is defined by $\pi(u,v)$ such that $\pi(u,v)$ minimizes:
$\{\int d(x,y) d \pi(dx,dy): \pi \...
- 553
7
votes
2
answers
3k
views
The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
- 422
4
votes
1
answer
2k
views
Earth movers distance (EMD) between two multivariate normals. Is it negative definite distance?
I was looking at the closed form formula for 2-Wassersteins distance for multivariate normal distribution on Wikipedia. https://en.wikipedia.org/wiki/Wasserstein_metric#Normal_distributions
It has a ...
- 141
9
votes
3
answers
2k
views
2-Wasserstein (optimal transport) and extension to the set of all signed measures
Consider the 2-Wasserstein distance between probability measures $\mu$ and $\nu$ (on $\mathbb{R}^d$), defined as
$$
d_{W_2}(\mu,\nu) = \inf_{\gamma} \Big[\int \|x-y\|^2 d\gamma(x,y)\Big]^{1/2}
$$
...
- 1,741
0
votes
1
answer
211
views
Relationship between a certain binary optimal transport and total-variation of modified distributions
Let $\mathcal X$ be a Polish space, and let $(N_x)_{x \in \mathcal X}$ be a system of closed neighborhoods in $\mathcal X$. Define $\Omega := \{(x,x') \in \mathcal X^2 \mid N_x \cap N_{x'} = \emptyset\...
- 6,853