The Wasserstein metric matrix and its computational property (Q6184918)

The Wasserstein metric is an important metric for the global comparison between probability distributions. Because of this metric property, it has many applications, for example in image processing, compressive sensing, inverse problems, quantum measurement, optimal transport and many more. A fundamental problem in applications of the Wasserstein metric is its accurate and fast computation which is an extremely difficult problem. A crucial tool in this regard is the computation of a certain kernel matrix or the so called Wasserstein metric matrix with a given vector. An important example of a known algorithm in this regard is the Sinkhorn iteration method. Building on previous work of the authors, in this interesting paper, the authors study the concrete algebraic structures and essential computational properties of the Wasserstein-1 metric matrices of one- and two-dimensions. They show that these matrices, can be represented by a Neumann series of nilpotent matrices and, therefore, the products of these matrices with a prescribed vector can be achieved stably and accurately for optimal computational complexities through solving unit bidiagonal triangular systems of linear equations. The authors also give appropriate generalizations of these one- and two-dimensional Wasserstein-1 metric matrices, as well as their corresponding extensions to higher dimensions, and examine carefully the computaional properties and the algebraic structures of these extended Wasserstein-1 metric matrices. The paper is well written with an excellent set of references.