A Fast Algorithm For Monge-Kantorovich Problem Based On Partial Differential Equations/Probability Theory

About the optimal transport problem, it has different kinds of ex-pressions in different fields. In this paper, we firstly introduce where this problem comes from and its different forms. And then according to paper [5], it uses a simple probability theory to transform the celebrated Monge-Kantorovich problem in a bounded region of Euclidean plane into a Dirichlet boundary problem associated to a quasi-linear elliptic equa-tion with0-order term missing in its diffusion coefficients: where, Ay’(...)>0, Bx’(...)>0, F is an unknown probability distribu-tion function.But it is quite difficult to solve this quasi-linear elliptic equation. So we start from the original energy equation, and try to find a fast algorithm.Firstly we introduce operator splitting method, penalty method as well as alternate iteration method to the energy equation, which trans-form a difficult multi-variable problem into a multi-step problem. Thus, we only have to deal with one variable in each step, or deal with a explicit expression, which reduces the difficulty a lot.Because the initial energy defines the distance between two probability density functions f(x, y) and f(x, y), in this paper, we want to introduce this to image process-ing. By taking each pixel of the image as a function value of a point, each image will correspond to a2-D function. Then after unitization, we can get two probability density functions. Thus, the above energy equal-ity also defines the Kantorovich-Rubinstein-Wasserstein L2-distance be-tween two images, we can use which as an indicator to describe the similarity or difference between two images. In the final part of this paper, we also give out several examples to confirm the correctness as well as the validity.