Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimal-transportation]

The tag has no usage guidance.

0
votes
0answers
17 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}(...
0
votes
1answer
68 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
votes
1answer
108 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
1answer
99 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)=\...
2
votes
1answer
65 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 ...
3
votes
2answers
220 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'}...
2
votes
1answer
72 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 \...
3
votes
1answer
138 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 $$ ...
3
votes
1answer
76 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 ...
3
votes
1answer
104 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 $\...
0
votes
0answers
40 views

Intuition behind a wasserstein distance between conditional distributions?

Is there an intuitive way to think about the Wasserstein distance between conditional distributions? Say I want to relate $W(y_s|x_s, y_t|x_t)$ to $W(y_s,y_t)$. Is this possible? I'm struggling to ...
2
votes
0answers
71 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 ...
3
votes
0answers
53 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_{\...
2
votes
0answers
99 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 ...
2
votes
0answers
63 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: $$...
3
votes
0answers
109 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
vote
0answers
88 views

Rate of convergence of probabilities under Wasserstein convergence of measures?

Suppose $\mu=\sum_{i=1}^k p_i\delta_{x_i}$ and $\mu'=\sum_{i=1}^k p_i'\delta_{x_i'}$ are two atomic probability measures. Let $W_r(\mu,\mu')$ be the Wasserstein distance between $\mu$ and $\mu'$. Are ...
3
votes
1answer
248 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 ...
4
votes
1answer
233 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 ...
1
vote
1answer
118 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,...
3
votes
2answers
533 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
votes
1answer
137 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(\...
9
votes
1answer
163 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}$...
3
votes
1answer
185 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): ...
3
votes
2answers
328 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 ...
7
votes
1answer
304 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 ...
6
votes
1answer
307 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$ ...
2
votes
0answers
48 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 - ...
4
votes
0answers
254 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 ...
1
vote
1answer
157 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 $...
3
votes
0answers
165 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. ...
28
votes
2answers
1k 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 ...
8
votes
3answers
400 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 ...
7
votes
2answers
820 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$...
2
votes
1answer
88 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 ...
1
vote
0answers
35 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,...
1
vote
1answer
111 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 ...
17
votes
2answers
1k 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}...
7
votes
1answer
362 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 ...
1
vote
1answer
172 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 ...
4
votes
0answers
211 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
vote
0answers
113 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. ...
4
votes
1answer
328 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 $$ \...
4
votes
1answer
216 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
votes
1answer
538 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 $...
0
votes
0answers
168 views

Reference request: density of $C_c^{\infty}(\mathbb R^d)$ in $L^2(\mathbb R^d,d\rho)$

My question is motivated by an optimal transportation approach to PDE's and gradient flows in metric spaces (see e.g Otto's geometry of dissipative evolution equations: the porous media equation and ...
4
votes
1answer
299 views

PDE-Based Triangle Inequality for Optimal Transportation

Suppose $\Omega$ is a suitably regular domain in $\mathbb{R}^n$ and $\rho_0,\rho_1\in\textrm{Prob}(\Omega)$. Benamou and Brenier showed that the $L_2$ transportation distance between $\rho_0$ and $\...
3
votes
1answer
453 views

Modulus of of continuity of a convolution operator with respect to Wasserstein metric

For a (discrete) measure $G$ on some reasonable metric space $\Theta$, consider the map $G \mapsto f_G$ defined as $$ f_G := f*G(dx) := \int f(dx|\theta) G(d\theta) $$ for some nice kernel function $...
1
vote
0answers
42 views

Constructing a family of domains for application of method of continuity in optimal transportation

Anyway can help me about this paper? http://arxiv.org/pdf/math/0601086v4.pdf I want to ask page 20, The author want to construct a family of subdomain for using method of continuity. But I can't ...
14
votes
0answers
1k views

1-Wasserstein distance between two multivariate normal

The $p$-Wasserstein between two measures $\nu_1$ and $\nu_2$ on $X$ is given by $$d_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)$...