## 4 Sparse Cost Functions
### Tree Structure  
We consider the MOT\({}_{\eta}\) problem with the structure of a _tree_\((\mathcal{V},\mathcal{E})\), which is a connected and circle-free graph with \(|\mathcal{E}|=|\mathcal{V}|-1\). We define the (non-empty) _neighbour_ set \(\mathcal{N}_{k}\) of \(k\in\mathcal{V}\) as the set of all nodes \(\ell\in\mathcal{V}\), such that \(\{k,\ell\}\in\mathcal{E}\). Furthermore, we denote by \(\mathcal{L}\coloneqq\{k\in\mathcal{V}:|\mathcal{N}_{k}|=1\}\) the set of all _leaves_ of the tree. We call \(1\in\mathcal{V}\) the _root_ of the tree. For every \(k\in\mathcal{V}\), there is a unique path between \(k\) and the root. For \(k\in\mathcal{V}\setminus\{1\}\), we define the _parent_\(p(k)\) as the node in \(\mathcal{N}_{k}\) such that \(p(k)\) lies in the path between \(k\) and the root \(1\). The root has no parent. Without loss of generality, we assume that \(p(k)<k\) holds for all \(k\in\mathcal{V}\setminus\{1\}\). We define the set of _children_\(\mathcal{C}_{k}\coloneqq\{\ell\in\mathcal{N}_{k}:\ell>k\}\). Then, we can derive a recursive formula for the \(k\)-th marginal of the tensor \(\mathbf{\mathcal{K}}\odot\mathbf{\Phi}\in\mathbb{R}^{n}\). Theorem 3.2: _Let \((\mathcal{V},\mathcal{E})\) be a tree with leaves \(\mathcal{L}\), and let \(c\) be the MOT\({}_{\eta}\) cost function associated. Furthermore, let \(k\in\mathcal{V}\) be an arbitrary node. Then, the \(k\)-th marginal of the transport plan \(\mathbf{\mathcal{K}}\odot\mathbf{\Phi}\) is given by_  
\[P_{k}(\mathbf{\mathcal{K}}\odot\mathbf{\Phi})=\phi^{k}\odot\bigodot_{\ell\in \mathcal{N}_{k}}\alpha^{(k,\ell)},\]  
_where the vectors \(\alpha^{(k,\ell)}\in\mathbb{R}^{n_{k}}\) are recursively defined as_  
\[\alpha^{(k,\ell)}= \begin{cases}\mathbf{\mathcal{K}}^{(k,\ell)}\phi^{\ell}&\text{ if }\ell\in\mathcal{L},\\ \mathbf{\mathcal{K}}^{(k,\ell)}\Big{(}\phi^{\ell}\odot\bigodot_{t\in\mathcal{N}_{k }\setminus\{k\}}\alpha^{(\ell,\ell)}\Big{)}&\text{otherwise.}\end{cases} \]  
A proof of Theorem 3.2 can be found in [13] (Theorem 3.2). The main idea is to split the rooted tree at the node \(k\) into \(|\mathcal{N}_{k}|\) subtrees. Therefore, the kernel matrix holds  
\[\mathbf{\mathcal{K}}_{i}=\prod_{\{k_{1},k_{2}\}\in\mathcal{E}}\mathbf{\mathcal{K}}_{ i_{k_{1}},k_{2}}^{(k_{1},k_{2})}=\prod_{\ell\in\mathcal{N}_{k}}\prod_{t\in \mathcal{D}_{\ell}}\mathbf{\mathcal{K}}_{i_{p(t)},i_{t}}^{(p(t),t)},\quad i\in\mathbf{ I},\]  
where \(\mathcal{D}_{\ell}\) is the set of descendants of \(\ell\), i.e., the nodes \(t\in\mathcal{V}\) such that \(\ell\) lies in the path between \(k\) and \(t\). Inserting \(\mathbf{\mathcal{K}}_{i}\) into \(P_{k}(\mathbf{\mathcal{K}}\odot\mathbf{\Phi})\) and recalling the definition of \(P_{k}\) in (2) yields the result. In order to efficiently perform the Sinkhorn algorithm, we compute iteratively for \(\ell=K,\ldots,2\) the vectors \(\beta_{\ell}\coloneqq\alpha^{(p(\ell),\ell)}\in\mathbb{R}^{n_{p(\ell)}}\). From Theorem 3.2, we obtain  
\[\beta_{\ell}= \begin{cases}\mathbf{\mathcal{K}}^{(p(\ell),\ell)}\phi^{\ell}&\text{ if }\ell\in\mathcal{L},\\ \mathbf{\mathcal{K}}^{(p(\ell),\ell)}\Big{(}\phi^{\ell}\odot\bigodot_{t\in \mathcal{C}_{\ell}}\beta_{t}\Big{)}&\text{otherwise.}\end{cases} \]  
Since we assumed that \(p(k)<k\), the computation of \(\beta_{\ell}\) requires only \(\beta_{t}\) for \(t>\ell\). Similarly, the vectors \(\gamma_{\ell}\coloneqq\alpha^{(\ell,p(\ell))}\in\mathbb{R}^{n_{\ell}}\) for \(\ell>1\) and \(\gamma_{1}\coloneqq\mathbf{1}_{n_{1}}\) can be iteratively computed by \[\gamma_{\ell}=\left(\mathbf{\mathcal{K}}^{(p(\ell),\ell)}\right)^{\intercal}\left( \phi^{p(\ell)}\odot\gamma_{p(\ell)}\odot\bigodot_{t\in\mathcal{C}_{p(\ell)} \setminus\{\ell\}}\beta_{t}\right),\quad\ell=2,\ldots,K,\]  
where the vectors \(\beta_{t}\in\mathbb{R}^{n_{p(\ell)}}\) are assumed to be known from above.