## 6 Numerical Examples
### Fixed-Support Wasserstein Barycenter for General Trees  
Let \(\mathcal{T}=(\mathcal{V},\mathcal{E})\) be a tree with set of leaves \(\mathcal{L}\); see Section 4.1. For \(k\in\mathcal{L}\), let measures \(\mu^{k}\) and weights \(\tilde{w}_{k}\in[0,1]\) be given that satisfy \(\sum_{k\in\mathcal{L}}\tilde{w}_{k}=1\). For any edge \(e\in\mathcal{E}\), we set  
\[w_{e}\coloneqq\begin{cases}1&\text{if }|e\cap\mathcal{L}|\
eq 1,\\ \tilde{w}_{k}&\text{if }e\cap\mathcal{L}=\{k\}\,.\end{cases}\]  
Figure 4: MOT\({}_{\eta}\) with tree-structured cost function, where \(d=2\), \(K=10\), \(N=10,000\), and \(p=3\). **Left**: Approximation error of \(\mathcal{S}^{(10)}\) between the Sinkhorn and the NFFT-Sinkhorn algorithm, depending on the number of Fourier coefficients \(M\) of the NFFT. **Right**: Computation time in seconds.  
Figure 5: MOT\({}_{\eta}\) with circle-structured cost function, where \(d=2\), \(K=3\), \(N=1000\), and \(p=3\). Left: Approximation error of \(\mathcal{S}^{(10)}\) between Sinkhorn and NFFT-Sinkhorn algorithm depending on the number of Fourier coefficients \(M\). Right: Computation time in seconds.  
Figure 3: Computation time in seconds of MOT\({}_{\eta}\) with a circle-structured cost function with regularization parameter \(\eta=0.1\). **Left**: fixed \(N=700\). **Right**: fixed \(K=3\).  
The generalized barycenters are the minimizers \(\mu^{k}\), \(k\in\mathcal{V}\setminus\mathcal{L}\), of  
\[\inf_{\mu^{k}\in\mathbb{F}\big{(}\Omega^{k}\big{)},k\in\mathcal{V}\setminus \mathcal{L}}\sum_{e=\{e_{1},e_{2}\}\in\mathcal{E}}w_{e}\mathrm{W}_{2}^{2}\big{(} \mu^{e_{1}},\mu^{e_{2}}\big{)}, \tag{20}\]  
where \(\mathrm{W}_{2}^{2}(\mu^{e_{1}},\mu^{e_{2}})\) is the squared Wasserstein distance [48; 49] between the measures \(\mu^{e_{1}}\) and \(\mu^{e_{2}}\). The well-known Wasserstein barycenter problem [50; 51] is a special case of (20), where the tree is star-shaped and the barycenter corresponds to the unique internal node. We consider the fixed-support barycenter problem [52; 26], where the nodes \(\mathbf{x}^{k}\), \(k\in\mathcal{V}\setminus\mathcal{L}\) are also given, so that we need to optimize (20) only for \(\mu^{k}_{i_{k}}\), \(k\in\mathcal{V}\setminus\mathcal{L}\). This yields an MOT problem with the tree-structured cost  
\[C_{i}=\sum_{e=\{e_{1},e_{2}\}\in\mathcal{E}}w_{e}\bigg{\|}\mathbf{x}^{e_{1}}_{i_{ 1}}-\mathbf{x}^{e_{2}}_{i_{1}}\bigg{\|}_{2}^{2},\quad i\in\mathbf{I},\]  
where the marginal constraints of (1) are only set for the known measures \(\mu^{k}\), \(k\in\mathcal{L}\) (see [53]). This barycenter problem can be solved approximately using a modification of the Sinkhorn Algorithm 2, in which we replace line 12 by  
\[(\phi^{k})^{(r+1)}=\begin{cases}\mathbf{1}&\text{if }k\in\mathcal{L},\\ \mu^{k}\oslash\left(\gamma_{k}^{(r)}\odot\left(\beta^{\odot c_{k}}\right)^{(r)} \right)&\text{otherwise}.\end{cases}\]  
We test our algorithm with a tree consisting of \(K=7\) nodes; see Figure 6. The four given marginals \(\mu^{k}\), \(k\in\mathcal{L}\), are dithered images in \(\mathbb{R}^{2}\) with uniform weights \(\mu^{k}_{i_{k}}=1/N\). As support points of the barycenters \(\mu^{k}\), \(k\in\mathcal{V}\setminus\mathcal{L}\), we take the union over all support points \(\mathbf{x}^{k}_{i_{k}}\) of all four input measures \(\mu^{k}\), \(k\in\mathcal{L}\). Furthermore, we use the barycenter weights \(\tilde{w}^{k}=1/4\). The given images and the computed barycenters are show in Figure 7, where we executed \(r=150\) iterations of the Sinkhorn algorithm and its accelerated version. We chose the regularization parameter \(\eta=5\cdot 10^{-3}\) and the fast summation parameters \(M=156\), \(p=3\).  
Figure 6: The tree graph of the barycenter problem, with leaves \(\mathcal{L}\) marked in blue.