Statistical Optimal Transport: Article Review
An in-depth analysis of the seminal paper "Regularized Discrete Optimal Transport" (Ferradans et al., SIAM 2014)[cite: 3]. This work explores relaxed formulations of the Kantorovich problem[cite: 3], the introduction of geometric graph-based regularizations such as Sobolev and Total Variation (TV)[cite: 3], along with their algorithmic application to high-resolution color palette transfers[cite: 3].
Algorithmic Complexity
Frank-Wolfe
Iterative projection-free scheme for solving linearized subproblems[cite: 3].
Downsampling
K-Means
Point cloud reduction (\(N=64, 144, 400\)) to make computation tractable[cite: 3].
Regularization Topology
k-NN Graphs
Penalization of irregular variations along the geometric data manifold[cite: 3].
Integrality Property
TU Matrix
Total unimodularity ensuring binary solutions at vertices under integer constraints[cite: 3].
Qualitative Evolution of Transfer (Fidelity vs. Quantization Resolution $N$)
Mathematical Formulation & Non-Local Regularization
To alleviate the rigidity of the strict coupling problem, the formulation introduces a relaxed transport polytope \(\mathcal{S}_{\kappa}\) weakening the classical marginal constraints[cite: 3]:
The underlying geometry is incorporated by applying a discrete gradient operator \(G_X\) on the data connectivity graph, where the regularization energy under the \((p,q)\) norm is written as[cite: 3]:
When \((p,q) = (1,1)\), the penalty corresponds to a non-smooth anisotropic Total Variation[cite: 3]. The global problem is then solved via a linear programming reformulation by introducing auxiliary variables bounding the geometric gradients[cite: 3].
Scientific Analysis Report
Access the full theoretical study, duality schemes, and comparative analyses of the algorithm.
PDF Preview (Available on wide screens or via download)