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$
  • $\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$ – Martin Kell Nov 29 '18 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$ – Morino_Hikari Nov 29 '18 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$ – Martin Kell Nov 29 '18 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$ – Morino_Hikari Nov 29 '18 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$ – Morino_Hikari Nov 29 '18 at 14:20
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
    $\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 '20 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 '20 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.