将高维最优传输距离近似转化为最近邻问题，大幅提速。
Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
- 用最近邻算法思路重构最优传输距离计算框架。
- 在高维下实现1+ε近似，时间复杂度降至n²⁻~Ω(ε¹/³)。
- 适合需要高效处理海量高维数据的研究者。
本文给出(1+ε)-近似地球移动距离（EMD）到(1+ε)-近似最近邻（CP）的归约。给定p∈[1,2]及两组n个点X,Y⊆(R^d,ℓ_p)，EMD是X与Y间完美匹配的最小成本，匹配代价为ℓ_p距离。若(1+ε)-近似最近邻可在时间n²⁻ϕ内求解，则(1+ε)近似EMD可在时间n²⁻Ω(ϕ)内完成。利用最新最近邻算法（Alman, Chan, Williams FOCS'16），得到高维情形下(1+ε)-近似EMD算法运行时间为n²⁻~Ω(ε¹/³)，优于此前最快时间n²⁻Ω(ε²)（Andoni, Zhang FOCS'23）。核心技术在于对乘法权重更新框架的亚线性实现：无需显式计算或存储权重，而是通过几何结构隐式执行更新。
原文摘要 · Abstract (English)
We give a reduction from $(1+\varepsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\varepsilon)$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\in [1, 2]$ and two sets of $n$ points $X,Y \subseteq (\mathbb R^d,\ell_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their $\ell_p$ distance. Further, CP is the basic problem of finding a pair of points realizing $\min_{x \in X, y\in Y} ||x-y||_p$. Our contribution is twofold: we show that if a $(1+\varepsilon)$-approximate CP can be computed in time $n^{2-ϕ}$, then a $1+O(\varepsilon)$ approximation to EMD can be computed in time $n^{2-Ω(ϕ)}$; plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a $(1+\varepsilon)$-approximation algorithm for EMD running in time $n^{2-\tildeΩ(\varepsilon^{1/3})}$ for high-dimensional point sets, which improves over the prior fastest running time of $n^{2-Ω(\varepsilon^2)}$ [Andoni, Zhang FOCS'23]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。