A Computationally Efficient Algorithm for Optimal Mass Transport via Wavelet-Based Multiresolution Methods
摘要
This paper introduces a computationally efficient approximation scheme for solving the Monge–Kantorovich (MK) optimal mass transport problem. Exact solutions for the MK problem are typically difficult or computationally expensive to obtain, particularly in high-dimensional or large-scale scenarios. To address this challenge, we propose an innovative method integrating wavelet theory and multiresolution analysis. Our approach exploits wavelet-based techniques to iteratively approximate the support of the optimal measure, thereby reducing the number of variables in linear programs and consequently decreasing the dimensionality and computational complexity of each subsequent optimization step. We present numerical experiments demonstrating that our wavelet-enhanced scheme achieves high accuracy with substantially fewer computational resources compared with traditional linear programming approaches. The method has potential applications across various domains, including image processing, economics, resource allocation, and machine learning, where efficient solutions to large-scale optimal transport problems are essential.