A reduced-order model for parametrized Optimal Transport problems
This work addresses computational efficiency in optimal transport for applications like image processing, but it appears incremental as it builds on existing model order reduction techniques.
The authors tackled the problem of efficiently solving parametrized optimal transport problems by developing a reduced-order model that uses model order reduction methods, resulting in a linear program with fewer degrees of freedom and constraints, and applied it to a 1D example and color transfer between images, comparing performance to the Sinkhorn algorithm.
In this work, we aim at efficiently solving a parametrized family of optimal transport problems by using model order reduction methods. We propose a reduced-order model by adding to the primal (respectively dual) version of the high-fidelity model the additional constraint to live in a non negative sub cone (resp. in subspaces) of small dimension. The reduced-order model then reads as a linear program with a small number of degrees of freedom and constraints. We identify explicit conditions under which this reduced-order model has at least one solution. We propose two a posteriori error estimations that bounds the error between the optimal values of the high-fidelity problem and the reduced-order model. As one of these estimations requires the computation of non linear terms (with respect to the reduction of dimension), we use an Empirical Interpolation Method (EIM) (see e.g. \cite{maday2007general} or \cite{barrault2004empirical}) to numerically efficiently compute this estimation. We apply the whole methodology on a simple 1D example and on a problem of color transfer between images, and compare its performances to Sinkhorn algorithm.