Questions tagged [optimal-transportation]
The optimal-transportation tag has no usage guidance.
260 questions
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
1
vote
1
answer
242
views
Barycenter Map on Wasserstein Space
Let $(X,d)$ be a complete separable metric space, $P_1(X,d)$ be the set of Radon probability measures on $X$ satisfying
$$
P_1(X,d)\triangleq \left\{
\nu:\,(\exists x_0\in X)\, \int_{x\in X} d(x,x_0)d\...
- 5,405
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
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
1
vote
0
answers
56
views
Moduli of continuity and Wasserstein differentiability of functions between measures
Let $X=\mathbb{R}^n$; I am also interested in the general case $X$ is a metric space but for simplicity let's focus on Euclidean space. Let $\mathcal{P}(X)$ denote the space of Borel probability ...
- 11
2
votes
0
answers
328
views
Explicit formula for this distance between positive semi-definite matrices?
Let $A$ and $B$ in $\mathbb{R}^{d\times d}$ be positive semi-definite (psd) matrices and let $d\tau$ be the uniform probability distribution on the unit sphere $\mathbb{S}^{d-1}$ in $\mathbb{R}^d$. I ...
1
vote
0
answers
113
views
Metrics on the space of distributions in terms of p.d.fs
If two probability distributions (on the same measure space) are s.t they have p.d.fs and the $L^1$ distance between the p.d.f.s is large, then is there a choice of a ``nice" metric $d_{\rm ...
- 2,246
1
vote
0
answers
56
views
Lax CD(K, $\infty)$ space in the sense of Sturm
In K.T. Sturm's "On the geometry of metric measure spaces. I", Definition 4.5, he introduces a "lax" version of the usual CD(K,$\infty$) lower bound. Namely, one allows for $\...
- 660
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
7
votes
0
answers
433
views
(geodesic) smoothness of f-divergence with respect to the Wasserstein metric
We consider the f-divergence, which takes the form
$$
D_f(P \| Q) = \int_\Omega f\left(\frac{dP}{dQ}\right) dQ.
$$
For example, when $f(t) = t \log t$, we obtain the KL-divergence.
My question is ...
- 1,127
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
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
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
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
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
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
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
2
votes
0
answers
146
views
Prove the equicontinuity of a maximizing sequence
Let $X$ be a compact subset of $\mathbb{R}$ and $c(x_1,x_2,x_3,x_4)$ be a fixed bounded continuous functions on $X^4$. Assume $\mu,\nu$ are probability measures on $X^2$, and $\mu\otimes\nu$ is the ...
- 323
1
vote
1
answer
163
views
Metric 1-current decomposition
I've been reading Paolini-Stepanov arcticle and in section 4, at page 6, they define a metric current from a transport:
$$T_{\eta}(\omega)=\int_{\Theta}[[\theta]](\omega)d\eta(\theta),$$
which ...
- 391
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, ...
- 565
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
3
votes
1
answer
170
views
Reformulation as optimization on probability distributions
This is a "soft" question, in the sense that I'm looking for historical remarks and general commentary rather than a definite answer.
For compact $X \in R^n$ and $f : R^n \to R$ consider the problem
...
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
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
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
4
votes
0
answers
187
views
Transport Distance between Level Sets of a Convex Function
Suppose I have a well-behaved, strictly convex function $f : \mathbf{R}^d \to [0, \infty)$, and assume that $f$ has its unique minimiser at $x = 0$, with $f(0) = 0$.
For $y > 0$, I define the ...
- 801
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
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
1
vote
0
answers
176
views
Rate of convergence of empirical distribution with respect to Wasserstein distance induced by binary cost function
Let $\mathcal X=(\mathcal X, d)$ be a Polish space (i.e complete metric space), and let $\Omega$ be a non-empty subset. Consider the binary cost function $c_\Omega$ on $\mathcal X^2$ defined by $c_\...
- 6,853
1
vote
0
answers
81
views
Empirical estimation of $\inf_{\gamma \in \Pi(\mu,\nu)}\gamma(\Omega)$, given i.i.d samples from $\mu$ and $\nu$
Let $\mathcal X$ be a Polish space and $\Omega \subseteq \mathcal X^2$ be open. Let $\mu$ and $\nu$ be probability measures, and consider the quantity $c_\Omega(\mu,\nu)$ defined by
$$
c_\Omega(\mu,\...
- 6,853
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
0
votes
0
answers
75
views
Optimizer of a semi-discrete optimal transport problem
Provided two probability distributions $\mu(dx)=\rho(x)dx$ and $\nu(dx)=\sum_{i=1}^n p_i\delta_{y_i}(dx)$ that are supported on some measurable set $\Omega\subset\mathbb R^d$, we consider the semi-...
user128095
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
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
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
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
1
vote
0
answers
97
views
Dependency of the Wasserstein metric on its parameters
Let the population on some region $\Omega\subset\mathbb R^d$ be modeled by a density function $\rho:\Omega\to (0,+\infty)$. Provided $n\ge 1$ food trucks labeled by their capacity $p_1,\ldots, p_n\in (...
user128095
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
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
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
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
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
1
vote
0
answers
60
views
Euler-Lagrange Equation for Kantorovich Dual Problem
Given two probability measures $\mu$ and $\nu$, the Kantorovich Dual problem for quadratic cost is to
$$
\text{minimize} \quad \int \phi(x)d\mu + \int \psi(y)d\nu
$$
over pairs $(\phi,\psi)\in L^1(d\...
- 325
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
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
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
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
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
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
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