Entropic Gromov-Wasserstein Discrepancy and Barycenter Averaging

Entropic Gromov-Wasserstein Discrepancy and Barycenter Averaging is a metric-measure alignment and relational matrix averaging methodology introduced by Peyré, Cuturi, and Solomon (2016) that compares and averages pairs of intra-domain distance or similarity matrices (C, p) in R^{N x N} x Sigma_N and (C_bar, q) in R^{M x M} x Sigma_M across incomparable ambient spaces by solving the entropically regularized non-convex quadratic assignment problem GW_epsilon(C, C_bar, p, q) = min_{T in U(p,q)} E(C, C_bar, T) - epsilon H(T), where E(C, C_bar, T) = sum_{i,j,k,l} L(C_{i,k}, C_bar_{j,l}) T_{i,j} T_{k,l}. Proposition 1 proves that for any separable divergence L(a, b) = f_1(a) + f_2(b) - h_1(a) h_2(b) (including squared Euclidean loss L(a,b) = (1/2)|a-b|^2 and Kullback-Leibler divergence L(a,b) = a log(a/b) - a + b), the 4-way tensor contraction L(C, C_bar) (x) T reduces from O(N^2 M^2) to O(N^2 M + N M^2) matrix multiplications c_{C, C_bar}(p, q) - h_1(C) T h_2(C_bar)^T (Equations 5-6). Proposition 2 and Algorithm 1 solve the entropic GW problem via projected gradient / Sinkhorn iterations T^{(k+1)} = Proj_{U(p,q)}^{KL}(K^{(k)}) with K^{(k)} = exp(-(L(C, C_bar) (x) T^{(k)}) / epsilon), and Propositions 3-5 (Algorithm 2) compute Gromov-Wasserstein barycenters of S matrices (C_s, p_s) via closed-form first-order updates C = (1 / p p^T) odot sum_s lambda_s T_s^T C_s T_s (under L_2 loss, preserving the positive semidefinite cone) and C = exp((1 / p p^T) odot sum_s lambda_s T_s^T log(C_s) T_s) (under KL loss, preserving infinitely divisible kernels).