# Subspace Detours Meet Gromov-Wasserstein
## 3 Subspace Detours for \(Gw\)
### Computation of Inner-GW between One-Dimensional Empirical Measures  
In practice, computing the Gromov-Wasserstein distance from samples of the distributions is costly. From a computational point of view, the subspace detour approach provides an interesting method with better computational complexity when choosing 1D subspaces. Moreover, we have the intuition than the GW problem between measures lying on smaller dimensional subspaces has a better sample complexity than between the original measures, as it is the case for the Wasserstein distance [31; 32]. Below, we show that when both \(E\) and \(F\) are one-dimensional subspaces, then the resulting GW problem between the projected measures can be solved in linear time. This will rely on a new closed-form expression of the GW problem in 1D. [PERSON] et al. [12] provided a closed-form for GW with \(c(x,x^{\prime})=\|x-x^{\prime}\|_{2}^{2}\) in one dimension between discrete measures containing the same number of points and with uniform weights. However, in our framework, the 1D projection of \(E,F\) may not have uniform weights, and we also would like to be able to compare distributions with different numbers of points. We provide in the next proposition a closed-form expression for the inner-GW problem between any unidimensional discrete probability distributions:  
Proposition 5: _Consider \(\Sigma_{n}=\{a\in\mathbb{R}_{+}^{n},\sum_{i=1}^{n}a_{i}=1\}\) the \(n\) probability simplex. For a vector \(a\in\mathbb{R}^{n}\), we denote \(a^{-}\) as the vector with values sorted decreasingly, i.e., \(a_{1}^{-}\geq\cdots\geq a_{n}^{-}\). Let \(\mu=\sum_{i=1}^{n}a_{i}\delta_{x_{i}},\
u=\sum_{j=1}^{m}b_{j}\delta_{y_{j}}\in \mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\) with \(a,b\in\Sigma_{n}\times\Sigma_{m}\). Suppose that \(x_{1}\leq\cdots\leq x_{n}\) and \(y_{1}\leq\cdots\leq y_{m}\). Consider the problem:_  
\[\min_{\gamma\in\Pi(a,b)}\sum_{ijkl}(x_{i}x_{k}-y_{j}y_{l})^{2}\gamma_{ij}\gamma _{kl} \tag{8}\]  
_Then, there exists \(\gamma\in\{NW(a,b),NW(a^{-},b)\}\) such that \(\gamma\) is an optimal solution of (8) where \(NW\) is the North-West corner rule defined in Algorithm 1. As a corollary, an optimal solution of (8) can be found in \(O(n+m)\)._  
```
\(a\in\Sigma_{n},b\in\Sigma_{m}\) while\(i<=n,j<=m\)do \(\gamma_{ij}=\min\{a_{i},b_{j}\}\) \(a_{i}=a_{i}-\gamma_{ij}\) \(b_{j}=b_{j}-\gamma_{ij}\)  If \(a_{i}=0\), \(i=i+1\), if \(b_{j}=0\), \(j=j+1\) endwhile return\(\gamma\in\Pi(a,b)\)
```  
**Algorithm 1** North-West corner rule \(NW(a,b)\)Proof. : Let \(\gamma\in\Pi(a,b)\). Then:  
\[\sum_{ijkl}(x_{i}x_{k}-y_{j}y_{l})^{2}\gamma_{ij}\gamma_{kl}=\sum_{ijkl}(x_{i}x_{k })^{2}\gamma_{ij}\gamma_{kl}+\sum_{ijkl}(y_{j}y_{l})^{2}\gamma_{ij}\gamma_{kl}- 2\sum_{ijkl}x_{i}x_{k}y_{j}y_{l}\gamma_{ij}\gamma_{kl}\]  
However, \(\sum_{ijkl}(x_{i}x_{k})^{2}\gamma_{ij}\gamma_{kl}=\sum_{ik}(x_{i}x_{k})^{2}a_{ i}a_{k}\), and \(\sum_{ijkl}(y_{j}y_{l})^{2}\gamma_{ij}\gamma_{kl}=\sum_{ji}(y_{j}y_{l})^{2}b_{ j}b_{l}\), so this does not depend on \(\gamma\). Moreover \(2\sum_{ijkl}x_{i}x_{k}y_{j}y_{l}\gamma_{ij}\gamma_{kl}=2(\sum_{ij}x_{i}y_{j} \gamma_{ij})^{2}\). Hence, the problem (8) is equivalent to \(\max_{\gamma\in\Pi(a,b)}(\sum_{ij}x_{i}y_{j}\gamma_{ij})^{2}\) (in terms of the OT plan), which is also equivalent to solving \(\max_{\gamma\in\Pi(a,b)}|\sum_{ij}x_{i}y_{j}\gamma_{ij}|\) or equivalently:  
\[\max_{\gamma\in\Pi(a,b)}\pm 1\sum_{ij}x_{i}y_{j}\gamma_{ij} \tag{9}\]  
We have two cases to consider: If \(\pm 1=1\), we have to solve \(-\min_{\gamma\in\Pi(a,b)}\sum_{ij}(-x_{i})y_{j}\gamma_{ij}\). Since the points are sorted, the matrix \(c_{ij}=-x_{i}y_{j}\) satisfies the Monge property [33]:  
\[\forall(i,j)\in\{1,\dots,n-1\}\times\{1,\dots,m-1\},\ c_{i,j}+c_{i+1,j+1}\leq c _{i+1,j}+c_{i,j+1} \tag{10}\]  
To see this, check that:  
\[ \begin{split}&(-x_{i})y_{j}+(-x_{i+1})y_{j+1}-(-x_{i+1})y_{j}-(-x _{i})y_{j+1}\\ &=(-x_{i})(y_{j}-y_{j+1})+(-x_{i+1})(y_{j+1}-y_{j})=(y_{j}-y_{j+1 })(x_{i+1}-x_{i})\leq 0\end{split}