3
$\begingroup$

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 Optimal Transport Theory (As far as I know, it hardly is)

The observation is as follows (which has been validated with some toy simulations).

==================================================================

Problem (not rigorously stated)

Let $\mu, \nu$ probabilistic measures on regular manifolds $\mathcal{M}, \mathcal{N}$, $C^{\infty}(\mathcal{M}, \mathcal{N})$ the set of continuous mapping from $\mathcal{M}$ to $\mathcal{N}$, and $\Pi(\mu,\nu)$ the set of measures on $\mathcal{M}\times\mathcal{N}$ s.t. its marginal distributions are respectively $\mu, \nu$.

Consider the following optimization problem

$$ (*) = \min_{T\in{C^{\infty}(\mathcal{M}, \mathcal{N})}} \inf_{\gamma\in\Pi(\mu,\nu)} \int d^{2}(T(p), q) d\gamma(p,q) $$ where the cost function can be considered as the $L_2$ distance on $\mathcal{N}$'s total space as a real vector space.

My question is that whether $(*) \propto h(\chi(\mathcal{M}), \chi(\mathcal{N}))$ where $h$ is certain metric function and $\chi(\cdot)$ denotes Euler characteristic. Generally, would it be possible that the minimum cost of the Wasserstein game is deeply related with the difference between some topological invariants of underlying manifolds'?

==================================================================

Look forward to any feedbacks and welcome discussions and potential references :D. I am willing to provide details of my toy experiments if one is interested in this problem.

$\endgroup$
12
  • $\begingroup$ (1) Which cost function are you thinking off? (2) As there is lots of choice for $T$ the answer seems to be $(*) = \inf_{S:\mathcal{N}\to\mathcal{N} \int c(S(y),y)d\nu(y)$ if the dimensions of the manifolds agree. $\endgroup$ Nov 29, 2018 at 13:24
  • $\begingroup$ For (1), em.. I am thinking about a general form of $h$ since I am not sure if anyone has seen a similar formulation before. Concretely, we can view $c$ as the geodesic distance on $\mathcal{N}$ if it is Riemannian. $\endgroup$ Nov 29, 2018 at 13:29
  • $\begingroup$ Your problem does not demand continuous transport of $\mu$ to $\nu$. Any coupling and any continuous/smooth $T$ would do. Hence let $T(r,s)=s$ where $D^1$ is the unit disk and $S^1$ is parametrized by $[-1,1)$. The push-forward is a absolutely continuous measure on the circle with density having a bump at $0$ and being zero at $\pm 1$. It's even possible to find a continuous map such that the push forward is exactly the uniform measure on $S^1$. Choose a coupling concentrated on $\{ (r,s,s) | r,s \in [-1,1]\}$. Problems arise if $\dim \mathcal{M} < \dim \mathcal{N}$. $\endgroup$ Nov 29, 2018 at 13:52
  • $\begingroup$ Oh, I see. Thanks for your swift feedbacks!And I have also considered a non-uniform case on two-dimension where $\mu = p\delta_{0} + (1-p)\text{Unif}(D^{1})$ and $\nu = \text{Unif}(S^{1})$ as I thought the negligible measure at point $(0,0)$ would make the conjectured 'topological obstruction' covered up by integral. And with experiments, I found out that even a small $p$ would make the transportation cost un-vanishing. By the way, have you ever read about some similar issues in recent literature? Since as far as I known, mathematician would not include the $T$ term in their setting. $\endgroup$ Nov 29, 2018 at 14:02
  • $\begingroup$ And I thought the simplification you made in the first reply is based on the existence of T that push $\mu$ forward to $\nu$, which is however not obvious to me... $\endgroup$ Nov 29, 2018 at 14:20

2 Answers 2

2
$\begingroup$

Applications of OT to Algebraic Topology was the subject of my thesis available here https://github.com/jhmartel/Thesis2019

There remains many interesting questions to solve!

I found the topology of either source or target space was encoded in the topology of the singularity $Z$ of certain $c$-optimal transports from source $(X, \sigma)$ to target $(Y, \tau)$.

In case $Y=\partial X$ , we found the singularity $Z$ had the homotopy type of $Y$ if the cost was attractive (like quadratic cost $c=d^2/2$) and had the homotopy type of $X$ when the cost $c$ was repulsive (see above thesis). We described general technique for building strong deformation retracts in either case. (The argument depends on studying ``gradient flow to poles" defined by the dual Kantorovich $c$-concave potentials and not to zeros, which we found more useful and not requiring any Lowasiejicz type inequalities...).

Topology of $X,Y$ apparently controls the topology of singularities, i.e. nontrivial topology tends to force discontinuous optimal transports.

For example, one can prove the following: If $X=D^2$ unit disk, with boundary $Y=\partial X=S^1$, and if $X,Y$ are equipped with canonical volume measures $\sigma$, $\tau$ satisfying $\int_X \sigma\int_Y\tau$, and if $c: X\times Y\to \mathbb{R}$ is a repulsive cost (satisfying standard (Twist) property and nondegeneracy), then the singularity $Z$ of $c$-optimal transports has the homotopy type of the source $(X,\sigma)$. Therefore $Z$ is nonempty and has exactly one connected component. E.g., $Z$ cannot consist of two discrete points.

If rather we assume the cost $c$ is attractive (e.g. quadratic cost $c=d^2/2$), then the singularity $Z$ does not have the homotopy type of $X$, but is homotopic to an ``image" of the homotopy type of $Y$. Frequently the image is degenerate and $Z$ is empty, i.e. the optimal transport is regular and single-valued everywhere.


Numerically I don't think there are any relations between Wasserstein distances (the positive real numbers found by minimal averaged squared distance of all couplings) and the topological integers or $\mathbb{R}$-valued invariants arising from (co)homology, e.g. volume, Euler characteristic, Betti numbers, etc..

However there definitely appears to be relation between the singularities of $c$-optimal transports for repulsive costs and their homological invariants. The idea is that the singularities of $c$-optimal transports are best defined by Kantorovich's contravariant singularity functor $Z=Z(c, \sigma, \tau):2^Y \to 2^X$, where $Z(Y_I):=\cap_{y\in Y_I} \partial ^c \psi(y)$, where $\partial ^c \psi$ is the $c$-subdifferential of the $c$-concave potential $\psi=\psi(y)$ arising from dual maximization program. The functor gives a $Y$-parameter cellulation of $X$, where the cells are the $c$-subdifferentials. When the cost $c$ is repulsive, then typically alot of the inclusions $Z(Y_J) \hookrightarrow Z(Y_I)$ are strong deformation retracts for subsets $Y_I \hookrightarrow Y_J$ of $Y$. This leads to a large codimension subset $Z_J$ for which $Z_J \hookrightarrow X$ is a strong deformation retract and $\dim(Z_J)=\dim(X)-j+1$. In this way we construct souls/spines of the source $X$ in the singularity of optimal transports.

There's much more to say, and it's very interesting question. I have several ongoing projects applying OT to Algebraic Topology. In fact, OT naturally leads to topology via the ideas of Dold-Thom Theorem, especially when we study the homotopy groups of ``electro neutral configurations", which is the additive abelian group of all finitely supported distributions $f=\sum n_x .x$, where $n_x\in \mathbb{Z}$ and $x\in X$ satisfying $\sum n_x=0$.

$\endgroup$
0
$\begingroup$

As for me, two trivial cases currently can be safely stated.

1. If $\mathcal{M}$ is $C^{\infty}$-diffeomorphic to $\mathcal{N}$, then $(*) = 0$.

2. In the toy case between $D^{1}$ and $S^{1}$, where $d\mu = p\delta_{0} + (1-p)d\text{Unif}_{D^{1}}$ and $d\nu = d\text{Unif}_{S^{1}}$, $ (*) = p\inf\int{d^{2}(y_{0}, y)}d\nu(y)$ exactly, since one can always construct a $C^{\infty}$-diffeomorphism from $D^{1}\backslash{\{(0,0)\}}$ to $S^{1}$.

Since $\beta_{1}(D^{1}) = 0$, $\beta_{1}(S^{1}) = 1$, $\beta_{1}(D^{1}\backslash{\{(0,0)\}}) = 0$, is there some possible relation between the different betti numbers and the non-vanishing $(*)$ in the toy case?

$\endgroup$
2
  • 2
    $\begingroup$ The notation $D^1$ for the unit disk is not very pleasant. Perhaps just $D$. Superscripts are usually for dimensions. I don't agree that the punctured unit disk is diffeomorphic to the circle. $\endgroup$
    – Ben McKay
    May 24, 2020 at 12:34
  • $\begingroup$ As noticed in the other comment, punctured disk and circle are not diffeomorphic. Also, the first Betti number of the punctured disk is not zero (if I understand correctly, what you denote by $D^1$ is the unit disk). $\endgroup$
    – Qfwfq
    May 24, 2020 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.