Low-rank tensor approximations for solving multi-marginal optimal transport problems

By adding entropic regularization, multi-marginal optimal transport problems can be transformed into tensor scaling problems, which can be solved numerically using the multi-marginal Sinkhorn algorithm. The main computational bottleneck of this algorithm is the repeated evaluation of marginals. In [Haasler et al., IEEE Trans. Inf. Theory, 67 (2021)], it has been suggested that this evaluation can be accelerated when the application features an underlying graphical model. In this work, we accelerate the computation further by combining the tensor network dual of the graphical model with additional low-rank approximations. For the color transfer of images, these added low rank approximations save more than 96% of the computation time.