Transport Clustering: Solving Low-Rank Optimal Transport via Clustering

Optimal transport (OT) finds a least-cost transport plan between two probability distributions. Unlike standard OT, which infers unstructured pointwise mappings, low-rank optimal transport explicitly constrains the rank of the transport plan to infer latent structure. This improves statistical robustness, yields sharper parametric rates for estimating Wasserstein distances, and generalizes $K$-means to co-clustering. However, these advantages come at the cost of a non-convex and NP-hard optimization problem. We introduce Transport Clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a clustering problem on correspondences obtained from a full-rank transport registration step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a $(1+\gamma)$ approximation for negative-type metrics, a $(1+\gamma+\sqrt{2\gamma}\,)$ approximation for kernel costs, and a $(1+\gamma+\rho)$ approximation for general metrics satisfying the triangle inequality. Here, $\gamma \in [0,1]$ is the cost ratio of the optimal full-rank to low-rank solutions, and $\rho\in[0,1]$ is an asymmetry coefficient on the cluster variances. Numerically, Transport Clustering outperforms existing solvers on synthetic benchmarks and large-scale datasets.