Questions tagged [optimal-transportation]
The optimal-transportation tag has no usage guidance.
260 questions
1
vote
1
answer
1k
views
Closed-form upper-bounds for Wasserstein distance between finite measures
Let $x_1,\dots,x_n,y_1,\dots,y_n\in \mathbb{R}$ and such that $x_i\neq x_j$ and $y_i\neq y_j$ if $i\neq j$. Let $a,b$ be elements of the probability n-simplex. Define the measures $\mu\triangleq \...
- 5,405
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
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
3
votes
2
answers
336
views
Invertibility of neural network as operator on Wasserstein space
Question statement: Consider the space of probability measures with finite second moments $P_2(\mathbb{R}^d)$, which is equipped with the Wasserstein-2 distance $W_2$, and the square integrable ...
- 1,127
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
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
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
7
votes
1
answer
504
views
Stability of displacement interpolation in optimal transport
Let $(X,d)$ be a complete separable metric space, and let $(\mathcal{P}_2 (X), W_2)$ be the space of probability measures on $X$ with finite second moments, equipped with the 2-Wasserstein distance. ...
- 660
14
votes
2
answers
892
views
Do distance functionals separate probability measures?
Let $(\Omega,d)$ be a compact metric space and $\mathcal P(\Omega)$ its space of Borel probability measures. Let $D=\{ d_p\mid p\in\Omega\}$ where $d_p(x)=d(p,x)$ be the set of all "distance ...
- 459
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
3
votes
1
answer
987
views
About the metrizability of the space of Probability measures $\mathcal{P}(S)$
It is often proved in Books that the space of Probability measures $\mathcal{P}(S)$ on a Polish metric space $(S,\rho)$ endowed with the weak/narrow topology induced by declaring it to be be the ...
- 309
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
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
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
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
9
votes
2
answers
778
views
Heat flow, decay of the Fisher information, and $\lambda$-displacement convexity
In the whole post I will work in the flat torus $\mathbb T^d=\mathbb R^d/\mathbb Z^d$ and $\rho$ will stand for any probability measure $\mathcal P(\mathbb T^d)$. This question is strongly related to ...
- 5,380
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
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 ...
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
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
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
719
views
Transport of measure
Let's disintegrate $\mu$ and $\nu$, two probabilities on $\mathbb{R}^{d}$ , according to
$$
\pi_{k} (x_{1},...,x_{d}) = (x_{k},...,x_{d})
$$
We get a family of measures and each measure $\mu_{k,d}^{+...
- 179
0
votes
1
answer
406
views
Computing discrete optimal transport
I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...
- 133
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 ...
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
6
votes
2
answers
763
views
How to control Wasserstein distance in terms of characteristic function
Let $\mathcal P(\Omega)$ be the set of probability measures supported on some compact subset $\Omega\subset\mathbb R^d$. For $\mu\in\mathcal P(\Omega)$, denote by $F_{\mu}$ its characteristic function,...
user128095
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
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
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
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
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
2
votes
1
answer
570
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
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
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
...
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
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
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
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
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
8
votes
1
answer
726
views
First variation in $L^2$ sense of the square of the Wasserstein metric
Let me consider the functional $\mathcal{F}(\rho)=\mathcal{W}_2^2(\mu,\rho)$ defined in in the space of absolutely continuous probability measures $\mathcal{P}_{ac,2}(\Omega)$, where $\mathcal{W}_2^2$ ...
- 145
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
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
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
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
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
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
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
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
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
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