# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
The goal is to find a coupling \(G\) on \(A\times B\) that minimizes the transport cost \(T\) defined as  
\[T_{p}(G)=\left(\int_{A\times A}\int_{B\times B}G(a,b)\big{|}d_{A}(a,a^{\prime} )-d_{B}(b,b^{\prime})\big{|}^{p}G(a^{\prime},b^{\prime})data^{\prime}dbdb^{ \prime}\right)^{\frac{1}{p}}, \tag{4}\]with \(p\geq 1\) (the most common value for \(p\) is 2, as it will be discussed below). The minimum of \(T_{p}(G)\) is to be found over couplings that satisfy the constraints defined in Equation (3). As for the standard Monge-Kantorovich OT presented above, it was proved that a minimum to the transport cost defined in Equation (4) always exists [8]; we write this minimum as \(GW_{p}(\alpha,\beta)\). Finding this minimum, however, is a quadratic optimization problem, as opposed to finding the coupling that minimizes the transport cost associated with the OT problem (Equation (2)), which is a linear optimization problem. This minimum of the transportation cost defines a distance over the space of metric measured spaces (i.e., the triplet \((A,d_{A},\alpha)\)) modulo the measure-preserving isometries [8]. When the metrics \(d_{A}\) and \(d_{B}\) are the Euclidean distance over real numbers, i.e., when \(A=\mathbb{R}^{m}\) and \(B=\mathbb{R}^{n}\) (with \(n\) not necessarily equal to \(m\)), and \(d_{A}=||.||_{\mathbb{R}^{m}}\) and \(d_{B}=||.||_{\mathbb{R}^{n}}\) (where \(||.||\) means the Euclidean norm), and when \(p=2\), an interesting property of \(GW_{2}(\alpha,\beta)\) is that it is invariant with respect to rigid body transformations (i.e., isometries). This is of significance for example if the GW framework is to be used to compare shapes in space, when this comparison has to be independent of the relative positions of the shapes..  
As mentioned above, classical OT is a linear programming problem. It is intriguing, however, that the current successes of OT are not due to recent advances in solving LP problems. They were instead prompted by the idea of entropic regularization, namely minimizing a modified version of the transport cost defined in Equation (2) :  
\[U_{\epsilon}(G) = U(G)-\epsilon H(G), \tag{5}\]  
where \(\epsilon\) is the parameter that controls the amount of regularization and \(H(G)\) is an entropy on the coupling \(G\). It is there to impose the positivity of its elements [18]. As \(\epsilon\to 0\) the regularized problem tends to the traditional problem. Interestingly, the minimum of the regularized transport cost \(U_{\epsilon}(G_{opt})\) is a distance that satisfies all metric properties for all values of \(\epsilon\). This distance is called the Sinkhorn distance [18]. The main advantage of the entropic regularization is that it leads to a strictly convex problem that has a unique solution [18]. In addition, this solution can be found effectively using the [PERSON]'s algorithm [19; 20; 21]. [PERSON]'s algorithms have running times of order \(O(N^{2})\), while solving directly the OT problem as a linear program problem has a running time complexity of \(O(N^{3})\). The same entropic regularization can be used the solve the GW problem, originally a quadratic optimization problem which is NP-hard in its general formulation. The idea is the same as for OT, namely add a regularized term to Equation (4) (see [22]):  
\[T_{p,\epsilon}(G)=\big{(}T_{p}(G)\big{)}^{p}-\epsilon H(G). \tag{6}\]  
Note that here it is not \(T_{p}(G)\) that is considered, but its \(p\)-th power. While this simplifies the optimization process, it sets \(T_{p,\epsilon}(G)\) to be a \"discrepancy\" (in the language of [PERSON] et al. [22]) and not a distance with metric properties. The addition of the entropic regularization led, however, to an iterative algorithm for finding the GW discrepancy, with each iteration amounting to solve a regularized OT problem [22]. While the regularization based on entropy significantly expanded the appeal of OT, there are issues with the numerical convergence of the regularized solution to the actual OT solution.