Questions tagged [optimal-transportation]
The optimal-transportation tag has no usage guidance.
260 questions
3
votes
1
answer
2k
views
Closed-form formula for Wasserstein distance between uniform discrete distribution and discrete distribution with same support
Let $x_1,\ldots,x_n$ be $n \ge 1$ distinct points in $\mathbb R^d$ and consider two discrete distributions on these points $\mu = (1/n)\sum_{i=1}^n\delta_{x_i}$, and $\nu = \sum_{i=1}^n\nu_i\delta_{...
- 6,853
3
votes
0
answers
49
views
Transport map to lower dimension?
Let $S^{d-1}$ be the sphere in $\mathbb{R}^d$.
Given a $C^\infty$ function $f \colon S^{d-1} \to \mathbb{R}$, define $g \colon S^{d-1} \to S^{d-1}$ as $g(x) = \exp_x(\nabla f(x))$, where $\nabla f(x)$ ...
- 171
3
votes
0
answers
69
views
Wasserstein bounds of interpolation measures
Assume we are given two densities, $p_0$ and $p_1$ on $\mathbb{R}^d$, and define (up to the normalization constant) the interpolation $p_t \propto p_0^{1-t} p_1^t$, which interpolates between $p_0$ ...
- 131
3
votes
0
answers
230
views
Are 1-Wasserstein and 2-Wasserstein distances between multivariate normal distributions equivalent?
The $p$-Wasserstein between two measures $\nu_1$ and $\nu_2$ on $X$ is given by
$$W^p_p(\nu_{1},\nu_{2})=\underset{\pi\in\Gamma(\nu_{1},\nu_{2})}{\inf}\int_{\mathbf{\mathcal{X}}^{2}}d(x,y)^p\pi(dx,dy)$...
- 1,058
3
votes
0
answers
88
views
Instances of c-concavity outside of optimal transport?
Let $X$ and $Y$ be metric spaces, and let $c:X\times Y\rightarrow \mathbb{R}$ be a nonnegative function which we refer to as a cost. For any $\phi:X\rightarrow \mathbb{R}$ and $\psi:Y\rightarrow \...
- 232
3
votes
0
answers
137
views
On the continuity with respect to the increasing convex order
For $p\ge 1$, let $\mathcal P_p(\mathbb R)$ be the set of probability measures on $\mathbb R$ of finite $p^{\rm th}$ moment. Denote by $W_p$ the Wasserstein metric of order $p$ and by $\preceq$ the ...
- 1,409
3
votes
0
answers
66
views
Continuous trajectory of midpoints of length-minimizing geodesics
Let $M$ be a smooth Riemannian manifold, $x$ be a point in $M$, and $\lambda:[0,1]\to M$ be a continuous path. Can we find a family of length-minimizing constant speed geodesics $\gamma_t:[0,1]\to M$ ...
- 131
3
votes
0
answers
66
views
Convex combination of cyclically monotone sets
I want to show the following statement, but I am not sure how.
Proposition(?):
Let $C \in \mathbb{R}^d$ be a compact convex set, and let $u, v : C \to \mathbb{R}$ be smooth convex functions.
Suppose
$$...
- 51
3
votes
0
answers
278
views
Radon-Nikodym derivative of vector-valued measure with respect to another vector-valued measure
Let $(X, | \cdot |)$ be a Banach space.
I am interested in whether one can extend the definition of the Kullback-Leibler divergence
$$
\text{KL}(\mu \ \Vert \ \nu)
:= \int_{\Omega} \ln\left(\frac{\...
- 67
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
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
3
votes
0
answers
106
views
Dependency of the Wasserstein distance on the parameter: a differential perspective
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$. Consider the $2-$Wasserstein distance below:
$$W_2(\mu,\nu)^2 \quad := \quad \inf_{\...
- 345
3
votes
0
answers
243
views
Parametric distances on product spaces of measures
Disclaimer: Please excuse my loose language. I'm neither an expert in geometry nor probability. Please ask for clarification if something appears unclear or awkward to you.
Let $X$ be a topological ...
- 6,853
3
votes
0
answers
362
views
Second-Order Taylor Expansion of Wasserstein Metric and Related Metrics
Suppose that we have a parametric distribution $P_{\theta}$, which is indexed by the parameter $\theta \in \mathbb{R}^d$. Let $W\{\cdot,\cdot\}$ be the Wasserstein Metric between two distributions.
...
- 1,127
2
votes
1
answer
237
views
Is the following set compact w.r.t. the Wasserstein distance?
Fix a finite first moment probability measure $q\in\mathcal{P}_1(\mathbb R ^d)$, and real numbers $K,M,R$. Consider the following set:
$$A:=\left\{p\in\mathcal{P}_1(\mathbb R ^d): \int |x|dp\leq K, \...
- 291
2
votes
1
answer
203
views
Does this maximisation problem admit a finite upper bound?
Let $\mathcal M_2$ be the space of real $2\times 2$ matrices and $\mathcal S_2\subset \mathcal M_2$ be its subset consisting of positive semidefinite elements, i.e. $A\in \mathcal S_2$ iff $A$ is ...
- 1,409
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
2
votes
1
answer
137
views
Wasserstein distance and put function
Let $\mathcal P$ be the set of probability distributions on $\mathbb R$ of finite first order, i.e. $\mu\in\mathcal P$ if
$$\int_{\mathbb R} |t|\mu(dt)<\infty.$$
For $\mu\in\mathcal P$, define its ...
- 1,409
2
votes
1
answer
214
views
For diffeomorphism $f$, if $X$ and $f(X)$ are both Gaussian, then $f$ is affine
I am trying to prove the following.
Let $f:\mathbb{R}^{n}\to \mathbb{R}^n$ be a diffeomorphism. If $X$ and
$f(X)$ are both $n$ -dimensional Gaussian variables, then $f$ is
affine. That is, there ...
- 305
2
votes
1
answer
385
views
Continuity equation $\partial_t \mu_t+\operatorname{div} (v_t \mu_t)=0$: are these two notions of weak solution equivalent?
Let $\Omega$ be an open connected convex subset of $\mathbb R^d$. Let $\mathcal P (\Omega)$ be the space of Borel probability measures on $\Omega$. Let $C_0 (\Omega)$ be the space of real-valued ...
- 657
2
votes
1
answer
176
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 ...
- 715
2
votes
1
answer
309
views
Density in Wasserstein space
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(\...
- 325
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
2
votes
1
answer
194
views
Strong convexity of internal energy with respect to Wasserstein metric
It is well known that the internal energy (see, e.g., Definition 3.32 in and Proposition 3.33 in 1) is geodesically convex with the 2-Wasserstein distance. I was wondering under what condition, the ...
- 422
2
votes
1
answer
257
views
Reference Request: 2-Wasserstein Metric on Wiener Space
Suppose that X is the subspace of the set of probability measures on the classical Wiener space $C[0,T]$, for some $T>0$, comprised of Gaussian measures.
In the finite-dimensional setting, the ...
- 5,405
2
votes
2
answers
312
views
$X$ Polish geodesic implies $(P_2(X), W_2)$ geodesic
If $X,d$ is a complete and separable space then the space of Borel probability measures with finite second moment on $X$ endowed with the Wasserstein distance $W_2$ is geodesic.
I am looking for a ...
- 41
2
votes
1
answer
142
views
Existence of first variation
I am trying to compute the first variation of the functional
$$\mathcal F(\rho) = \int_{\Omega} R(x;\rho) d\rho(x)$$
where $R$ is some function of $x$ that also depends on $\rho$. Here $\rho$ is a ...
- 21
2
votes
1
answer
73
views
Connection between Wassertein-2 metric and difference in variance
Given two probability densities $\mu\in\mathcal P(\mathbb R^d)$ and $\nu\in\mathcal P(\mathbb R^d)$, we define their Wasserstein-$p$ metric as
$$
W_p^p(\mu, \nu)=\inf_{\gamma\in \Gamma(\mu, \nu)}\int_{...
- 123
2
votes
1
answer
100
views
A variant of (discrete) optimal transport problem
Let $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$ and $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ be given and satisfy
$$\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j.$$
Define $\...
- 1,409
2
votes
2
answers
293
views
Optimal transport: the existence of an optimal pair of $c$-conjugate functions
$\newcommand{\diff}{ \, \mathrm d}$
Let
$X,Y$ be Polish spaces,
$\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
$\mathcal P(X)$ the space of Borel probability ...
- 825
2
votes
1
answer
267
views
Optimal transport for applied mathematicians: how does $\varphi (x) = \inf_{y \in Y} [c(x, y) - \psi (y)] \neq -\infty$ follow in Theorem 1.37?
I'm reading a proof of Theorem 1.37 from Santambrogio's Optimal transport for applied mathematicians: calculus of variations, PDEs, and modeling. First, I quote related definitions. Let $X,Y$ be ...
- 657
2
votes
1
answer
222
views
Given iid samples from the joint distribution $P$ of pair of r.v.'s $(X,Y)$, how to get iid samples from independence coupling $P_X \otimes P_Y$?
Let $(X,Y)$ be a pair of random variables on a measure space $\mathcal T \subseteq \text{"subsets of }\mathbb R^2\text{"}$, with joint probability distribution $P$.
We don't assume $X$ and $Y$ are ...
- 6,853
2
votes
1
answer
767
views
Integer solution of optimal transport
Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...
- 407
2
votes
1
answer
141
views
(Sub)Optimality of random transport
Problem Setup: Consider the intervals $I_R = [a_R, b_R]$ and $I_B = [a_B,b_B]$. Let $F_R$ and $F_B$ denote the CDF of distributions with support on the intervals $I_R$ and $I_B$. I draw $k$ red and ...
- 25
2
votes
1
answer
129
views
Wasserstein distance of push-forward measures
I asked this same question on MSE, but with no luck, so I am trying to ask here.
Consider two measures $\mu , \nu$ on $\mathbb{R}^n$. Now consider a map (a priori only measurable, but feel free to add ...
- 749
2
votes
1
answer
534
views
Bounds on the Bures–Wasserstein distance
The Bures–Wasserstein distance between $n\times n$ positive semidefinite matrices $A$ and $H$ is defined to be
$$
d(A,H) := \left[ \operatorname{tr} A + \operatorname{tr} H - 2\operatorname{tr} (A^{1/...
- 283
2
votes
1
answer
304
views
An approximation problem w.r.t marginal distribution of coordinates of uniform random vector on high-dimensional unit-sphere
Let $X=(X_1,\ldots,X_d)$ be uniformly distributed on the sphere of radius $\sqrt{d}$ in $\mathbb R^d$. Fix a "sufficiently integrable" function $h:\mathbb R \to \mathbb R$, and define ...
- 6,853
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
2
votes
1
answer
173
views
Is there an analogue of transportation-cost inequality under a weighted Log-Sobolev Inequality?
It is known that under the Log-Sobolev Inequality for $\pi$, i.e., if for all $\rho$,
$$H_\pi(\rho):=\int \rho(x)\log\frac{\rho(x)}{\pi(x)}dx \leq \frac{1}{2\beta}\int \rho(x)\left\|\nabla \log\frac{\...
- 21
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
2
votes
1
answer
317
views
optimal transport, measurable selection
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(...
- 325
2
votes
1
answer
210
views
Controlling Mean Difference Between Product and Joint Distributions Using Optimal Transportation
Suppose we have nonindependent random variables $X \sim P$ and $Y \sim Q$, where $P$ and $Q$ denote their marginal distributions. We are interested in upper bounding
$$
|\mathbf{E}_{X, Y\sim P \...
- 1,127
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
2
votes
1
answer
261
views
Existence of solution to a martingale optimal transport type problem
I encounter the following problem during the course of my research: Given a random variable $Y=(Y_1,Y_2)$ with values in $\mathbb R^2$ and the cost function $c(x,y)=(x_1-y_1)(x_2-y_2)$ where $x=(x_1,...
- 325
2
votes
1
answer
148
views
Fast algorithm for large-scale, asymmetric transportation linear program
I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
- 4,049
2
votes
0
answers
106
views
When is there a Lipschitz Kantorovich Potential?
Let $c:\mathbb{R}^d\times \mathbb{R}^d\to [0,\infty)$ be a Lipschitz cost function and consider the optimal transport problem
$$
C(\mu,\nu):=\inf_{\pi}\, \int c(x,y)\,\pi(dxdy)
$$
where, as usual, the ...
2
votes
0
answers
59
views
Random solutions to non-Lipschitz ODEs, optimal transport, and general solutions to the continuity equation
I am reading Cedric Villani’s book “Optimal Transport: old and new” and I am stuck on one paragraph (see page 26/27 in this book). He speaks about random solutions to an ODE and I simply cannot figure ...
- 21
2
votes
0
answers
95
views
Can we control the Wasserstein metric between $\mu$ and $\nu$ by their moment difference?
Fix $p \in [1, \infty)$. Let $(\mathcal P_p(\mathbb R^d), W_p)$ be the Wasserstein space of all Borel probability measures on $\mathbb R^d$ with finite $p$-th moment. Let $D_p$ be the collection of ...
- 657
2
votes
0
answers
92
views
Construct a Bregman divergence from Wasserstein distance
I was wondering whether one has studied the Bregman divergence arising from a squared Wasserstein distance.
More precisely, let $\Omega\subset \mathbb{R}^d$ be a compact set and $c\in \Omega\times \...
- 503
2
votes
0
answers
110
views
relative entropy, Fisher information, and metric slope for non-convex domains
$\newcommand{\R}{\mathbb R}$ If $\Omega\subset \R^d$ is a convex domain it is well-known that the relative entropy
$$
\mathcal H(\rho)=
\int_{\Omega}\rho\log\rho \ \mathrm{d}x
\qquad \mbox{for }\rho=...
- 5,380