## 4 Sparse Cost Functions
### Circle Structure
To efficiently compute the marginal optimal transport as for the tree structure, we choose \(k=1\) as the starting point and decompose the marginal into two matrices, which can be computed recursively as follows. For matrices \(\mathbf{G},\mathbf{H}\in\mathbb{R}^{n\times m}\), we define the inner product with respect to the second dimension by  
\[=\phi_{i_{k}}^{k}\sum_{i_{1}}\phi_{i_{1}}^{1}\sum_{i_{2}}\mathcal{ K}_{i_{1},i_{2}}^{(1,2)}\phi_{i_{2}}^{2}\cdots\sum_{i_{k-2}}\mathcal{K}_{i_{k-3},i_{k-2}}^{(k-3,k-2)}\phi_{i_{k-2}}^{k-2}\sum_{i_{k-1}}\mathcal{K}_{i_{k-2},i_ {k-1}}^{(k-2,k-1)}\phi_{i_{k-1}}^{k-1}\mathcal{K}_{i_{k-1},i_{k}}^{(k-1,k)}\]2  
Under the assumptions of Theorem 3.1, we have  
\[P_{k}(\mathbf{K}\odot\mathbf{\Phi})= \begin{cases}\phi^{1}\odot\left\langle\mathbf{K}^{(1, 2)},\left(\phi^{2}\odot\alpha^{(2,1)}\right)^{\mathsf{T}}\right\rangle,&k=1, \\ \phi^{k}\odot\left\langle\alpha^{(k,1)},\left(\phi^{1}\odot\lambda^{(1,k)} \right)^{\mathsf{T}}\right\rangle,&k=2,\ldots,K,\end{cases} \]  
where \(\alpha^{(k,1)}\) is given in (9) and  
\[\lambda^{(1,k)}\coloneqq \begin{cases}\mathbf{\mathcal{K}}^{(1,2)},&k=2,\\ \lambda^{(1,k-1)}\Big{(}\phi^{(k-1)}\odot\mathbf{\mathcal{K}}^{(k-1,k)}\Big{)},&k =3,\ldots,K.\end{cases}  \tag{10}\]  
Proof. : Let \(k\in[K]\) and \(i_{k}\in[n_{k}]\). For \(k=1\), the assertion follows from Theorem 3.1. For \(k>2\), we have  
\[\left[P_{k}(\mathbf{\mathcal{K}}\odot\mathbf{\Phi})\right]_{i_{k}} =\phi_{i_{k}}^{k}\sum_{i_{1}}\phi_{i_{1}}^{1}\sum_{i_{2}}\mathbf{ \mathcal{K}}_{i_{1}i_{2}}^{(1,2)}\phi_{i_{2}}^{2}\cdots\sum_{i_{k-1}}\mathbf{ \mathcal{K}}_{i_{k-2}i_{k-1}}^{(k-2,k-1)}\phi_{i_{k-1}}^{k-1}\mathbf{\mathcal{K}}_ {i_{k-1}i_{k}}^{(k-1,k)}\] \[\qquad\sum_{i_{k+1}}\mathbf{\mathcal{K}}_{i_{k}i_{k+1}}^{(k+1)}\phi_{ i_{k+1}}^{k+1}\cdots\sum_{i_{k}}\mathbf{\mathcal{K}}_{i_{k-1}i_{K}}^{(K-1,K)}\phi_{i_{k}} ^{k}\mathbf{\mathcal{K}}_{i_{k}i_{k}}^{(K,1)}\] \[=\phi_{i_{k}}^{k}\sum_{i_{1}}\phi_{i_{1}}^{1}\underbrace{\sum_{i_ {2}}\mathbf{\mathcal{K}}_{i_{1}i_{2}}^{(1,2)}\phi_{i_{2}}^{2}\cdots\sum_{i_{k-1}} \mathbf{\mathcal{K}}_{i_{k-2}i_{k-1}}^{(k-2,k-1)}\phi_{i_{k-1}}^{k-1}\mathbf{\mathcal{ K}}_{i_{k-1}i_{k}}^{(k-1,k)}}_{\mathrm{I}:=}\alpha_{i_{k}i_{1}}^{(k,1)}.\]  
Furthermore, the term \(\mathrm{I}\) can be rewritten as  
\[\mathrm{I}=\sum_{i_{k-1}}\mathbf{\mathcal{K}}_{i_{k-1}i_{k}}^{(k-1,k)}\phi_{i_{k- 1}}^{k-1}\sum_{i_{k-2}}\mathbf{\mathcal{K}}_{i_{k-2}i_{k-1}}^{(k-2,k-1)}\phi_{i_{k- 2}}^{k-2}\cdots\sum_{i_{2}}\mathbf{\mathcal{K}}_{i_{1}i_{2}}^{(1,2)}\phi_{i_{2}}^ {2}\mathbf{\mathcal{K}}_{i_{2}i_{3}}^{(2,3)}\]  
By (10), we have  
\[\lambda_{i_{1}i_{3}}^{(1,3)}=\sum_{i_{2}}\mathbf{\mathcal{K}}_{i_{1}i_{2}}^{(1,2)} \phi_{i_{2}}^{2}\mathbf{\mathcal{K}}_{i_{2}i_{3}}^{(2,3)},\quad i_{1}\in[n_{1}],\ i_{3}\in[n_{3}].\]  
This implies that  
\[\mathrm{I} =\sum_{i_{k-1}}\mathbf{\mathcal{K}}_{i_{k-1}i_{k}}^{(k-1,k)}\phi_{i_{ k-1}}^{k-1}\sum_{i_{k-2}}\mathbf{\mathcal{K}}_{i_{k-2}i_{k-1}}^{(k-2,k-1)}\phi_{i_{k- 2}}^{k-2}\cdots\sum_{i_{3}}\mathbf{\mathcal{K}}_{i_{3}i_{4}}^{(3,4)}\phi_{i_{3}}^{ 3}\lambda_{i_{1}i_{3}}^{(1,3)},\] \[=\cdots=\sum_{i_{k-1}}\mathbf{\mathcal{K}}_{i_{k-1}i_{k}}^{(k-1,k)}\phi _{i_{k-1}}^{k-1}\lambda_{i_{1}i_{k-1}}^{(1,k-1)}=\left[\lambda^{(1,k-1)}\Big{(} \phi^{k-1}\odot\mathbf{\mathcal{K}}^{(k-1,k)}\Big{)}\right]_{i_{1}i_{k}}=\lambda_{ i_{1}i_{k}}^{(1,k)}.\]  
Hence, the hypothesis is true for all \(k>2\). The case \(k=2\) can be proven using the same procedure. In order to efficiently compute a maximizing sequence of the dual \(\text{MOT}_{\eta}\) problem (6), we set for \(k\in[K]\) the dual matrices  
\[\beta_{k} \coloneqq\alpha^{(k,1)}\in\mathbb{R}^{n_{k}\times n_{1}},\] \[\gamma_{k} \coloneqq\lambda^{(k,1)}\in\mathbb{R}^{n_{1}\times n_{k}},\]  
given in Theorems 3 and 4, respectively. The method is shown in Algorithm 3. ```
1:Input: Initialization \((\phi^{k})^{(0)},\;k\in[K]\), parameters \(\eta,\delta>0\)
2:Initialize \(r\gets 0\)
3:for\(k=K,\cdots,2\)do
4:\(\left(\beta_{k}\right)^{(0)}\coloneqq