This paper introduces Sinkhorn distances, a new family of optimal transportation distances that can be computed efficiently using the Sinkhorn-Knopp algorithm. Optimal transportation distances are fundamental for histograms but are computationally expensive due to the need to solve a linear program. The authors propose regularizing the optimal transportation problem with an entropic term, which transforms the linear program into a strictly convex problem that can be solved quickly with the Sinkhorn-Knopp algorithm. This regularization is based on the maximum-entropy principle and results in a distance that can be computed much faster than traditional optimal transportation methods. The Sinkhorn distance is shown to perform better than the Earth Mover's Distance (EMD) on the MNIST benchmark problem. The paper also demonstrates that Sinkhorn distances can be computed efficiently on large-scale data using parallel platforms such as GPGPUs. The Sinkhorn distance is defined as the minimum of the transportation cost over a restricted set of joint probability matrices, and it is shown to be symmetric and satisfy triangle inequalities. The paper concludes that Sinkhorn distances are a promising approach for optimal transportation problems, offering both computational efficiency and good performance.This paper introduces Sinkhorn distances, a new family of optimal transportation distances that can be computed efficiently using the Sinkhorn-Knopp algorithm. Optimal transportation distances are fundamental for histograms but are computationally expensive due to the need to solve a linear program. The authors propose regularizing the optimal transportation problem with an entropic term, which transforms the linear program into a strictly convex problem that can be solved quickly with the Sinkhorn-Knopp algorithm. This regularization is based on the maximum-entropy principle and results in a distance that can be computed much faster than traditional optimal transportation methods. The Sinkhorn distance is shown to perform better than the Earth Mover's Distance (EMD) on the MNIST benchmark problem. The paper also demonstrates that Sinkhorn distances can be computed efficiently on large-scale data using parallel platforms such as GPGPUs. The Sinkhorn distance is defined as the minimum of the transportation cost over a restricted set of joint probability matrices, and it is shown to be symmetric and satisfy triangle inequalities. The paper concludes that Sinkhorn distances are a promising approach for optimal transportation problems, offering both computational efficiency and good performance.