提出分层精炼算法，让大规模点集匹配既快又精确。
Hierarchical Refinement: Optimal Transport to Infinity and Beyond
- 用低秩近似分层构建点集划分，逐步逼近双射映射
- 处理超百万点数据，时间复杂度为对数线性，空间线性
- 适合需要高精度匹配的大规模数据任务
最优传输（OT）在机器学习中因能通过最小代价对应关系对齐数据集而取得巨大成功，主要得益于Sinkhorn算法的高效性。然而，该算法在点数上具有二次时间与空间复杂度，限制了其在更大数据集上的应用。低秩OT可实现线性复杂度，但无法计算点间的单射对应。当最优传输问题为数据集间分配问题时，存在保证为双射的最优映射（即Monge映射）。本文发现，最优低秩耦合的因子会将每个点与其在Monge映射下的像聚类在一起。基于这一不变性，我们提出层级精炼（HiRef）算法，通过求解一系列低秩OT子问题，动态构建数据集的多尺度划分，最终得到双射的Monge映射。该算法实现对数线性时间复杂度和线性空间复杂度，兼具低秩OT的优势并克服其分辨率局限。我们在多个数据集上验证了其优势，包括超过一百万点的数据，使全秩OT得以扩展至此前超出Sinkhorn能力范围的问题。
原文摘要 · Abstract (English)
Optimal transport (OT) has enjoyed great success in machine learning as a principled way to align datasets via a least-cost correspondence, driven in large part by the runtime efficiency of the Sinkhorn algorithm (Cuturi, 2013). However, Sinkhorn has quadratic space and time complexity in the number of points, limiting scalability to larger datasets. Low-rank OT achieves linear complexity, but by definition, cannot compute a one-to-one correspondence between points. When the optimal transport problem is an assignment problem between datasets then an optimal mapping, known as the Monge map, is guaranteed to be a bijection. In this setting, we show that the factors of an optimal low-rank coupling co-cluster each point with its image under the Monge map. We leverage this invariant to derive an algorithm, Hierarchical Refinement (HiRef), that dynamically constructs a multiscale partition of each dataset using low-rank OT subproblems, culminating in the bijective Monge map. Hierarchical Refinement runs in log-linear time and linear space, retaining the advantages of low-rank OT while overcoming its limited resolution. We demonstrate the advantages of Hierarchical Refinement on several datasets, including ones containing over a million points, scaling full-rank OT to problems previously beyond Sinkhorn's reach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。