提出一种快速计算Wasserstein距离上下界的新方法，兼顾效率与严格性。
Quantization-based Bounds on the Wasserstein Metric
- 在粗网格上求解量化后的Kantorovich问题，结合特殊代价矩阵
- 实现10~100倍加速，误差低于2%且提供严格上下界
- 适合需要高效且可靠距离估计的生成模型与图像匹配任务
Wasserstein度量在生成建模、图像检索和域自适应等机器学习应用中日益重要，但其计算成本过高。为此，已有熵正则化最优传输、下采样和子采样等近似方法，以牺牲精度换取效率。本文针对规则网格上的离散测度，提出一种新方法：在粗网格上精确求解带有量化测度和定制代价矩阵的Kantorovich问题，随后通过上采样与校正步骤，在原空间或对偶空间中获得全分辨率输入的Wasserstein度量的严格上界或下界。我们在DOTmark最优传输图像基准上评估该方法，结果表明相比熵正则化OT实现10~100倍加速，同时保持逼近误差低于2%。
原文摘要 · Abstract (English)
The Wasserstein metric has become increasingly important in many machine learning applications such as generative modeling, image retrieval and domain adaptation. Despite its appeal, it is often too costly to compute. This has motivated approximation methods like entropy-regularized optimal transport, downsampling, and subsampling, which trade accuracy for computational efficiency. In this paper, we consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds. Focusing on discrete measures on regular grids, our approach involves formulating and exactly solving a Kantorovich problem on a coarse grid using a quantized measure and specially designed cost matrix, followed by an upscaling and correction stage. This is done either in the primal or dual space to obtain valid upper and lower bounds on the Wasserstein metric of the full-resolution inputs. We evaluate our methods on the DOTmark optimal transport images benchmark, demonstrating a 10x-100x speedup compared to entropy-regularized OT while keeping the approximation error below 2%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。