Questions tagged [optimal-transportation]
The optimal-transportation tag has no usage guidance.
260 questions
4
votes
0
answers
183
views
Regularity of optimal transport of Gaussian mixtures
In one of the problems that I am working on, I came across the topic of smoothness of optimal transport for Gaussian mixtures. In particular, let $P=P_\theta=\sum_{i=1}^k \frac{1}{k}\mathcal{N}(x| \...
- 161
5
votes
0
answers
244
views
Distribution of point knowing target in optimal matching
I am a young PhD student in statistics.
Recently, papers (Ambrosio, Stra and Trevisan; Talagrand; Ledoux to cite but a few) tackled the problem of finding the expected cost in an optimal matching, ...
- 555
0
votes
0
answers
103
views
Expectation of maximal Wasserstein distance between empirical distribution and a pdf
Let $P$ be a continuous probability distribution on $R^d$, $X$ the random variable $\sim P$, and $
\hat{X}$ be n i.i.d samples drawn according to $P$. We have another variable $\mu \in S^{d-1}$.
Do ...
- 109
3
votes
1
answer
311
views
Kantorovich duality with pseudometrics
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 ...
2
votes
0
answers
266
views
Optimal transport between Gaussian mixtures 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}(...
- 161
1
vote
1
answer
124
views
Finding $P$ points among $N$ to approximate a probability density function?
Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...
- 2,306
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
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 ...
3
votes
1
answer
202
views
Is there a coupling that induces a given coupling via a transition kernel?
Let $X,Y$ be two measurable spaces, $\mu,\nu$ two probability measures on $X$, and $\kappa$ a transition kernel from $X$ to $Y$.
Define $\tilde\mu(dy)=\int_X\kappa(dy|x)\mu(dx)$ and $\tilde\nu(dy)=\...
- 1,675
8
votes
2
answers
740
views
How does a statistical divergence change under a Lipschitz push-forward map?
Let $\mu, \nu$ be two probability measures on a space $X$ (assume Polish space).
$T: X \rightarrow Y$ is a Lipschitz-map that acts as a push-forward on these measures; let $\mu^\prime = T_{\#\mu}$ and ...
- 615
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
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
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
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
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
3
votes
1
answer
351
views
Regularity of linearized Monge-Ampere equation
Consider the linearized Monge-Ampere equation $ (p-q)+\nabla\cdot(p\nabla\phi)=0$, where $p$ and $q$ are the density functions of two probability measures, which are supported on a bounded domain $\...
- 325
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
0
answers
116
views
A variant of the optimal transport
Let $\mu$, $\nu$ and $\gamma$ be three probability measures on $\mathbb R$. Consider the optimisation problem as follows:
$$\inf_{(X,Y,Z)}~ \mathbb E\big[|Y-Z|^2\big],$$
where the inf is taken ...
- 345
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
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
4
votes
0
answers
757
views
Tangent space and gradient on subspace of Wasserstein space given by finitely supported measures
Let $\mathcal{P}_2(M)$ be the 2-Wasserstein space over some Riemannian manifold $(M,g)$ (connected, complete, and without boundary). Let $\mathcal{FP}_2(M,n)$ be the subspace of probability measures ...
- 1,675
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
4
votes
1
answer
351
views
Inf of Jensen's inequality
I'm reading a monograph that considers the following problem:
$$\inf_{z(t) \in C^1} \int_0^1 c\bigg(\frac{dz(t)}{dt}\bigg) dt\\ z(0) = x, z(1) = y$$
Here $c$ is a convex function, $z(t)$ are paths ...
- 427
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
6
votes
2
answers
2k
views
Wasserstein distance and the Kantorovich-Rubinstein duality
The only few references I could find on this topic are either amateur blog posts (http://n.ethz.ch/~gbasso/download/A%20Hitchhikers%20guide%20to%20Wasserstein/A%20Hitchhikers%20guide%20to%...
- 2,246
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
10
votes
1
answer
274
views
Cutting a Gaussian in two pieces that are maximally separated in the Wasserstein metric
Denote the standard Gaussian probability measure on $\mathbb R^n$ by $\gamma$. We partition $\mathbb R^n$ into two sets $A$ and $A^c$ such that $\gamma(A) = \gamma(A^c) = 1/2$.
Denote by $\gamma_{A}$...
- 1,034
3
votes
1
answer
752
views
Wasserstein convergence of conditional measures
Suppose $W_r(\mu_n,\mu)\to0$, where $\mu_n$ and $\mu$ are discrete probability measures on some metric space $\Omega$, and that all measures have the same number of atoms $d$ (but not the same atoms):
...
- 710
3
votes
2
answers
758
views
Multi-marginal optimal transport
The notion of Wasserstein distance between two probability measures is well-studied and well-motivated in many different branches of math and stat.
Let $\mu$ and $\nu$ be any two probability measures ...
- 1,109
7
votes
1
answer
438
views
An isoperimetric type of inequality in terms of Wasserstein distance/Optimal transport
Let $A \subset \mathbb{R}^n$ be a region having the same volume as an $n$ dimensional ball $B^n_R$ with radius $R$ centring at the origin.
Isoperimetric inequality says:
$ Vol_{n-1} \partial A \geq ...
- 365
7
votes
1
answer
865
views
Fenchel-Rockafellar Duality in Villani's Book
Villiani writes (some notation changed) in Topics in Optimal Mass Transportation:
Theorem 1.9. Let $E$ be a normed VS, $E^*$ it topological dual. $\Theta$ and $\Psi$ are two convex functions on $E$ ...
- 427
2
votes
0
answers
75
views
existence of minimizer to the dual problem of a martingale optimal transport type problem
Let $\nu$ be a given probability measure on $\mathbb R^2$ and consider function of the following form:
$$L(f)(x_1,x_2)=\sup_{y\,=\,(y_1,y_2)\,\in\, \operatorname{Graph} (f)} \{ x_1 y_2 + x_2 y_1 - ...
- 325
4
votes
0
answers
589
views
Optimal transport between two distributions in a Markov chain
In a previous question, given an ergodic Markov chain, I'm interesting in sampling as short a path as possible with prescribed distributions for its endpoints. In a comment, I propose that the ...
- 6,853
1
vote
1
answer
218
views
How to sample a path between 2 states in a Markov chain
Given an ergodic Markov chain and 2 states $x$ and $y$, how may one algorithmically sample a path (of finite length) $x =: s_0 \rightarrow s_1 \rightarrow \ldots \rightarrow s_T = y$ between $x$ and $...
- 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
39
votes
3
answers
4k
views
Manifold of probability measures: connections between two types of metrics
The space of probability measures could be viewed as an infinite-dimensional manifold, equipped with two possible types of metrics — (1) Wasserstein and (2) Fisher-Rao. Metric (1) is connected with ...
- 1,127
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
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
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
1
vote
0
answers
48
views
Negative Definiteness of Hopf-Lax-Oleinik Semigroup
Denote by $H_{t}$ the Hopf-Lax semigroup, i.e.\begin{equation}
H_{t}f(x)=\inf_{y\in\mathbb{R}}\left\lbrace f(y)+\frac{(x-y)^{2}}{2t}\right\rbrace.\end{equation} Is $H_{t}$ negative definite on bounded,...
- 289
1
vote
1
answer
129
views
Optimization problem restricted to a smaller field?
Let $c:\mathbb R^2\to\mathbb R$ be a Lipschitz and bounded function (which can be supposed as "nice" as possible). Let $\mu$ and $\nu$ be two probability measures on $\mathbb R$ with finite first ...
- 1,835
20
votes
2
answers
2k
views
The geometric median of a triangle
Let $\Omega\subset \mathbb R^n$ be a compact domain of dimension $n$. Define the geometric median on $\Omega$ as the point $m_{\Omega}\in \mathbb R^n$ such that the integral $\int_{\Omega}|x-m_{\Omega}...
- 14.3k
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
1
vote
1
answer
685
views
Existence of optimal coupling in optimal transport
Let $P,Q$ be any two distributions over a space $\mathcal{X}$ and let $\mathcal{M}(P,Q)$ be the set of all couplings of $P$ and $Q.$ For a given metric $d$ over $\mathcal{X},$ the optimal transport ...
- 1,269
4
votes
1
answer
725
views
Is there an elementary proof of the polar factorization theorem for vector-valued function?
I have recently learned the polar factorization theorem for vector-valued functions due to Brenier. Namely, given a probability space $(X,\mu)$ and a bounded domain $\Omega\subset \mathbb{R}^n$ with ...
- 1,881
1
vote
0
answers
121
views
$\mathbb{P}(d(X,Y)>\alpha)<\beta$ if $\mathbb{P}(X\in E)\leq \mathbb{P}(Y\in E^{\alpha})+\beta$ for all measurable E
Given two random variables X,Y with measures P,Q. Show that if $P(E) \le Q(E^\alpha) + \beta$ for all measurable $E\subset\mathbb{R}$ then $\mathbb{P}(d(X,Y)>\alpha)<\beta$.
Only hints please.
...
- 395
8
votes
1
answer
727
views
continuity of the Boltzmann entropy in the Wasserstein metric
For Lebesgue-absolutely continuous probability measures $\rho\ll \mathcal{L}^d$ in the whole space $\mathbb{R}^d$ with finite second moments (i-e $\rho\in \mathcal{P}^2_{ac}(\mathbb{R}^d)$), let
$$
\...
- 5,380
6
votes
1
answer
402
views
Reference request: Wasserstein metric spaces for non linear weights/mobility?
There is a very nice theory of gradient flows in metric spaces by Ambrosio, Gigli and Savaré. One particularly important application is the quadratic Wasserstein setting, where the metric space in ...
- 5,380
5
votes
1
answer
2k
views
Earth mover/Wasserstein distance between a pdf and an empirical distribution
This question is inspired by this much older question:
Convergence of an empirical distribution w.r.t. the Hellinger distance
Let $P$ be a continuous probability distribution on a compact subset of $...
- 51