# Transport Clustering: Solving Low-Rank Optimal Transport via Clustering

arXiv: https://arxiv.org/abs/2603.03578 · HTML: https://mlsanity.com/paper/2603.03578/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 59 references that are in the map.
- First posted on arXiv 3 Mar 2026.

## Builds on (most cited first, 23 of 23)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improving and generalizing flow-based generative models with minibatch optimal transport](https://mlsanity.com/paper/2302.00482/) (2023)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [A mathematical perspective on Transformers](https://mlsanity.com/paper/2312.10794/) (2023)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Neural Optimal Transport](https://mlsanity.com/paper/2201.12220/) (2022)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark](https://mlsanity.com/paper/2106.01954/) (2021)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Statistical optimal transport](https://mlsanity.com/paper/2407.18163/) (2024)
- [Schr"odinger Bridge Flow for Unpaired Data Translation](https://mlsanity.com/paper/2409.09347/) (2024)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [Distributional Preference Alignment of LLMs via Optimal Transport](https://mlsanity.com/paper/2406.05882/) (2024)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [Making transport more robust and interpretable by moving data through a small number of anchor points](https://mlsanity.com/paper/2012.11589/) (2020)
- [Linear Time Sinkhorn Divergences using Positive Features](https://mlsanity.com/paper/2006.07057/) (2020)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling](https://mlsanity.com/paper/2411.10555/) (2024)
- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Background Modeling for Double Higgs Boson Production: Density Ratios and Optimal Transport](https://mlsanity.com/paper/2208.02807/) (2022)

## Abstract (arXiv)

Optimal transport (OT) finds a least cost transport plan between two probability distributions using a cost matrix defined on pairs of points. 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 stability and robustness, yields sharper parametric rates for estimating Wasserstein distances adaptive to the intrinsic rank, and generalizes K-means to co-clustering. These advantages, however, 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 textittransport registration step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a (1+γ) approximation for negative-type metrics and a (1+γ+√2γ,) approximation for kernel costs, where γ ∈ [0,1] denotes the approximation ratio of the optimal full-rank solution relative to the low-rank optimal. Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.