MathOverflow

Questions tagged [optimal-transportation]

Ask Question

The tag has no usage guidance.

102 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
4
votes
0answers
81 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 ...
0
votes
0answers
34 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 smooth}$ ...
2
votes
1answer
85 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 ...
4
votes
1answer
119 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 ...
2
votes
0answers
41 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 ...
1
vote
0answers
61 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
0answers
121 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 ...
2
votes
1answer
82 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 ...
0
votes
0answers
41 views

When a unique solution is found for a matrix of unknown coefficients, A, that have infinite solutions? How to optimise trace(A) s.t. row sum 1?

Let $\boldsymbol{A}_{(n\times n)}=[a_{ij}]$ be a square matrix such that the sum of each row is 1 and $a_{ij}\ge0$$(i=1,2,\dots,n~\text{and}~j=1,2,\dots,n)$ are unknown. Suppose that $\boldsymbol{b}_{...
0
votes
0answers
93 views

Upper-bound on optimal transport distance between uniform distribution on balls in metric space

Context: I'm studying the so-called "Ollivier-Ricci curvature theory" (e.g see this ref). I'm particularly interested with how concentration of measure (in particular, in the sense of the Otto-Villani ...
2
votes
0answers
52 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 ...
0
votes
0answers
40 views

Jump process with marginals given by a curve of probability distributions?

I am trying to understand section 2.2. in this paper: https://arxiv.org/pdf/1807.04404.pdf The set up is the following: $X$ is a finite metric space. There is a (differentiable?) path $p(t) \in \...
0
votes
1answer
220 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}^{+...
0
votes
1answer
116 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~\...
0
votes
0answers
58 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 ...
0
votes
0answers
107 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 ...
5
votes
1answer
257 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,...
3
votes
2answers
280 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 ...
0
votes
0answers
43 views

Bounded total-variation distance between distorted idstributions in Banach space

Let $\mathcal X$ be a Banach space (assumed to be Polish, if needed). For $r \ge 0$ and $x \in \mathcal X$, let $\mathbb R_r(x)$ be the closed ball of radius $r$ around $x$. Let $\mathcal A \subseteq \...
0
votes
1answer
123 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\...
1
vote
0answers
61 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,\...
0
votes
0answers
61 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-...
1
vote
0answers
71 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_\...
3
votes
1answer
111 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 ...
1
vote
2answers
413 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 ...
3
votes
1answer
89 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
1answer
106 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\...
6
votes
1answer
347 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: \...
5
votes
1answer
167 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 ...
1
vote
0answers
35 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\...
1
vote
0answers
72 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 (...
4
votes
1answer
134 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$ ...
1
vote
1answer
91 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 ...
4
votes
1answer
359 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 \{+\...
7
votes
1answer
284 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 ...
1
vote
1answer
113 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 ...
1
vote
2answers
121 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 \...
0
votes
0answers
57 views

Closure Wasserstein for pointmasses

Suppose that $(X,d)$ is a metric space which is (not necessarily) complete and let $W_1(X)$ denote the Wasserstein metric space on $(X,d)$. Let $\{\delta_x\}_{x \in K}$ is a collection of degenerate ...
2
votes
1answer
172 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 ...
4
votes
0answers
106 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 ...
2
votes
1answer
420 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 ...
2
votes
1answer
164 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(...
7
votes
0answers
266 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 ...
3
votes
0answers
84 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| \...
5
votes
0answers
224 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, ...
0
votes
0answers
91 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 ...
3
votes
1answer
187 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 ...
1
vote
0answers
156 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}(...
1
vote
1answer
117 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$ ...
0
votes
1answer
480 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_{\...

1
2 3