A Numerical Scheme for Approximating the Support and the Value of an Optimal Solution to the Mass Transfer Problem via Wavelets and Multiresolution Analysis

In this paper, we present a scheme for approximating the support and optimum value of an optimal measure for the Monge-Kantorovich (MK) mass transfer problem. Obtaining exact solutions to the MK problem is difficult; such solutions are only found in a few specific cases. Using an algorithm to approximate the optimum value is computationally expensive, particularly in high-dimensional or large-scale scenarios. To address this challenge, we developed an innovative method that integrates wavelet theory and multiresolution analysis. This method uses wavelet-based techniques to approximate the support of an optimal measure, further reducing the number of variables in the linear programs and thus decreasing the dimensionality and computational complexity of each step of the scheme. This method generates a sequence of transport problems with optimal measures of finite support. We then demonstrate that the optimum values ​​of the transport problems converge to the optimum value of the MK problem and that the supports of the finite optimal measures converge to the support of an optimal measure for the MK problem. We present some numerical experiments to demonstrate the efficiency of the scheme. We observe that the method has potential applications in various fields, such as image processing, economics, resource allocation, and machine learning, where finding efficient solutions to large-scale optimal transportation problems is essential.