Fast Wasserstein Barycenters and Smoothed Dual Subgradient Descent

Fast Wasserstein Barycenters and Smoothed Dual Subgradient Descent is a computational optimal transport framework introduced by Cuturi and Doucet (2014) for computing Fréchet means (Wasserstein barycenters) of empirical probability measures nu_1, ..., nu_N under p-Wasserstein distances by minimizing the weighted sum f(mu) = (1/N) sum_{i=1}^N D(mu, nu_i) over a discrete support X = [x_1, ..., x_n] and probability simplex weight vector a in Sigma_n. To overcome the non-smoothness and O(n^3 log n) linear-programming cost of the unregularized dual optimal transport polytope, the method introduces the entropically smoothed primal objective p_lambda(a, b; M) = min_{T in U(a,b)} <T, M> - (1/lambda) h(T) and its smoothed Legendre dual d_lambda(a, b; M) = max_{alpha, beta} alpha^T a + beta^T b - (1/lambda) sum_{i,j} exp(-lambda(m_{ij} - alpha_i - beta_j)). Proposition 2 and Algorithm 3 establish that the zero-sum centered optimal dual scaling logarithm alpha_lambda^* = (1/lambda) log(u) - (log(u)^T 1_n / (lambda n)) 1_n recovered from Sinkhorn-Knopp matrix scaling T_lambda^* = diag(u) exp(-lambda M) diag(v) is the exact gradient nabla_a p_lambda(a, b; M) on the probability simplex, enabling entropic mirror descent / exponentiated gradient updates for fixed-support weight optimization (Algorithm 1) and alternating closed-form Newton support updates X <- (1/N) sum_{i=1}^N Y_i (T_i^*)^T diag(a^{-1}) for free-support barycenters (Equation 8, Algorithm 2).