Joint Metric Space Embedding by Unbalanced OT with Gromov–-Wasserstein Marginal Penalization Florian Beier, Moritz Piening, Robert Beinert, Gabriele Steidl Abstract We propose a new approach for unsupervised alignment of heterogeneous datasets, which maps data from two different domains without any known correspondences to a common metric space. Our method is based on an unbalanced optimal transport problem with Gromov–Wasserstein marginal penalization. It can be seen as a counterpart to the recently introduced joint multidimensional scaling method. We prove that there exists a minimizer of our functional and that for penalization parameters going to infinity, the corresponding sequence of minimizers converges to a minimizer of the so-called embedded Wasserstein distance. Our model can be reformulated as a quadratic, multi-marginal, unbalanced optimal transport problem, for which a bi-convex relaxation admits a numerical solver via block-coordinate descent. We provide numerical examples for joint embeddings in Euclidean as well as non-Euclidean spaces. † † affiliationnotice: Equal contribution 1 Introduction The comparison of heterogeneous data distributions is a fundamental task in computer vision, computational biology and machine learning. Most existing approaches rely on using a suitable ground cost function such as an available metric. A classic example is the Wasserstein distance which seeks an optimal transport (OT) between two given distributions. However, often the given distributions are in heterogeneous spaces, where a readily available ground cost function between these spaces does not generally exist. Additional effort may be required to learn appropriate cost functions ( Cuturi & Avis, 2014 ; Heitz et al., 2021 ) . However, even if there exists a natural embedding into a canonical joint metric space, this metric may not be suited to accurately gauge differences in their samples. Examples of such heterogeneous settings are, e.g., the comparison of graph- or mesh-valued data such as 3d shapes or manifolds. This paper introduces a novel framework based on OT which enables the joint comparison and visualization of heterogeneous datasets by optimally transferring them into an a-priori fixed metric space, see Figure 3 for an illustrative example. Original Aligned (a) Spherical embedding Original Aligned (b) Toroidal embedding Figure 3 : Joint (aligning) transfer of two metric spaces (gray surfaces with surface distance) to a fixed reference space, namely to the sphere and the torus by our method, where the color “yellow” corresponds to higher values, see Subsection 6.1 . 1.1 Previous Work As a first step, we highlight the most relevant contributions related to our study among the vast literature on OT and dimensionality reduction. Optimal Transport with Invariances Classical Wasserstein distances allow to compare measures on a common metric space. In specific tasks in geometry processing like shape matching, the considered measures, however, live on distinct metric spaces that incorporate the different geodesic distances on the given shapes. To address this, Gromov–Wasserstein (GW) distances are introduced ( Mémoli, 2011 ; Sturm, 2006 ) . In ( Alaya et al., 2022 ) , an approximation of GW distances is obtained by jointly embedding measures into Euclidean spaces. Furthermore, projection- and subspace-robust Wasserstein-2 distances are introduced in ( Paty & Cuturi, 2019 ) . Another approach incorporates invariance to Euclidean isometries via the Wasserstein Procrustes problem ( Grave et al., 2019 ) . This is extended to account for linear operators with bounded Schatten norms in ( Alvarez-Melis et al., 2019 ) and to Gaussian mixture applications in ( Salmona et al., 2024 ) . As outlined in Section 5 , our paper extends such invariant OT to non-Euclidean domains. Joint Dimensionality Reduction Dimensionality reduction is a core topic in machine learning enabling visualization and clustering by finding optimal low-dimensional representations of data. Classical methods like principal component analysis (PCA) ( Greenacre et al., 2022 ) and multidimensional scaling (MDS) ( Carroll & Arabie, 1998 ) preserve large variations or pairwise distances, but fail on nonlinear manifolds ( Alaya et al., 2022 ; Deng et al., 2024 ) . Nonlinear approaches, e.g., locally linear embedding ( Roweis & Saul, 2000 ) , probabilistic models, e.g., t-distributed stochastic neighbor embedding (t-SNE) ( Van der Maaten & Hinton, 2008 ) , and deep learning methods, e.g., variational autoencoders (VAEs), ( Kingma et al., 2019 ) address these challenges. As an extension, several recent methods focus on joint embeddings of heterogeneous data. Here, we are given data on two incompatible domains and are interested in simultaneous embedding. The manifold-aligning generative adversarial network ( Amodio & Krishnaswamy, 2018 ) employs a generative adversarial network for domain alignment. Maximum mean discrepancy (MMD) manifold-alignment ( Liu et al., 2019 ) balances an MMD and a distortion term. UnionCom ( Cao et al., 2020 ) leverages the generalized unsupervised manifold alignment (GUMA) ( Cui et al., 2014 ) . Single-cell alignment with optimal transport (SCOT) ( Demetci et al., 2022 ) and the partial manifold alignment algorithm ( Cao et al., 2022 ) employ GW distances. Finally, the recently proposed joint multidimensional scaling (JMDS) ( Chen et al., 2023 ) algorithm combines MDS with OT for the joint embedding of two datasets into a shared Euclidean space. Complementing this and research on non-Euclidean embeddings ( McInnes et al., 2018 ; Deng et al., 2024 ) and connections between MDS and GW ( Van Assel et al., 2024 ; Clark et al., 2025 ) , we propose a joint embedding into arbitrary metric spaces based on factored transport plans ( Forrow et al., 2019 ) and GW distances. 1.2 Contribution Our main contributions are the following: 1. Towards the aligned “embedding” of heterogeneous metric spaces into a fixed, not necessarily Euclidean space, we propose to minimize an unbalanced OT problem with a quadratic cost function, where the marginals are penalized by GW distances. This formulation seeks near-isometric joint embeddings of the inputs into a metric space, while enabling an optimal comparison in the Wasserstein distance. 2. We prove that our functional has a minimizer. Further, if its regularization parameter goes to infinity, our functional approaches the so-called “embedded Wasserstein distance” ( Salmona et al., 2024 ) . In this sense, we also refer to our model as the “relaxed embedded Wasserstein distance”. 3. For the (approximate) computation of a minimizer, we provide an equivalent formulation of our model as a quadratic, multi-marginal, unbalanced OT problem. A bi-convex relaxation enables the application of existing algorithms to solve the problem numerically. 4. We recall JMDS from the point of view of our model: while we are searching for the weight of atomic measures fixing their supports, JMDS fixes the weights and aims to find the supports of the measures. 5. Numerical experiments demonstrate the potential of our method for joint embeddings of heterogeneous data on the 2d Euclidean space, the torus, the 2-sphere and the space of 2d Gaussians with the Wasserstein distance. All proofs are given in Appendix A . 2 OT-Based Distances Given a compact metric space (Z,d_{Z}) , we denote by \mathcal{P}(Z) the space of probability measures defined on the Borel- \sigma -algebra induced by the distance d_{Z} . For two compact metric spaces Z_{1} and Z_{2} , the push-forward measure of \mu\in\mathcal{P}(Z_{1}) under a measurable map T\colon Z_{1}\to Z_{2} is denoted by T_{\sharp}\mu\coloneqq\mu\circ T^{-1}\in\mathcal{P}(Z_{2}). (1) The set of transport plans between two measures \mu_{1}\in\mathcal{P}(Z_{1}) and \mu_{2}\in\mathcal{P}(Z_{2}) is given by \Pi(\mu_{1},\mu_{2})\coloneqq\bigl\{\pi\in\mathcal{P}(Z_{1}\times Z_{2}):P_{i,\sharp}\pi=\mu_{i},\;i=1,2\bigr\}, (2) where P_{i}\colon Z_{1}\times Z_{2}\to Z_{i},(z_{1},z_{2})\mapsto z_{i} , i=1,2 , denotes the projection to the first and second component, respectively. To lift d_{Z} from Z to \mathcal{P}(Z) , we rely on the Wasserstein(-2) distance between \mu_{1},\mu_{2}\in\mathcal{P}(Z) defined by \W(\mu_{1},\mu_{2})\coloneqq\!\!\min_{\pi\in\Pi(\mu_{1},\mu_{2})}\Bigl(\!\int\limits_{Z\times Z}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi(z,z^{\prime})\!\Bigr)^{\frac{1}{2}}. (3) By \Pi_{\mathrm{o}}(\mu_{1},\mu_{2}) , we denote the set of minimizers in ( 3 ). The Wasserstein distance metricizes the weak convergence of measures, where a sequence of measures (\mu_{n})_{n\in\mathbb{N}} converges weakly to a measure \mu\in\mathcal{P}(Z) , written \mu_{n}\rightharpoonup\mu , if for every (bounded) continuous function \varphi\colon Z\to\mathbb{R} , we have \int_{Z}\varphi\,\mathrm{d}\mu_{n}\to\int_{Z}\varphi\,\mathrm{d}\mu as n\to\infty . To compare heterogeneous data via their internal geometry, we can rely on GW distances, which enables us to compare measures on different metric spaces. To highlight the connection between measures and underlying spaces, we consider metric measure spaces (mm-spaces) , which are triples \mathbb{X}=(X,d_{X},\xi) such that (X,d_{X}) is a compact metric space and \xi\in\mathcal{P}(X) . Two mm-spaces \mathbb{X}_{i}=(X_{i},d_{X_{i}},\xi_{i}) , i=1,2 , are isomorphic if there exists a bijective map I\colon\supp\xi_{1}\to\supp\xi_{2} between the supports of the measures such that I is measure-preserving , i.e., I_{\sharp}\xi_{1}=\xi_{2} , and I is an isometry , i.e., d_{X_{1}}(x_{1},x_{1}^{\prime})=d_{X_{2}}(I(x_{1}),I(x_{1}^{\prime})) for all x_{1},x_{1}^{\prime}\in\supp\xi_{1} . By [\mathbb{X}] we denote the equivalence class of all mm-spaces which are isomorphic to \mathbb{X} . Finally, if I is an isometry between two metric spaces X_{i} , i=1,2 , we write I\colon X_{1}\hookrightarrow X_{2} , and just X_{1}\hookrightarrow X_{2} if such an isometry between X_{1} and X_{2} exists. Sturm’s GW distance ( Sturm, 2006 ) between two mm-spaces \mathbb{X}_{i} , i=1,2 , is defined by \SGW(\mathbb{X}_{1},\mathbb{X}_{2})\coloneqq\!\inf\limits_{\begin{subarray}{c}(Z,d_{Z})\text{ metric space},\\ I_{i}\colon\supp\xi_{i}\hookrightarrow Z,\,i=1,2\end{subarray}}\!\W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}), where the Wasserstein distance is taken over the respective space (Z,d_{Z}) . The SGW distance seeks optimal isometric embeddings of either mm-space into a joint metric space such that their Wasserstein distance in the embedded space is minimal, see Figure 4(a) . Indeed, SGW is a metric on the equivalence classes of mm-spaces. Mémoli proposed a different GW distance, which is numerically more appealing than Sturm’s construction. For two mm-spaces \mathbb{X}_{i} , i=1,2 , Mémoli’s GW distance ( Mémoli, 2011 ) is defined by \displaystyle\GW(\mathbb{X}_{1},\mathbb{X}_{2})\coloneqq\min_{\gamma\in\Pi(\xi_{1},\xi_{2})}G_{X_{1},X_{2}}(\gamma)^{\frac{1}{2}} (4) with the quadratic GW objective \displaystyle G_{X_{1},X_{2}}(\gamma) \displaystyle\coloneqq\iint\limits_{(X_{1}\times X_{2})^{2}}\bigl(d_{X_{1}}(x_{1},x_{1}^{\prime})-d_{X_{2}}(x_{2},x_{2}^{\prime})\bigr)^{2} (5) \displaystyle\hskip 27.0pt{\times}\,\mathrm{d}\gamma(x_{1},x_{2})\,\mathrm{d}\gamma(x_{1}^{\prime},x_{2}^{\prime}). (6) The problem seeks a transport between \mathbb{X}_{1} and \mathbb{X}_{2} which minimizes the overall pairwise distance distortion, see Figure 4(b) . Both distances—SGW and GW— define a metric on the equivalence classes of mm-spaces. Furthermore, both distances induce the same topology, but SGW turns these equivalence classes into a complete metric space, while GW does not ( Sturm, 2006 ; Mémoli, 2011 ) . The later can be alleviated by embedding into a larger space and extending the GW definition accordingly ( Sturm, 2023 ) . (a) Sturm’s GW (b) Mémoli’s GW Figure 4 : Illustration of GW formulations of Sturm and Mémoli. 3 Unbalanced OT With GW Penalization Throughout this section, let (Z,d_{Z}) be a fixed compact metric space. Furthermore, let \mathbb{X}_{i}=(X_{i},d_{X_{i}},\xi_{i}) , i=1,2 , be two mm-spaces, whose measures’ support can be isometrically embedded into (Z,d_{Z}) , i.e., \supp\xi_{i}\hookrightarrow Z . For this specific setting, we relax Sturm’s GW distance to \EW(\mathbb{X}_{1},\mathbb{X}_{2})\coloneqq\inf_{\begin{subarray}{c}I_{1}\colon\supp\xi_{1}\hookrightarrow Z\\ I_{2}\colon\supp\xi_{2}\hookrightarrow Z\end{subarray}}\W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}). (7) On a certain subspace of equivalence classes of mm-spaces, this defines a metric, which we call embedded Wasserstein metric . For the specific case of Euclidean spaces X_{1} , X_{2} , and Z , this reduces to the Wasserstein Procrustes problem ( Grave et al., 2019 ) and to the “embedded Wasserstein metric” in ( Salmona et al., 2024 ) . We adopt this name. Proposition 3.1 . \EW defines a metric on the subset of isomorphic classes [(X,d_{X},\xi)] for which there exist surjective isomorphism I\colon\supp\xi\hookrightarrow Z . By the following proposition, the infimum in ( 7 ) is attained. Proposition 3.2 . Let \mathbb{X}_{i} , i=1,2 be two mm-spaces and (Z,d_{Z}) a metric space such that \supp\xi_{i}\hookrightarrow Z for i=1,2 . Then the infimum in ( 7 ) is attained. While EW relies on appropriate isometries, the following relaxation enables us to handle arbitrary mm-spaces \mathbb{X}_{i} , i=1,2 . For \lambda>0 , we consider the following GW penalized unbalanced OT problem \displaystyle\EW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2}) \displaystyle\coloneqq\inf_{\pi\in\mathcal{P}(Z\times Z)}\!\!\Big(\int_{Z\times Z}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi(z,z^{\prime}) (8) \displaystyle+\lambda\sum_{i=1}^{2}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi))\Big)^{\frac{1}{2}}. (9) By penalizing the GW terms, the marginals P_{i,\sharp}\pi\in\mathcal{P}(Z) take a form that enforces (Z,d_{Z},P_{i,\sharp}\pi) to be nearly isomorphic to the inputs \mathbb{X}_{i} , i=1,2 . Furthermore, the first term ensures that the marginals P_{i,\sharp}\pi , i=1,2 are close in the Wasserstein distance on (Z,d_{Z}) . The penalization extends EW to non-isomorphic metric spaces by considering minimum-distortion embeddings. By the following proposition, the infimum in ( 9 ) is attained. Proposition 3.3 . Let \mathbb{X}_{i} , i=1,2 be two mm-spaces and (Z,d_{Z}) a metric space. Then ( 9 ) admits a solution. As the GW penalization enforces isometry, EW in ( 7 ) becomes the limit of EW λ in ( 9 ) if \lambda goes to infinity. Proposition 3.4 . Let \mathbb{X}_{i} , i=1,2 be two mm-spaces and let (Z,d_{Z}) be a metric space such that \supp\xi_{i}\hookrightarrow Z . Let (\lambda_{n})_{n\in\mathbb{N}} be a sequence with \lambda_{n}\to\infty as n\to\infty . Then any sequence (\pi_{n})_{n\in\mathbb{N}} of minimizers of \EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2}) converges weakly, up to a subsequence, to some \pi\in\mathcal{P}(Z\times Z) . There exist isometries (I_{1},I_{2}) realizing \EW(\mathbb{X}_{1},\mathbb{X}_{2}) such that \pi\in\Pi_{\mathrm{o}}(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}) . If there exist no isometric embeddings \supp\xi_{i}\hookrightarrow Z , the limit of \EW_{\lambda} as \lambda\to\infty yields best possible approximations of \mathbb{X}_{i} on the given metric space (Z,d_{Z}) with respect to the GW distance. More precisely, a GW approximation of an mm-space \mathbb{X} on the metric space (Z,d_{Z}) is a minimizer \zeta\in\mathcal{P}(Z) of \GWA(\mathbb{X})\coloneqq\min_{\zeta\in\mathcal{P}(Z)}\GW^{2}(\mathbb{X},(Z,d_{Z},\zeta)). (10) For discrete mm-spaces, GW approximations are studied in ( Clark et al., 2025 ) and are closely related to MDS. Proposition 3.5 . Let \mathbb{X}_{i} , i=1,2 , be two mm-spaces and let (Z,d_{Z}) be a metric space. Let (\lambda_{n})_{n\in\mathbb{N}} be a sequence with \lambda_{n}\to\infty as n\to\infty . Then any sequence (\pi_{n})_{n\in\mathbb{N}} of minimizers of \EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2}) converges weakly, up to a subsequence, to \pi\in\Pi(\zeta_{1},\zeta_{2}) , where \zeta_{i}\in\mathcal{P}(Z) is a GW approximation of \mathbb{X}_{i} . On the other side, if \lambda\to 0 , the influence of the Wasserstein term in \EW_{\lambda} increases. Figuratively, the marginals P_{1,\sharp}\pi and P_{2,\sharp}\pi of the minimizers \pi of \EW_{\lambda} have to become more similar if \lambda goes to zero. In the limit case, when both marginals coincide, we obtain a fixed-support GW barycenter ( Beier et al., 2023 ) . In detail, a fixed-support GW barycenter on the metric space (Z,d_{Z}) is a minimizer \zeta\in\mathcal{P}(Z) of \GWB(\mathbb{X}_{1},\mathbb{X}_{2})\coloneqq\min_{\zeta\in\mathcal{P}(Z)}\sum_{i=1}^{2}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},\zeta)). (11) Proposition 3.6 . Let \mathbb{X}_{i} , i=1,2 , be two mm-spaces and let (Z,d_{Z}) be a metric space. Let (\lambda_{n})_{n\in\mathbb{N}} be a sequence with \lambda_{n}\to 0 as n\to\infty . Then any sequence (\pi_{n})_{n\in\mathbb{N}} of minimizers of \EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2}) converges weakly, up to a subsequence, to (\Id,\Id)_{\sharp}\zeta , where \zeta\in\mathcal{P}(Z) is a fixed-support GW barycenter. In the rest of the paper, we skip the integration domains of the integrals for better readability, since they are clear from the context. Then, by definition of the GW distance, EW λ in ( 9 ) can be rewritten as \displaystyle\EW_{\lambda}^{2}(\mathbb{X}_{1},\mathbb{X}_{2})=\inf\limits_{\pi\in\mathcal{P}(Z\times Z)}\inf\limits_{\begin{subarray}{c}\gamma_{i}\in\Pi(\xi_{i},P_{Z,\sharp}\pi)\\ i=1,2\end{subarray}} (12) \displaystyle\int d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi(z,z^{\prime})+\lambda\big(G_{X_{1},Z}(\gamma_{1})+G_{X_{2},Z}(\gamma_{2})\big)\,\,\,\,\, (13) or equivalently as \displaystyle\EW_{\lambda}^{2}(\mathbb{X}_{1},\mathbb{X}_{2})=\inf\limits_{\mu_{1},\mu_{2}\in\mathcal{P}(Z)}\inf\limits_{\pi\in\Pi(\mu_{1},\mu_{2})}\inf\limits_{\begin{subarray}{c}\gamma_{i}\in\Pi(\xi_{i},\mu_{i})\\ i=1,2\end{subarray}} (14) \displaystyle\int d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi(z,z^{\prime})+\lambda\big(G_{X_{1},Z}(\gamma_{1})+G_{X_{2},Z}(\gamma_{2})\big).\,\,\, (15) Figure 5 : Illustration of our multi-marginal transport problem. The colors are in line with Figure 4 : quantities with respect to \mathbb{X}_{1} are red, and quantities related to \mathbb{X}_{2} are blue. For computing EW λ , we will rewrite the term by 4-plans. To this end, we use the notation Z_{1}=Z_{2}\coloneqq Z and denote the projection onto X_{i} , Z_{i} by P_{X_{i}},P_{Z_{i}} , respectively. Now we consider 4-plans \alpha\in\mathcal{P}(X_{1},Z_{1},Z_{2},X_{2}) fulfilling P_{X_{i},\sharp}\alpha=\xi_{i} , i=1,2 . Let \pi\coloneqq P_{Z_{1}\times Z_{2},\sharp}\alpha\quad\text{and}\quad\gamma_{i}\coloneqq P_{X_{i}\times Z_{i},\sharp}\alpha,\;i=1,2. (16) Clearly, such plans automatically fulfill P_{Z_{i},\sharp}\pi=P_{Z_{i},\sharp}\gamma_{i},\;i=1,2 see Figure 5 . Thus, ( 13 ) can be reformulated as a quadratic, multi-marginal, unbalanced OT problem \displaystyle\EW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2})=\inf_{\begin{subarray}{c}\alpha\in\mathcal{P}(X_{1}\times Z_{1}\times Z_{2}\times X_{2})\\ P_{X_{i},\sharp}\alpha=\xi_{i},i=1,2\end{subarray}}F_{\lambda}(\alpha)^{\frac{1}{2}} (17) with the quadratic objective \displaystyle F_{\lambda}(\alpha) \displaystyle\coloneqq\iint\frac{1}{2}\bigl(d_{Z}^{2}(z_{1},z_{2})+d_{Z}^{2}(z_{1}^{\prime},z_{2}^{\prime})\bigr) (18) \displaystyle\hskip 30.0pt+\lambda\sum_{i=1}^{2}(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z_{i},z_{i}^{\prime}))^{2} (19) \displaystyle\quad\times\,\mathrm{d}\alpha(x_{1},z_{1},z_{2},x_{2})\,\mathrm{d}\alpha(x^{\prime}_{1},z^{\prime}_{1},z^{\prime}_{2},x^{\prime}_{2}). (20) We summarize our findings in the following proposition. Proposition 3.7 . If \alpha solves ( 17 ), then its projections ( 16 ) are solutions of ( 13 ) and in particular \pi is a solution of ( 9 ). Conversely, any solution of ( 9 ) can be expressed this way. In Appendix B , we illustrate relations between the Wasserstein distance, GW, EW and EW λ by numerical examples. 4 Bi-Convex Relaxation At its core, the computation of EW λ in ( 17 ) requires the solution of a quadratic optimization problem. Similar formulations appear, for instance, in the computation of the GW distance ( Peyré et al., 2016 ; Séjourné et al., 2021 ) , in the multi-marginal GW setting ( Beier et al., 2023 ) , and in CO-OT ( Vayer et al., 2020b ) . All of these quadratic OT problem have in common that they can be numerically solved using a block-coordinate descent on their bi-convex relaxations. In the following, we adapt this approach to our multi-marginal, unbalanced transport problem ( 17 ). For this, we decouple the minimization with respect to the inner and outer transport plan \gamma in the double integral of ( 17 ). More precisely, denoting the inner plan by \alpha_{1} and the outer plan by \alpha_{2} , we consider the bi-convex relaxation \inf_{\begin{subarray}{c}\alpha_{1},\alpha_{2}\in\mathcal{P}(X_{1}\times Z_{1}\times Z_{2}\times X_{2})\\ (P_{X_{i}})_{\sharp}\alpha_{k}=\xi_{i},\ i,k=1,2\end{subarray}}\mathcal{F}_{\lambda}(\alpha_{1},\alpha_{2}) (21) with the bilinear objective \displaystyle\mathcal{F}_{\lambda}(\alpha_{1},\alpha_{2}) \displaystyle\coloneqq\iint\frac{1}{2}\bigl(d_{Z}^{2}(z_{1},z_{2})+d_{Z}^{2}(z_{1}^{\prime},z_{2}^{\prime})\bigr) (22) \displaystyle\hskip 30.0pt+\lambda\sum_{i=1}^{2}(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z_{i},z_{i}^{\prime}))^{2} (23) \displaystyle\hskip 15.0pt{\times}\,\mathrm{d}\alpha_{1}(x_{1},z_{1},z_{2},x_{2})\,\mathrm{d}\alpha_{2}(x_{1}^{\prime},z_{1}^{\prime},z_{2}^{\prime},x_{2}^{\prime}). (24) By construction, the minimizers of ( 21 ) constitute a lower bound to the original, quadratic problem ( 17 ). Moreover, every bi-convex minimizer of the form \alpha_{1}=\alpha_{2} yields a minimizer of the original problem. In order to find a numerical solution, we apply block-coordinate descent, which consists of alternatively fixing \alpha_{1} and \alpha_{2} in ( 21 ) and minimizing with respect to the other argument. Fixing \alpha_{1} , it remains to solve the (linear) multi-marginal, unbalanced OT problem \displaystyle\inf_{\begin{subarray}{c}P_{X_{i},\sharp}\alpha_{2}=\xi_{i}\\ i=1,2\end{subarray}}\int c_{1}(x_{1}^{\prime},z_{1}^{\prime},z_{2}^{\prime},x_{2}^{\prime})\,\mathrm{d}\alpha_{2}(x_{1}^{\prime},z_{1}^{\prime},z_{2}^{\prime},x_{2}^{\prime}), (25) where the effective cost is given by \displaystyle c_{1}(x_{1}^{\prime},z_{1}^{\prime},z_{2}^{\prime},x_{2}^{\prime})\coloneqq\frac{1}{2}d_{Z}^{2}(z_{1}^{\prime},z_{2}^{\prime})+\lambda\sum_{i=1}^{2} (26) \displaystyle\int\bigl(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z_{i},z_{i}^{\prime})\bigr)^{2}\,\mathrm{d}\alpha_{1}(x_{1},z_{1},z_{2},x_{2}).\,\,\,\, (27) The cost function additively decouples into three partial cost functions solely depending on two coordinates of c_{1} . Unbalanced, multi-marginal OT formulations of this kind are treated in ( Beier et al., 2022 ) , where, relying on an entropic regularization, a multi-marginal Sinkhorn scheme is proposed. Mathematically, this means that, for a regularization parameter \varepsilon>0 , we approximate the minimizer of ( 25 ) by \inf_{\begin{subarray}{c}P_{X_{i},\sharp}\alpha_{2}=\xi_{i}\\ i=1,2\end{subarray}}\int c_{1}\,\mathrm{d}\alpha_{2}+\varepsilon\KL(\alpha_{2},\upsilon), (28) where \upsilon denotes the uniform measure on X_{1}\times Z_{1}\times Z_{2}\times X_{2} and KL the Kullback–Leibler divergence. More precisely, with the Radon–Nikodým derivative \,\mathrm{d}\gamma/\,\mathrm{d}\upsilon , the KL divergence is given by \KL(\gamma,\upsilon)\coloneqq\int\log(\,\mathrm{d}\gamma/\,\mathrm{d}\upsilon)\,\mathrm{d}\upsilon if \gamma\ll\upsilon and \KL(\gamma,\upsilon)\coloneqq\infty otherwise. In total, we may approximate the minimizer of the quadratic, unbalanced, multi-marginal OT problem ( 17 ) by applying Algorithm 1 . 0: \mathbb{X}_{i}=(X_{i},d_{X_{i}},\xi_{i}),\ i=1,2. (mm-spaces) 0: (Z,d_{Z}) (finite metric space) 0: \lambda>0 (penalization parameter) 0: \varepsilon>0 (regularization parameter) 1: Initialize \alpha_{1}=\alpha_{2}:=\xi_{1}\otimes\mu\otimes\mu\otimes\xi_{2} where \mu is the uniform measure on (Z,d_{Z}) 2: while not converged do 3: Compute c_{1} as in ( 27 ) 4: Update \alpha_{2} using the multi-marginal Sinkhorn scheme in ( Beier et al., 2022 ) with c_{1} 5: Compute c_{2} analogous to ( 27 ) 6: Update \alpha_{1} using the multi-marginal Sinkhorn scheme in ( Beier et al., 2022 ) with c_{2} 7: end while 7: \alpha_{1} or \alpha_{2} Algorithm 1 Computation of EW λ 5 Discrete EW λ and JMDS The distance EW in ( 7 ) generalizes Wasserstein Procrustes ( Grave et al., 2019 ) to non-Euclidean spaces, while EW λ in ( 9 ) is closely related to the JMDS model ( Chen et al., 2023 ) . In this section, we explain the relation. We consider the discrete case, where X_{1}\coloneqq\{x_{1}^{1},\ldots,x_{1}^{n_{1}}\}\quad\text{and}\quad X_{2}\coloneqq\{x_{2}^{1},\ldots,x_{2}^{n_{2}}\} are point sets equipped with dissimilarity distances d_{X_{1}} and d_{X_{2}} as well as measures \xi_{1}\coloneqq\sum_{j=1}^{n_{1}}\xi_{1}^{j}\delta_{x_{1}^{j}},\quad\xi_{2}\coloneqq\sum_{j=1}^{n_{2}}\xi_{2}^{j}\delta_{x_{2}^{j}}. Discrete EW λ fixes a discrete embedding space Z_{1}=Z_{2}=Z\coloneqq\{z^{1},\ldots,z^{m}\}. with metric d_{Z} . Accordingly, we use measures with fixed supports \mu_{i}=\sum_{j=1}^{m}\mu_{i}^{j}\delta_{z^{j}},\;\gamma_{i}=\sum_{j,k=1}^{n_{i},m}\gamma_{i}^{j,k}\delta_{x_{i}^{j},z^{k}},\;\pi=\sum_{j,k=1}^{m}\pi_{j,k}\delta_{z^{j},z^{k}}, (29) where i=1,2 . Since the supports of the measures are fixed, we can restrict ourselves to the weight matrices \bm{\mu}_{i}\in\Delta_{m} , \bm{\xi}_{i}\in\Delta_{n_{i}} , \bm{\pi}\in\Pi(\bm{\mu}_{1},\bm{\mu}_{2}) and \bm{\gamma}_{i}\in\Pi(\bm{\xi}_{i},\bm{\mu}_{i}) , i=1,2 in the corresponding probability simplicies \Delta . Then EW λ in ( 15 ) becomes the discrete minimization problem \displaystyle\EW_{\lambda}(X_{1},X_{2})=\min_{\begin{subarray}{c}\bm{\mu_{i}}\in\Delta_{m}\\ i=1,2\end{subarray}}\min_{\bm{\pi}\in\Pi(\bm{\mu}_{1},\bm{\mu}_{2})}\min_{\begin{subarray}{c}\bm{\gamma}_{i}\in\Pi(\bm{\xi}_{i},\bm{\mu}_{i})\\ i=1,2\end{subarray}}\; (30) \displaystyle\big\langle\bm{\pi},\bm{D}^{2}_{Z,Z}\big\rangle+\lambda\big(G_{X_{1},Z}(\bm{\gamma}_{1})+G_{X_{2},Z}(\bm{\gamma}_{2})\big), (31) where \bm{D}^{2}_{Z,Z}\coloneqq\big(d_{Z}^{2}(z^{j},z^{k})\big)_{j,k=1}^{m} and, for i=1,2 , \displaystyle G_{X_{i},Z}(\bm{\gamma}_{i}) (32) \displaystyle\coloneqq\sum_{j,k=1}^{n_{i},m}\sum_{r,s=1}^{n_{i},m}\gamma_{i}^{s,k}\gamma_{i}^{j,k}\big(d_{X_{1}}(x_{i}^{j},x_{i}^{r})-d_{Z}(z^{k},z^{s})\big)^{2}. (33) JMDS aims to find point sets \mathcal{Z}_{1}\coloneqq\{z_{1}^{1},\ldots,z_{1}^{n_{1}}\}\subset\mathbb{R}^{d},\quad\mathcal{Z}_{2}\coloneqq\{z_{2}^{1},\ldots,z_{2}^{n_{2}}\}\subset\mathbb{R}^{d} (34) such that the dissimilarity relations in X_{i} are approximately preserved in \mathcal{Z}_{i} , i=1,2 , while ensuring that the intermediate points are optimally aligned. Here, \mathcal{Z}_{i} , i=1,2 are exclusively in \mathbb{R}^{d} with the Euclidean metric d(x,y)=\|x-y\| . Instead of measures with fixed support, we use \mu_{i}\coloneqq\sum_{j=1}^{n_{i}}\frac{1}{n_{i}}\delta_{z_{i}^{j}},\;\pi=\sum\limits_{j,k=1}^{m}\pi_{j,k}\delta_{z_{1}^{j},z_{1}^{k}}, as well as \gamma_{i}\coloneqq\sum_{j,k=1}^{n_{i}}\gamma^{j,k}_{i}\delta_{x_{i}^{j},z_{i}^{k}}\quad\text{with}\quad\gamma^{j,k}_{i}\coloneqq\left\{\begin{array}[]{ll}\tfrac{1}{n_{i}}&j=k,\\ 0&j\not=k,\end{array}\right. and will optimize over the supports \mathcal{Z}_{i} , i=1,2 . Then ( 15 ) becomes \displaystyle\JMDS_{\lambda}(X_{1},X_{2})\coloneqq\min_{\mathcal{Z}_{1},\mathcal{Z}_{2}}\min_{\bm{\pi}\in\Pi(\frac{1}{n_{1}}\bm{1}_{n_{1}},\frac{1}{n_{2}}\bm{1}_{n_{2}})}\; (35) \displaystyle\big\langle\pi,\bm{D}^{2}_{\mathcal{Z}_{1},\mathcal{Z}_{2}}\big\rangle+\lambda\big(G_{1}(\mathcal{Z}_{1})+G_{2}(\mathcal{Z}_{2})\big), (36) where \bm{D}^{2}_{\mathcal{Z}_{1},\mathcal{Z}_{2}}\coloneqq\big(d^{2}(z_{1}^{j},z_{2}^{k})\big)_{j,k=1}^{n_{1},n_{2}} and, for i=1,2 , \displaystyle G_{i}(\mathcal{Z}_{i})\!\coloneqq\!\sum_{j,k=1}^{n_{i}}\sum_{r,s=1}^{n_{i}}\gamma^{j,k}_{i}\gamma^{r,s}_{i}\big(d_{X_{i}}(x_{i}^{j},x_{i}^{r})-d(z_{i}^{k},z_{i}^{s})\big)^{2} (37) \displaystyle\qquad\;\;=\sum_{j,k=1}^{n_{i}}\frac{1}{n_{i}^{2}}\big(d_{X_{i}}(x_{i}^{j},x_{i}^{k})-d(z_{i}^{j},z_{i}^{k})\big)^{2}. (38) This is exactly the functional proposed as JMDS in ( Chen et al., 2023 ) . Note that the Wasserstein Procrustes model is given by \min_{\bm{\pi}\in\Pi(\frac{1}{n_{1}}\bm{1}_{n_{1}},\frac{1}{n_{2}}\bm{1}_{n_{2}})}\min_{Q\in\SO(d)}\big\langle\pi,\bm{D}^{2}_{Q\mathcal{Z}_{1},\mathcal{Z}_{2}}\big\rangle. (39) This is exactly the first summand in JMDS λ , where the minimization over the special orthogonal group \SO(d) can be skipped in ( 36 ) since G_{i}(\mathcal{Z}_{i}) , i=1,2 , are invariant under orthogonal transforms. To summarize: 1. Our discrete EW λ fixes the support of the marginals \mu_{i} in ( 15 ) which results in the optimization over the weights, where JMSD fixes the weights of the \mu_{i} and optimizes over the supports. 2. Fixing the support has the advantage that we can work with arbitrary metric spaces (Z,d_{Z}) , while the “free support” approach of JMDS is restricted to the Euclidean space. 3. The minimization problems have to be tackled by completely different optimization algorithms, namely an unbalanced multimarginal Sinkhorn algorithm for the block-coordinate descent in Algorithm 1 for EW λ and the so-called SMACOF method combined with Wasserstein Procrustes minimizations ( Chen et al., 2023 ) for JMDS. 6 Numerical Results Next, we provide several proof-of-concept examples 1 1 1 https://github.com/MoePien/RelaxedEmbeddedWasserstein . Additional parameter ablations are described in Supplement C . 6.1 Joint Embedding of 3d Shapes In the first example, we exploit EW λ to align and embed 3d shapes—the surfaces of objects in \mathbb{R}^{3} —into a joint space (Z,d_{Z}) . For this, we interpret a 3d shape as mm-space \mathbb{X}\coloneqq(X,d_{X},\xi) , where X is the surface, d_{X} is the surface (or geodesic) distance, and \xi is the uniform measure. Practically, X is parametrized by the vertices of a triangular mesh, d_{X} is approximated using Dijkstra’s algorithm ( Dijkstra, 1959 ) on the corresponding graph, and \xi is chosen as the discrete uniform measure. For the joint embedding of two given (discrete) shapes \mathbb{X}_{i} , i=1,2 , we compute the 4-plan \alpha in ( 17 ) using the discretization in Section 5 and Algorithm 1 . Since the relaxation behind EW λ does not yield an isometry, but only a transport plan \gamma_{i}=P_{X_{i}\times Z_{i},\sharp}\alpha , we visualize the computed relaxed embeddings by the marginals P_{Z_{i},\sharp}\gamma_{i}=P_{Z_{i},\sharp}\alpha . Bended Rectangles Shapes Ours JMDS (a) S-bended rectangle and Swiss roll (without hole). Shapes Ours JMDS (b) S-bended rectangle and Swiss roll with hole. Figure 8 : Embedding and alignment of an S-bended rectangle and a Swiss roll into \mathbb{R}^{2} . For our method, we visualize the marginals P_{Z_{i},\sharp}\alpha of the computed 4-plan \alpha in ( 17 ) and compare them with JMDS. In the second example (b), JMDS produces an unexpected hole when embedding the S-bended surface. Shapes Ours JMDS (a) Same human shape in different poses. Shapes Ours JMDS (b) Distinct human shapes in different poses. Figure 11 : Embedding and alignment of human shapes from the FAUST dataset into \mathbb{R}^{2} . For our method, we visualize the marginals P_{Z_{i},\sharp}\alpha of the computed 4-plan \alpha in ( 17 ) and compare them with JMDS. Here JMDS tends to split some of the extremities. We start by embedding an S-bended rectangle and a Swiss roll (with and without a hole) into \mathbb{R}^{2} . Intuitively, we expect that the surfaces without holes are unrolled by the relaxed embedding behind EW λ , since there actually exists isometric embeddings. For the discretization, we choose Z as an equispaced 50 \times 50 grid on [0,1.3]^{2}\subset\mathbb{R}^{2} and d_{Z} as the corresponding Euclidean distance and apply Algorithm 1 with \lambda=100 and \varepsilon=10^{-3} . In Figure 8 , the relaxed embeddings are visualized by P_{Z_{i},\sharp}\alpha , where the point sizes represent the underlying probability masses/weights. As comparison, we also show the results of JMDS with \lambda=10 and \varepsilon=10^{-3} for the incorporated regularized OT problem. Both methods produce representations that unroll the shapes and succeed in aligning the embeddings. JMDS, however, produces an unexpected hole during the alignment of the S-bended shape and the Swiss role with hole. Human Shapes Since we are not limited to isometries, we next consider an experiment where isometric embeddings are not possible. More precisely, we embed human shapes from the FAUST dataset ( Bogo et al., 2014 ) into \mathbb{R}^{2} . For this, we choose (Z,d_{Z}) as an equispaced 60 \times 60 grid on [0,1.3]^{2}\subset\mathbb{R}^{2} and apply Algorithm 1 with \lambda=100 and \varepsilon=4\cdot 10^{-4} . The obtained transport-based embeddings are shown in Figure 11 . As comparison, we apply JMDS with \lambda=10 and \varepsilon=4\cdot 10^{-4} . The 2d representations clearly resemble the 3d human shapes, but JMDS splits some of the extremities. Since our method and JMDS can both be derived from the same functional, we additionally compare the achieved objectives, the Wasserstein distances between embeddings, and the GW distances between embeddings and input spaces. The experiment is repeated for each pairwise combination of the first ten shapes from the FAUST dataset and different \lambda . For comparison, the shapes are downsampled to 35 vertices, and both methods are regularized with \varepsilon=0.001 . For our method, we set Z according to a uniform 30 \times 30 grid on [0,1.3]^{2} . Results are shown in Table 1 . In total, we here achieve better joint embeddings than JMDS both in terms of GW and Wasserstein. GW 2 W 2 Ours ( \lambda=1) 0.0057 \pm 0.004 0.017 \pm 0.007 JMDS ( \lambda=1 ) 0.0071 \pm 0.007 0.029 \pm 0.010 Ours ( \lambda=10 ) 0.0048 \pm 0.004 0.027 \pm 0.016 JMDS ( \lambda=10 ) 0.0057 \pm 0.005 0.046 \pm 0.023 Table 1 : Mean and standard deviation of GW distance (between input shapes and embeddings) and of Wasserstein distance (between both embeddings) for joint 2d embeddings of the FAUST dataset via our method and JMDS. Spherical and Toroidal Embeddings Finally, we consider the alignment of spherical and toroidal subsets, i.e., the joint embedding into a non-Euclidean space. More precisely, we consider the 3d shapes in the introductory Figure 3 . As target space (Z,d_{Z}) , we choose a 30 \times 30 grid on the canonical parametrization of the sphere \mathbb{S}(2) and the torus \mathbb{T}(2)=\mathbb{S}(1)\times\mathbb{S}(1) equipped with the corresponding geodesic distance. Using \lambda=10^{3} and \varepsilon=10^{-3} for Algorithm 1 , we embed the spherical rectangle and a spherical cap, both with a hole, onto the sphere, and the half-torus and toroidal triangle onto the torus. The relaxed embeddings are shown in Figure 3 , where the color encodes the mass of the computed marginals. Up to a smoothing due to the incorporated entropic regularization, the transport plans \gamma_{i}=P_{X_{i}\times Z_{i},\sharp}\alpha correspond to the expected isometries. 6.2 Alignment of Feature Spaces In the next example, we use our method to align different feature spaces occurring in real-world data. More precisely, we consider the genetyping—the determination of the corresponding cell class—of single cells from various measured modalities. Multimodal technologies as proposed in ( Cheow et al., 2016 ; Chen et al., 2019 ) are, however, uncommon such that there is a rising interest in embedding the corresponding features into a joint feature space ( Demetci et al., 2022 ; Liu et al., 2019 ; Chen et al., 2023 ) . Following the experiments of ( Demetci et al., 2022 ) for n single cells, our first aim is to assign the recorded features X_{1}\coloneqq\{x_{1}^{1},\dots,x_{1}^{n}\}\subset\mathbb{R}^{d_{1}} from one modality to the features X_{2}\coloneqq\{x_{2}^{1},\dots,x_{2}^{n}\}\subset\mathbb{R}^{d_{2}} of another modality, i.e., to recover the underlying one-to-one correspondence between x_{1}^{j} and x_{2}^{j} . Our second goal consists in transferring a classifier from X_{1} to X_{2} in an unsupervised manner. To achieve both goals, we apply the following methodology: 1. We equip the recorded, uncorrelated features X_{1}\subset\mathbb{R}^{d_{1}} and X_{2}\subset\mathbb{R}^{d_{2}} with specific distances d_{X_{i}} estimated with the unsupervised SCOT routine ( Demetci et al., 2022 ) . 2. We equip the constructed metric spaces with the uniform measure to obtain the mm-spaces \mathbb{X}_{i}\coloneqq(X_{i},d_{X_{i}},\xi_{i}) . 3. Fixing a 20 \times 20 grid Z\coloneqq\{z^{1},\dots,z^{m}\}\subset\mathbb{R}^{2} over [0,1]^{2} equipped with the Euclidean metric, we apply Algorithm 1 with the discretization in Section 5 to compute the 4-plan \alpha in ( 17 ). 4. Based on the transport plans \gamma_{i}\coloneqq P_{X_{i}\times Z_{i},\sharp}\alpha , we pair x_{i}^{j} with its barycentric projection \tilde{x}_{i}^{j}\in\mathbb{R}^{m} given by \tilde{x}_{i}^{j}\coloneqq\sum_{k=1}^{m}\gamma_{i}^{jk}\,z_{k}\biggm/\penalty\sum_{k=1}^{m}\gamma_{i}^{jk}. (40) For the first aim, the identification of the underlying correspondence, we identify x_{1}^{j} with x_{2}^{k} whose barycentric projection \tilde{x}_{2}^{k} is closest to \tilde{x}_{1}^{j} . To quantify the quality of the pairing, we rely on the FOSCTTM (fraction of samples closer than the true match) score ( Liu et al., 2019 ) . More precisely, FOSCTTM is defined by \frac{1}{n^{2}}\,\sum_{j=1}^{n}\#\Bigl\{k\in\{1,\dots,n\}:\lVert\tilde{x}_{1}^{j}-\tilde{x}_{2}^{k}\rVert<\lVert\tilde{x}_{1}^{j}-\tilde{x}_{2}^{j}\rVert\Bigr\} (41) and ranges from 0 (perfect identification) to 1. For the second aim, the transfer of a classifier from X_{1} to X_{2} , we exemplarily consider the k-nearest neighbor (KNN) method. More precisely, we use the barycentric projections \{\tilde{x}_{1}^{1},\dots,\tilde{x}_{1}^{n}\} and the corresponding gene type labels of the first modality to classify a feature x_{2}^{k} (more exact \tilde{x}_{2}^{k} ) from the second modality, where we consider the closest five neighbors. Here, higher classification accuracies (KNN-Acc) indicate better class alignments. Ours JMDS (a) SNAREseq dataset Ours JMDS (b) scGEM dataset Figure 14 : Joint embedding of two feature spaces into \mathbb{R}^{2} using our method and JMDS (Top: first feature space, Bottom: second feature space). Both methods align the color-coded classes. SNAREseq scGEM FOSCTTM \downarrow KNN-Acc \uparrow Time FOSCTTM \downarrow KNN-Acc \uparrow Time {\EW}_{\lambda} (Ours) 0.165 0.943 28.9s 0.208 0.610 1.7s JMDS ( Chen et al., 2023 ) 0.219 0.872 8.7s 0.230 0.616 0.3s SCOT ( Demetci et al., 2022 ) 0.402 0.447 76.7s 0.247 0.578 17.6s UnionCom ( Cao et al., 2020 ) 0.436 0.380 90.6s 0.392 0.465 1.5s Table 2 : Comparison of the joint embedding of two feature spaces into \mathbb{R}^{2} using our method, JMDS, SCOT, and UnionCom. For the experiments, we employ the publicly available datasets 2 2 2 https://rsinghlab.github.io/SCOT/data/ from ( Demetci et al., 2022 ) , where SNAREseq consists of d_{1}=19 and d_{2}=10 features of n=1047 single cells, and scGEM of d_{1}=34 and d_{2}=27 features of n=177 specimens. The computed embedding of X_{i} into \mathbb{R}^{2} of our method and JMDS are visualized in Figure 14 . For FOSCTTM and KKN-Acc, we additionally compare both methods with the alignment techniques UnionCom ( Cao et al., 2020 ) and SCOT ( Demetci et al., 2022 ) using the same distances on X_{i} . Note that UnionCom relies on GUMA and t-SNE, whereas SCOT relies on GW and MDS. The results are recorded in Table 2 . The hyperparameters of all methods are chosen according to a grid search minimizing the FOSCTTM on a 10% validation split, see Supplement D . A further experiment with different feature spaces for MNIST and FashionMNIST is given in Supplement E . 6.3 Alignment of Gaussian Mixture Models In the final example, inspired by ( Salmona et al., 2024 ) , we want to align Gaussian mixture models (GMMs). For this, we consider the space of 2d Gaussians \mathcal{N}_{2}=\{\mathcal{N}(\mu,\Sigma)|\mu\in\mathbb{R}^{2},\Sigma\in\mathbb{R}^{2\times 2}\text{ spd.}\} equipped with the Wasserstein distance, which yields a non-Euclidean geometry . A GMM can now be interpreted as mm-space \mathbb{X}=(\mathcal{N}_{2},\W,\xi) with discrete measure \xi\coloneqq\sum_{j=1}^{n_{1}}\xi_{j}\,\delta_{\mu_{j},\Sigma_{j}} . For the experiment, we fit two GMMs to affine-transformed 2d datasets using the expectation-maximization algorithm. Here, we employ the datasets “Blobs” and “Moons” from scikit-learn ( Pedregosa et al., 2011 ) , see Figure 17 . For the alignment of the GMMs, we choose Z\subset\mathcal{N}_{2} , where the means form a 15 \times 15 grid over [0,1]^{2} and we use a coarse grid over suitable matrices. Particularly, we consider matrices \Sigma=r^{2}\begin{bmatrix}\sigma_{1}^{2}&\sigma_{12}\\ \sigma_{12}&\sigma_{2}^{2}\end{bmatrix}, (42) where we choose \sigma_{1}^{2},\sigma_{2}^{2}\in\{0.8,1.\} and \sigma_{12}\in\{-0.2,0.,0.2\} . The parameter r^{2}>0 corresponds to the mean variance of the considered GMMs. Applying Algorithm 1 to compute \alpha in ( 17 ), and considering the marginals \zeta_{i}\coloneqq P_{Z_{i},\sharp}\alpha , which are again discrete measures on \mathcal{N}_{2} , we obtain the aligned GMMs in Figure 17 . Original Aligned (a) Tri-modal GMM Original Aligned (b) “Moons” GMM Figure 17 : Alignment of GMMs with respect to the Wasserstein distance. The considered and computed GMMs are visualized via their density function on \mathbb{R}^{2} . 7 Conclusion We propose an unbalanced OT framework with GW marginal penalization which enables the joint embedding of two datasets based on pairwise intra-dataset distances. While our model can handle the aligned transfer into arbitrary metric spaces, it relies on their appropriate definition. In particular, due to computational restrictions, working on a grid in \mathbb{R}^{d} is restricted to small dimensions d . As a future research direction, we are interested in developing a non-Euclidean free-support solver based on existing free-support GW barycenter algorithms ( Peyré et al., 2016 ; Vayer et al., 2020a ; Beier & Beinert, 2025 ) . This may combine our EW λ approach with a non-Euclidean version of JMDS. From a theoretical point of view, the joint embedding using proposed variational formulation may be adapted to handle multiple input spaces. The main issue is hereby the selection of an appropriate generalization of the employed Wasserstein part. A possible choice would be to utilize only the Wasserstein distance between the embeddings of the k th and (k+1) st embedding. Since the employed multi-marginal Sinkhorn method linearly scales in the number of spaces, we expect that the resulting method remains numerically tractable for small numbers of spaces. The actual choice of the model and the numerical implementation of a multiple space variant, however, requires further studies. Impact Statements This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. Appendix A Proofs Proof of Proposition 3.1 The main idea of the proof follows the argumentation for the original embedded Wasserstein distance on Euclidean spaces in ( Salmona et al., 2024 ) , which we adapt to arbitrary metric spaces. The definiteness follows directly from the definition of the isomorphic equivalence classes, the isometries in EW, and the definiteness of the Wasserstein distance. The symmetry is inherited from the Wasserstein distance too. It remains to show the triangle inequality. Without loss of generality, we take representatives \mathbb{X}_{i}\coloneqq(Z,d_{Z},\xi_{i}) , i=1,\dots,3 , such that \xi_{i}\in\mathcal{P}(Z) possess full support. Since the inverse and composition of isometries are isometry, we have \EW(\mathbb{X}_{1},\mathbb{X}_{2})=\inf_{I_{i}:Z\hookrightarrow Z}\W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2})=\inf_{I_{i}:Z\hookrightarrow Z}\W(\xi_{1},(I_{1}^{-1}\circ I_{2})_{\sharp}\xi_{2})=\inf_{I:Z\hookrightarrow Z}\W(\xi_{1},I_{\sharp}\xi_{2}). Using the triangle inequality of the Wasserstein distance, we obtain \displaystyle\EW(\mathbb{X}_{1},\mathbb{X}_{2}) \displaystyle=\inf_{I:Z\hookrightarrow Z}\W(\xi_{1},I_{\sharp}\xi_{2})\leq\inf_{I,J:Z\hookrightarrow Z}\W(\xi_{1},J_{\sharp}\xi_{3})+\W(J_{\sharp}\xi_{3},I_{\sharp}\xi_{2}) \displaystyle=\inf_{J:Z\hookrightarrow Z}\Bigl(\W(\xi_{1},J_{\sharp}\xi_{3})+\inf_{I:Z\hookrightarrow Z}\W(J_{\sharp}\xi_{3},I_{\sharp}\xi_{2})\Bigr)=\inf_{J:Z\hookrightarrow Z}\Bigl(\W(\xi_{1},J_{\sharp}\xi_{3})+\inf_{I:Z\hookrightarrow Z}\W(\xi_{3},(J^{-1}\circ I)_{\sharp}\xi_{2})\Bigr) \displaystyle=\inf_{J:Z\hookrightarrow Z}\W(\xi_{1},J_{\sharp}\xi_{3})+\inf_{K:Z\hookrightarrow Z}\W(\xi_{3},K_{\sharp}\xi_{2})=\EW(\mathbb{X}_{1},\mathbb{X}_{3})+\EW(\mathbb{X}_{3},\mathbb{X}_{2}). \Box Proof of Proposition 3.2 Let X\in\{X_{i}:i=1,2\} . We equip the space of continuous functions C(X,Z) with the topology of uniform convergence d(f,g)\coloneqq\max_{x\in X}d_{Z}(f(x),g(x)) . 1. First, we we show that \Iso(X,Z)\coloneqq\{I:X\hookrightarrow Z\}\subset C(X,Z) is compact. Since (Z,d_{Z}) is compact, we see immediately that \Iso(X,Z) is pointwise bounded. Moreover, since all functions in \Iso(X,Z) are isometries the set is equicontinuous. By the Theorem of Arzelà–Ascoli ( Munkres, 2000 ) (Thm. 47.1), this gives the relative compactness of \Iso . Further, \Iso(X,Z)\subset C(X,Z) is closed and thus compact, since we have for any sequence of isometies (I_{n})_{n} from X to Z converging to some I\in C(X,Z) that d_{X}(x,x^{\prime})=d_{Z}(I_{n}(x),I_{n}(x^{\prime}))\rightarrow d_{Z}(I(x),I(x^{\prime})) as n\to\infty , so that I\in\Iso(X,Z) . Then also \Iso(X_{1},Z)\times\Iso(X_{2},Z) is compact. 2. Next, we show that the functional F(I_{1},I_{2})\coloneqq\W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}) in ( 7 ) is lower semi-continuous on \Iso(X_{1},Z)\times\Iso(X_{2},Z) . For i=1,2 , let (I_{i,n})_{n\in\mathbb{N}}\subset\Iso(X_{i},Z) and I_{i}\in\Iso(X_{1},Z) with I_{i,n}\to I_{i} as n\to\infty . Then, for all \varphi\in C(Z,\mathbb{R}) , it holds by the dominated convergence theorem that \displaystyle\int_{Z}\varphi\,\mathrm{d}(I_{i,n})_{\sharp}\xi_{i}=\int_{X}\varphi\circ I_{i,n}\,\mathrm{d}\xi_{i} (43) \displaystyle\rightarrow\int_{X_{i}}\varphi\circ I_{i}\,\mathrm{d}\xi_{i}=\int_{Z}\varphi\,\mathrm{d}I_{i,\sharp}\xi_{i}\;\text{ as }\;n\to\infty. (44) Thus we obtain the weak convergence (I_{i,n})_{\sharp}\xi_{i}\rightharpoonup I_{i,\sharp}\xi_{i} . Finally, due to the joint weak lower semi-continuity of the Wasserstein distance ( Ambrosio et al., 2005 ) (Lemma. 7.1.4), we get the desired lower semi-continuity of F . Finally, application of the Weierstrass theorem yields the assertion. \Box Proof of Proposition 3.3 Since \mathcal{P}(Z\times Z) is weakly compact, the existence of a minimizer follows by Weierstrass’ theorem, see, e.g., ( Mordukhovich & Nam, 2022 ) (Thm. 2.164), once we can show that the objective function \displaystyle F(\pi) \displaystyle\coloneqq\int_{Z\times Z}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi(z,z^{\prime})+\lambda\sum_{i=1}^{2}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi)) (45) in ( 9 ) is weakly lower semi-continuous. Let (\pi_{n})_{n\in\mathbb{N}}\subset\mathcal{P}(Z\times Z) and \pi\in\mathcal{P}(Z\times Z) be such that \pi_{n}\rightharpoonup\pi as n\to\infty . We handle the terms of F separately. Since d_{Z}^{2} is continuous in both arguments, we obtain by definition of the weak convergence that \int_{Z\times Z}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi_{n}(z,z^{\prime})\rightarrow\int_{Z\times Z}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\pi(z,z^{\prime}) as n\to\infty . We turn to the GW terms. For i=1,2 , set \mu_{i,n}\coloneqq P_{i,\sharp}\pi_{n}\quad\text{and}\quad\mu_{i}\coloneqq P_{i,\sharp}\pi. Then the weak lower semi-continuity of the marginal projection operators yields \mu_{i,n}\rightharpoonup\mu_{i} as n\to\infty . Now let \gamma_{i,n}\in\Pi(\xi_{i},\mu_{i,n}) be a solution of \GW(\mathbb{X}_{i},(Z,d_{Z},\mu_{i,n})) , n\in\mathbb{N} . As (\gamma_{i,n})_{n\in\mathbb{N}}\subset\mathcal{P}(X_{i}\times Z) and the latter is weakly compact, we can choose a converging subsequence again denoted by (\gamma{i,n})_{n\in\mathbb{N}} , such that \gamma_{i,n}\rightharpoonup\gamma_{i}\in\mathcal{P}(X_{i}\times Z) . Using again the weak continuity of the marginal projection, we get \gamma\in\Pi(\xi_{i},\mu_{i}) . Therefore, it holds \displaystyle\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi))=\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},\mu_{i}))\leq\iint\limits_{(X_{i}\times Z)^{2}}(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z,z^{\prime}))^{2}\,\mathrm{d}\gamma(x_{i},z)\,\mathrm{d}\gamma(x_{i}^{\prime},z^{\prime}) and by continuity of the integrand and the fact that (\gamma_{i,n}\otimes\gamma_{i,n})\rightharpoonup(\gamma_{i}\otimes\gamma_{i}) , see, e.g., ( Bogachev, 2018 ) (Prop. 2.7.8) further \displaystyle\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi)) \displaystyle\leq\lim_{n\to\infty}\!\iint_{(X_{i}\times Z)^{2}}(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z,z^{\prime}))^{2}\,\mathrm{d}\gamma_{i,n}(x_{i},z)\,\mathrm{d}\gamma_{i,n}(x_{i}^{\prime},z^{\prime}) \displaystyle=\lim_{n\to\infty}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},\mu_{i,n}))=\lim_{n\to\infty}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi_{n})). This gives lower semi-continuity of the functional of F . \Box Proof of Proposition 3.4 1. First, we show that \displaystyle\EW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2})\leq\EW(\mathbb{X}_{1},\mathbb{X}_{2}),\qquad\lambda>0. (46) To this end, let I_{i}:X_{i}\hookrightarrow Z_{i} be isometries realizing \EW(\mathbb{X}_{1},\mathbb{X}_{2}) , i.e., \EW(\mathbb{X}_{1},\mathbb{X}_{2})=\W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}). By definition of the GW distance, we have \GW(\mathbb{X}_{i},(Z_{i},d_{Z_{i}},I_{i,\sharp}\xi_{i})=0 , i=1,2 . Then we obtain for \tilde{\pi}\in\Pi_{0}(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}) that \displaystyle\EW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2}) \displaystyle\leq\Big(\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\tilde{\pi}(z,z^{\prime})\Big)^{\frac{1}{2}}=\W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2})=\EW_{(Z,d_{Z})}(\mathbb{X}_{1},\mathbb{X}_{2}). 2. Now let (\lambda_{n})_{n\in\mathbb{N}} with \lambda_{n}\to\infty as n\to\infty , and let \pi_{n}\in\mathcal{P}(Z\times Z) realize \EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2}) . Then we conclude by ( 46 ) that \displaystyle\EW(\mathbb{X}_{1},\mathbb{X}_{2})\geq\EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2}) \displaystyle=\int_{Z\times Z}d_{Z}(z,z^{\prime})\,\mathrm{d}\pi_{n}(z,z^{\prime})+\lambda_{n}\sum_{i=1}^{2}\GW(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi_{n})) \displaystyle\geq\lambda_{n}\sum_{i=1}^{2}\GW(\mathbb{X}_{i},(Z,d_{Z},(P_{i})_{\#}\pi_{n})). Hence, we obtain for i=1,2 that \GW(\mathbb{X}_{i},(Z,d_{Z},(P_{i})_{\#}\pi_{n}))\to 0\;\text{ as }\;n\to\infty. Since (\pi_{n})_{n\in\mathbb{N}} is contained in the weakly compact set \mathcal{P}(Z\times Z) , there exists a subsequence (denoted in the same way) which weakly converges to some \pi\in\mathcal{P}(Z\times Z) . Then also P_{i,\sharp}\pi_{n} converges weakly to P_{i,\sharp}\pi , i=1,2 and we obtain as in the proof of ( 3.3 ), that \GW(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi))\leq\lim_{n\to\infty}\GW(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi_{n}))=0. Thus, there exist isometries I_{i}:X_{i}\hookrightarrow Z with P_{i,\sharp}\pi=I_{i,\sharp}\xi_{i} , i=1,2 , i.e., \pi\in\Pi(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}) . Finally, we obtain for any fixed \lambda>0 that \displaystyle\EW(\mathbb{X}_{1},\mathbb{X}_{2}) \displaystyle\leq\Big(\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z_{1},z_{2})\,\mathrm{d}\pi(z_{1},z_{2})\Big)^{\frac{1}{2}} \displaystyle=\Big(\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z_{1},z_{2})\,\mathrm{d}\pi(z_{1},z_{2})+\lambda\sum_{i=1}^{2}\underbrace{\GW(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi))}_{=0}\Big)^{\frac{1}{2}} \displaystyle\leq\lim_{n\to\infty}\Big(\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z_{1},z_{2})\,\mathrm{d}\pi_{n}(z_{1},z_{2})+\lambda\sum_{i=1}^{2}\GW(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\pi_{n}))\Big)^{\frac{1}{2}} \displaystyle\leq\lim_{n\to\infty}\EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2})\leq\EW(\mathbb{X}_{1},\mathbb{X}_{2}). Hence \pi\in\Pi(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}) and \displaystyle\EW(\mathbb{X}_{1},\mathbb{X}_{2}) \displaystyle=\inf_{\begin{subarray}{c}J_{i}:X_{i}\hookrightarrow Z,i=1,2\end{subarray}}\W(J_{1,\sharp}\xi_{1},J_{2,\sharp}\xi_{2})=\Big(\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z_{1},z_{2})\,\mathrm{d}\pi(z_{1},z_{2})\Big)^{\frac{1}{2}} (47) implies that (I_{1},I_{2}) minimizes \EW(\mathbb{X}_{1},\mathbb{X}_{2}) and \pi realizes \W(I_{1,\sharp}\xi_{1},I_{2,\sharp}\xi_{2}) . \Box Proof of Proposition 3.5 Without loss of generality, assume that \pi_{n} converges to \pi\in\Pi(\zeta_{1},\zeta_{2}) with \zeta_{i}\in\mathcal{P}(Z) weakly; otherwise take a convergent subsequence. Since (Z,d_{Z}) is compact, the diameter M\coloneqq\sup_{z,z^{\prime}\in Z}d(z,z^{\prime}) is finite. Using plans \tilde{\pi}_{n}\in\Pi(\zeta_{1,n},\zeta_{2,n}) , where \zeta_{i,n}\in\mathcal{P}(Z) are arbitrary GW approximations of \mathbb{X}_{i} , i.e., minimizers of ( 10 ), we estimate the relaxed embedded Wasserstein metric as follows: \displaystyle\GW^{2}(\mathbb{X}_{1},(Z,d_{Z},P_{1,\sharp}\pi_{n}))+\GW^{2}(\mathbb{X}_{1},(Z,d_{Z},P_{2,\sharp}\pi_{n}))\leq\frac{1}{\lambda_{n}}\EW_{\lambda_{n}}^{2}(\mathbb{X}_{1},\mathbb{X}_{2}) (48) \displaystyle\leq\frac{1}{\lambda_{n}}\int_{Z\times Z}d_{Z}^{2}(z,z^{\prime})\,\mathrm{d}\tilde{\pi}_{n}(z,z^{\prime})+\sum_{i=1}^{2}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\tilde{\pi}_{n}))\leq\frac{M^{2}}{\lambda_{n}}+\GWA(\mathbb{X}_{1})+\GWA(\mathbb{X}_{2}). (49) Taking the limit n\to\infty , and exploiting ( Beier & Beinert, 2025 , Lem. I.1) , we notice that the left-hand side becomes \GW^{2}(\mathbb{X}_{1},(Z,d_{Z},\zeta_{1}))+\GW^{2}(\mathbb{X}_{2},(Z,d_{Z},\zeta_{2})) . Hence \zeta_{i} , i=1,2 , have to be GW approximations of \mathbb{X}_{i} on (Z,d_{Z}) . \Box Proof of Proposition 3.6 Without loss of generality, assume that \pi_{n} converges to \pi\in\mathcal{P}(Z\times Z) weakly; otherwise take a convergent subsequence. Estimating \EW_{\lambda_{n}} using the plans \tilde{\pi}_{n}\coloneqq(\Id,\Id)_{\sharp}\zeta_{n} , where \zeta_{n}\in\mathcal{P}(Z) is an arbitrary fixed-support barycenter, i.e., a minimizer of ( 11 ), we obtain \EW_{\lambda_{n}}^{2}(\mathbb{X}_{1},\mathbb{X}_{2})\leq\lambda_{n}\sum_{i=1}^{2}\GW^{2}(\mathbb{X}_{i},(Z,d_{Z},P_{i,\sharp}\tilde{\pi}_{n})=\lambda_{n}\GWB(\zeta). (50) Thus, \lambda_{n}\to 0 implies \EW_{\lambda_{n}}(\mathbb{X}_{1},\mathbb{X}_{2})\to 0 and therefore \W^{2}(P_{1,\sharp}\pi_{n},P_{2,\sharp}\pi_{n})\to 0 . Due to the stability of the Wasserstein distance ( Ambrosio et al., 2005 , Prop. 7.1.3.) , the limit of \pi_{n} has the form \pi=(\Id,\Id)_{\sharp}\zeta for some \zeta\in\mathcal{P}(Z) . Moreover, we have \GW^{2}(\mathbb{X}_{1},(Z,d_{Z},P_{1,\sharp}\pi_{n}))+\GW^{2}(\mathbb{X}_{1},(Z,d_{Z},P_{2,\sharp}\pi_{n}))\leq\frac{1}{\lambda_{n}}\EW_{\lambda_{n}}^{2}(\mathbb{X}_{1},\mathbb{X}_{2})\leq\GWB(\mathbb{X}_{1},\mathbb{X}_{2}). (51) Taking the limit n\to\infty , and exploiting ( Beier & Beinert, 2025 , Lem. I.1) , we notice that the left-hand side becomes \GW^{2}(\mathbb{X}_{1},(Z,d_{Z},\zeta))+\GW^{2}(\mathbb{X}_{1},(Z,d_{Z},\zeta)) . Hence \zeta has to be a fixed-support GW barycenter. \Box Proof of Proposition 3.7 For arbitrary \alpha\in\mathcal{P}(X_{1}\times Z_{1}\times Z_{2}\times X_{2}) , and for \pi\coloneqq P_{Z_{1}\times Z_{2},\sharp}\alpha and \gamma_{i}\coloneqq P_{X_{i}\times Z_{i},\sharp}\alpha , the functional in ( 17 ) can be estimated by \displaystyle F_{\lambda}(\alpha) \displaystyle=\iint\limits_{(X_{1}\times Z_{1}\times Z_{2}\times X_{2})^{2}}\Bigl[\tfrac{1}{2}\bigl(d_{Z}^{2}(z_{1},z_{2})+d_{Z}^{2}(z_{1}^{\prime},z_{2}^{\prime})\bigr)+\lambda\sum_{i=1}^{2}(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z_{i},z_{i}^{\prime}))^{2}\Bigr]\,\mathrm{d}\alpha(x_{1},z_{1},x_{2},x_{2})\,\mathrm{d}\alpha(x_{1}^{\prime},z_{1}^{\prime},z_{2}^{\prime},x_{2}^{\prime}) \displaystyle=\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z_{1},z_{2})\,\mathrm{d}\pi(z_{1},z_{2})+\lambda\sum_{i=1}^{2}\iint_{(X_{i}\times Z_{i})^{2}}(d_{X_{i}}(x_{i},x_{i}^{\prime})-d_{Z}(z_{i},z_{i}^{\prime}))^{2}\,\mathrm{d}\gamma_{i}(x_{i},z_{i})\,\mathrm{d}\gamma_{i}(x_{i}^{\prime},z_{i}^{\prime}) (52) \displaystyle=\int_{Z_{1}\times Z_{2}}d_{Z}^{2}(z_{1},z_{2})\,\mathrm{d}\pi(z_{1},z_{2})+\lambda\left(G_{X_{1},Z}(\gamma_{1})+G_{X_{2},Z}(\gamma_{2})\right)\geq\EW^{2}_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2}). (53) Now let \pi^{*} and \gamma_{i}^{*} be solutions of ( 13 ). Due to the gluing lemma ( Villani, 2003 , Lem. 7.6) , there exists \alpha^{*}\in\mathcal{P}(X_{1}\times Z_{1}\times Z_{2}\times X_{2}) such that P_{Z_{1}\times Z_{2},\sharp}\alpha^{*}=\pi^{*} and P_{X_{i}\times Z_{i},\sharp}\alpha^{*}=\gamma_{i}^{*} . For this \alpha^{*} , the inequality in ( 53 ) becomes sharp, i.e., F_{\lambda}(\alpha^{*})=\EW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2}) . Thus \alpha^{*} solves ( 17 ). The other way round, let \alpha^{*} be a solution of ( 17 ). As argued in the first part of the proof, the inequality in ( 53 ) has to be again sharp. Hence \pi^{*}\coloneqq P_{Z_{1}\times Z_{2},\sharp}\alpha^{*} and \gamma_{i}^{*}\coloneqq P_{X_{i}\times Z_{i},\sharp}\alpha^{*} solve ( 13 ). \Box Appendix B Numerical Studies on GW, EW, and EW λ Our approach enables geometrically meaningful data comparison as we can approximate the EW metric on general metric spaces Z . We validate this in two experiments. Approximation of \EW by \EW_{\lambda} for Synthetic Circular Data Consider circular mm-spaces \mathbb{X}_{i}=(\mathbb{S}^{1},d_{\mathbb{S}^{1}},\xi_{i}) with (Z,d_{Z})=(\mathbb{S}^{1},d_{\mathbb{S}^{1}}) , where ( \mathbb{S}^{1} , d_{\mathbb{S}^{1}} ) denotes the circle equipped with a circular distance. We set \xi_{1} uniformly distributed and \xi_{2} according to the density of a von Mises distribution with increasing dispersion parameter \kappa . Note that the von Mises distribution takes the form of a uniform distribution for \kappa=0 and becomes more concentrated for \kappa\to\infty . Due to the rotational invariance of the uniform distribution on the circle, the embedded Wasserstein distance can easily be calculated in this case as it coincides with the Wasserstein distance. Thus, we can ignore the isometry in \EW and directly calculate \EW by solving the linear program underlying the OT problem. We discretize the circle into 360 bins and estimate \EW_{\lambda} for different choices of \kappa and \lambda . The results in Figure 19 show an improved approximation of \EW for larger \lambda as announced in Proposition 3.4 . Indeed, we have an excellent fit for \lambda=20 , whereas \lambda=0.2 leads to an underestimation. \EW^{2} ( \lambda=\infty ) \EW^{2}_{\lambda} ( \lambda=20 ) \EW^{2}_{\lambda} ( \lambda=0.2 ) Figure 19 : Comparison of \EW with \EW_{\lambda} for different \lambda . While the curves for \EW (left) and \EW_{20} (middle) are almost identical, those for \EW_{0.2} (right) is consistently smaller. 2d Shape Matching Next, we compare randomly rotated gray-value images. We can describe such images as mm-spaces \mathbb{X}_{i}=(X,d,\xi_{i}) where X\subset\mathbb{R}^{2} is a grid that describes the pixel positions equipped with the Euclidean metric and \xi_{i} is the pixel intensity, see ( Beier et al., 2023 ) . We use (Z,d_{Z})=(X,d) . We apply random affine transformations, i.e., translations and rotations, to the first 10 FashionMNIST ( Xiao et al., 2017 ) training images from the classes “Trouser”, “Pullover” and “Sneaker”, respectively. Then we compute \W , \GW and \EW_{\lambda} for \lambda=20 . The results are displayed in Figure 21 . As expected, the Wasserstein distance cannot recover the class structure due to the affine transformations, whereas \EW_{\lambda} and GW capture the class structure. Moreover, we see that the distance matrices of \EW_{\lambda} and GW display almost identical patterns, up to scaling. \EW_{\lambda} ( \lambda=20 ) \GW \W Figure 21 : Pairwise \W , \GW and \EW_{20} distances of 10 randomly rotated and translated images from each of the “Trouser” (T), “Pullover” (P), and “Sneaker” (S) FashionMNIST classes. Smaller distances are darker. The class block structure is recovered with \EW_{\lambda} and \GW , but not with Wasserstein. Appendix C Parameter Sensitivity Algorithm 1 depends on three input parameters, namely the GW regularization parameter \lambda , the entropic regularization parameter \varepsilon and the chosen discrete reference space Z . Generally, we aim to set \lambda as high as possible and \varepsilon as low as possible while preserving numerical stability. Based on two sets of 3d shapes described in Section 6.1 , namely a s-curve in combination with a Swiss roll with a hole and two human shapes, we present a parameter sensitivity study that illustrates the impact of \lambda , \varepsilon and Z . Throughout this study note that our Euclidean joint embeddings are invariant to translations and rotations which results in arbitrarily oriented joint embeddings. In Figure 24 , we investigate the influence of the GW parameter \lambda that promotes near-isometric embeddings. We observe that the embeddings of both spaces nearly coincide for small \lambda . This is supported by Proposition 3.6 showing that the embeddings form a fixed-support barycenter in the limiting case. Moreover, we see a saturation effect where an increase of \lambda from 1 to 100 has only a small impact on the joint embeddings. In Figure 27 , we investigate the influence of the entropic parameter \varepsilon that enables efficient computation. Here, we see that a large \varepsilon leads to a highly blurred embedding. This shows that it is advisable to choose a low, but numerically stable value for \varepsilon . Lastly, we investigate the discretization of the reference space in Figure 30 . Again, we aim for a fine discretization, but the runtime of our algorithm depends heavily on the size |Z| of our reference space. We observe that the joint embeddings display the same shapes and alignments, only at higher resolution. All embeddings were computed with 40 iterations of Algorithm 1 . \lambda=0.5 \lambda=1 \lambda=100 (a) S-bended rectangle and Swiss roll with hole. \lambda=0.5 \lambda=1 \lambda=100 (b) Same human shape in different poses. Figure 24 : Ablation study of \lambda for joint embedding of shapes from Figure 8(b) and 11(a) . Based on varying \lambda values, we employ our method with \varepsilon=0.001 and Z defined by a uniform 20\times 20 grid in [0,1.3]^{2} . \varepsilon=0.001 \varepsilon=0.002 \varepsilon=0.01 (a) S-bended rectangle and Swiss roll with hole. \varepsilon=0.001 \varepsilon=0.002 \varepsilon=0.01 (b) Same human shape in different poses. Figure 27 : Ablation study of \varepsilon for joint embedding of shapes from Figure 8(b) and 11(a) . Based on varying \varepsilon values, we employ our method with \lambda=100 and Z defined by a uniform 20\times 20 grid in [0,1.3]^{2} . Below the joint embeddings, we show convergence plots of the unregularized functional F_{100}(\alpha) from ( 17 ) after 4, 8, 12, 16, 20, 24 and 28 iterations. |Z|=15^{2} (28s) |Z|=20^{2} (53s) |Z|=60^{2} (27min) (a) S-bended rectangle and Swiss roll with hole. |Z|=15^{2} (19s) |Z|=20^{2} (34s) |Z|=60^{2} (20min) (b) Same human shape in different poses. Figure 30 : Ablation study of the grid size for joint embedding of shapes from Figure 8(b) and 11(a) . Based on \varepsilon=0.001 and \lambda=100 , we employ our method with Z\subset[0,1.3]^{2} defined by a uniform 15\times 15 , 20\times 20 or 60\times 60 grid. We include CPU runtimes. Appendix D Hyperparameter Selection JMDS, SCOT, and our method all rely on the Sinkhorn algorithm. Therefore, we use the same fixed entropic regularization \varepsilon for all three methods for a given experiment. We choose it as small as possible while avoiding numerical overflow, i.e., \varepsilon=0.001 or \varepsilon=0.002 . Next, there are multiple ways of defining the nearest neighbor graph described in Section 6.2 . For our experiments, we start by running the SCOT algorithm which offers an unsupervised hyperparameter search to determine the shape of the nearest neighbor graph ( Demetci et al., 2022 ) . We use the unsupervised hyperparameter selection of the publicly available SCOT implementation 3 3 3 https://github.com/rsinghlab/SCOT (March 2025) to estimate a suitable nearest-neighbor graph. Here, we use the same \varepsilon as in the rest of the experiment and use the default grid over the neighborhood size. Note that the public implementation uses a connectivity graph based on pairwise correlation distances between points instead of Euclidean distances, see ( Demetci et al., 2022 ) . Then, we use SCOT and MDS to estimate the final embeddings based on the pairwise geodesic distance matrix estimated from this graph. We use the same distance graph for UnionCom, JMDS, and our algorithm. Here, we estimate suitable hyperparameters based on a random 10% validation split. We use four parameter configurations for each algorithm, i.e., we test \lambda=0.01,0.1,10,100 for JMDS and our method. For UnionCOM, we use combinations of \beta=1,10 and a perplexity of 30 and 100 for the t-SNE dimensionality reduction. We use no parameter annealing for any method. Appendix E Further Example for Comparing Feature Spaces As an addition to the genetyping experiment, we present another experiment with real-world data based on latent spaces. We consider the task of comparing the 4d latent spaces of an auto-encoder (AE) versus a variational auto-encoder (VAE), trained on FashionMNIST ( Xiao et al., 2017 ) . For this purpose, we train a simple convolutional AE with two convolutional layers and one linear layer for the encoder and the decoder. We train the AE with the MSE loss and the VAE with the log-likelihood loss for 10 epochs on the canonical training data splits. Subsequently, we embed the test data using the resulting AE and VAE into the 4d latent spaces. Note that such distinct AE trained on the same dataset generally produce incomparable embeddings. For our experiment, we consider the first 100 data points of the test split. We choose Z as an equispaced 20 \times 20 grid on [0,1.3]\subset\mathbb{R}^{2} with the Euclidean distance. We follow the same evaluation routine as in Subsection 6.2 for parameter selection and visualization. The joint embeddings are visualized in Figure 33 . Comparing FOSCTTM and KNN, we see again a good embedding quality for our approach, see the figure caption. Figure 33 : Joint embedding of the FashionMNIST latent space of an AE and a VAE into \mathbb{R}^{2} using our method and JMDS. The AE latent space is on the top and the VAE latent space is on the bottom. Both methods align the color-coded classes. A quantitative comparison shows that our model achieves a better FOSCTTM (0.040) than JMDS (0.042), whereas our KNN-Accuracy (0.589) is slightly worse than the one of JMDS (0.644). Ours JMDS