标题： 基于量化的方法对Wasserstein度量的界值研究 显示英文标题

标题： Quantization-based Bounds on the Wasserstein Metric

摘要： Wasserstein度量在许多机器学习应用（如生成模型、图像检索和领域适应）中变得越来越重要。尽管它具有吸引力，但计算起来通常成本过高。这促使了近似方法的发展，如熵正则化最优传输、下采样和子采样，这些方法以准确率为代价换取计算效率。本文考虑了计算Wasserstein度量的有效近似值的挑战，同时将其作为严格的上界或下界。专注于规则网格上的离散测度，我们的方法涉及在粗网格上使用量化测度和专门设计的成本矩阵精确求解Kantorovich问题，然后进行放大和校正阶段。这一过程可以在原始空间或对偶空间中进行，以获得全分辨率输入的Wasserstein度量的有效上下界。我们在DOTmark最优传输图像基准上评估了我们的方法，与熵正则化的最优传输相比，速度提高了10倍到100倍，同时将近似误差保持在2%以下。 显示英文摘要

摘要： 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%.