Fast Dual Subgradient Optimization of the Integrated Transportation
  Distance Between Stochastic Kernels
Zhengqi Lin Andrzej Ruszczynski
A generalization of the Wasserstein metric, the integrated transportation
distance, establishes a novel distance between probability kernels of Markov
systems. This metric serves as the foundation for an efficient approximation
technique, enabling the replacement of the original system's kernel with a
kernel with a discrete support of limited cardinality. To facilitate practical
implementation, we present a specialized dual algorithm capable of constructing
these approximate kernels quickly and efficiently, without requiring
computationally expensive matrix operations. Finally, we demonstrate the
efficacy of our method through several illustrative examples, showcasing its
utility in practical scenarios. This advancement offers new possibilities for
the streamlined analysis and manipulation of stochastic systems represented by
kernels.