将低秩最优传输问题转化为聚类问题，高效求解且保证近似精度。
Transport Clustering: Solving Low-Rank Optimal Transport via Clustering
- 通过运输注册生成对应关系，将低秩OT转为聚类问题。
- 在负类型度量下达到(1+γ)近似，核成本下为(1+γ+√(2γ))。
- 适合需要快速稳定计算高维数据间距离的科研与工程应用。
最优传输（OT）通过定义点对间代价矩阵，寻找两个概率分布间的最小代价传输方案。不同于标准OT推断无结构的点对映射，低秩最优传输显式约束传输方案的秩，以揭示潜在结构。这提升了统计稳定性与鲁棒性，实现了自适应于内在秩的Wasserstein距离估计的更优参数率，并推广了K-means至共聚类。然而，该方法面临非凸且NP难的优化挑战。本文提出运输聚类算法，通过全秩运输注册步骤获取对应关系，将低秩OT转化为聚类问题。我们证明该简化可获得多项式时间、常数因子近似解：在负类型度量下为(1+γ)近似，在核代价下为(1+γ+√(2γ))近似，其中γ∈[0,1]表示全秩最优解相对于低秩最优解的近似比。实验表明，该方法在合成基准及大规模高维数据集上优于现有低秩OT求解器。
原文摘要 · Abstract (English)
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 $\textit{transport 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+γ+\sqrt{2γ}\,)$ approximation for kernel costs, where $γ\in [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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。