## 3 Multi-Marginal Optimal Transport  
In the following, we consider the discrete _multi-marginal optimal transport_ (MOT) between \(K\) marginal measures \(\mu^{k}\in\mathbb{P}(\Omega^{k})\), \(k\in[K]\). We define the set of _admissible transport plans_ by  
\[\Pi(\mu^{1},\ldots,\mu^{k})\coloneqq\left\{\mathbf{\Pi}\in\mathbb{R}^{\mathbf{n}}_{ \geq 0}:P_{k}(\mathbf{\Pi})=\mu^{k}\text{ for all }k\in[K]\right\}, \tag{1}\]where the \(k\)-th marginal projection is defined as  
\[P_{k}(\mathbf{\Pi})\coloneqq\sum_{\ell\in[K]\setminus\{k\}}\sum_{i_{\ell}\in[n_{ \ell}]}\mathbf{\Pi}_{i_{1},\cdots,i_{K}}\in\mathbb{R}^{n_{k}}. \tag{2}\]  
For a _cost function_\(c\colon\mathbf{\Omega}\to\mathbb{R}_{\geq 0}\) and the samples \(\mathbf{x}_{i}=\left(x_{i_{1}}^{1},\ldots,x_{i_{K}}^{K}\right)\), \(i\in I\), we define the respective _cost matrix_  
\[\mathbf{C}\coloneqq[\mathbf{C}_{i}]_{i\in I}=[c(\mathbf{x}_{i})]_{i\in I}=[c(\mathbf{x}_{i_{1} }^{1},\cdots,\mathbf{x}_{i_{K}}^{K})]_{(i_{1},\cdots,i_{K})\in I}\in\mathbb{R}_{ \geq 0}^{\mathbf{\pi}}. \tag{3}\]  
The discrete MOT problem reads  
\[\min_{\mathbf{\Pi}\in\Pi(\mu^{1},\ldots,\mu^{K})}\langle\mathbf{\Pi},\mathbf{C} \rangle_{\mathrm{F}}, \tag{4}\]  
whose solution \(\mathbf{\Pi}\in\mathbb{R}_{\geq 0}^{\mathbf{\pi}}\) is called _optimal plan_. _Entropy Regularization_  
As the MOT problem (4) is numerically unfeasible, we consider for \(\eta>0\) the entropy-regularized multi-marginal optimal transport (\(\text{MOT}_{\eta}\)) problem  
\[\min_{\mathbf{\Pi}\in\Pi(\mu^{1},\ldots,\mu^{K})}\langle\mathbf{\Pi},\mathbf{C} \rangle_{\mathrm{F}}+\eta\langle\mathbf{\Pi},\log\mathbf{\Pi}-\mathbf{1}_{\eta} \rangle_{\mathrm{F}}=\min_{\mathbf{\Pi}\in\Pi(\mu^{1},\ldots,\mu^{K})}\sum_{i \in I}\mathbf{\Pi}_{i}\mathbf{C}_{i}+\eta\sum_{i\in I}\mathbf{\Pi}_{i}\big{(}\log \mathbf{\Pi}_{i}-1\big{)}, \tag{5}\]  
which is a convex optimization problem. It is possible to numerically deduce the optimal transport plan \(\mathbf{\Pi}\) of (5) from the solution of the corresponding Lagrangian dual problem. The following theorem is a special case of [3] for a constant entropy function. Theorem 3.1: _The Lagrangian dual formulation of the discrete MOT\({}_{\eta}\) problem (5) states_  
\[\sup_{\phi^{k}\in\mathbb{R}_{\geq 0}^{n_{k}}\times\mathbb{R}\in[K]}\mathcal{S} \Big{(}\phi^{1},\cdots,\phi^{K}\Big{)}\coloneqq\sup_{\phi^{i}\in\mathbb{R}_{ \geq 0}^{n_{k}}\times\mathbb{R}\in[K]}\eta\sum_{k\in[K]}\sum_{j\in[n_{k}]}\mu^{k}_ {j}\log\phi^{k}_{j}-\eta\sum_{i\in I}\mathcal{K}_{i}\mathbf{\Phi}_{i}, \tag{6}\]  
_where the kernel matrix \(\mathbf{\mathcal{K}}\in\mathbb{R}^{n}\) is defined by_  
\[\mathcal{K}_{i}\coloneqq\exp\left(-\frac{\mathbf{C}_{i}}{\eta}\right),\quad i\in I,\]  
_and the dual tensor \(\mathbf{\Phi}=\bigotimes_{k=1}^{K}\phi^{k}\) by_  
\[\mathbf{\Phi}_{i}\coloneqq\prod_{k=1}^{K}\phi^{k}_{i_{k}},\quad i\in I.\]  
_The functional \(\mathcal{S}\colon\mathbb{R}_{\geq 0}^{\mathbf{\pi}}\to\mathbb{R}\) is called the Sinkhorn function._  
The solutions of the dual and the primal problem are generally not equal. The solution of (6) is generally a lower bound to the solution of the primal problem (5). Equality holds if the cost function \(c\) is lower semi-continuous; i.e., \(\liminf c(\mathbf{x})\geq c(\mathbf{x}_{0})\) as \(\mathbf{x}\to\mathbf{x}_{0}\) for every \(\mathbf{x}_{0}\in\mathbb{R}^{n}\), or Borel measurable and bounded [40]. This is obviously the case for the squared Euclidean norm cost function  
\[c\colon\mathbb{R}^{\mathbf{\pi}}\to[0,\infty),\quad c(\mathbf{x})=\sum_{ \begin{subarray}{c}k_{1},k_{2}\in[K]\\ k_{1}+k_{2}\end{subarray} }\left\|x_{i_{k_{1}}}^{k_{1}}-x_{i_{k_{2}}}^{k_{2}} \right\|_{2}^{2}\]  
that we study here. **Proposition 1** ([41]).