论文标题
关于贪婪的Wasserstein最小化的组合特性
On Combinatorial Properties of Greedy Wasserstein Minimization
论文作者
论文摘要
我们讨论了一种现象，其中最佳运输会导致大量的组合规律性。考虑以$ [0,1] $构建以贪婪的方式构建的无限序列$（x_k）_ {k = 1}^{\ infty} $ in $ [0,1] $：给定$ x_1，\ dots，x_n $，新的点$ x__ {n+1} $，以便选择$ w liper $ w y sempir $ w y+pimim $ w__2测量，$ x_ {n+1} = \ arg \ min_x〜w_2 \ left（\ frac {1} {n+1} \ sum_ {k = 1}^{n}δ__{x_k}示例：$ x_ {n+1} =（2k+1）/（2n+2）$ in \ mathbb {z} $中的某些$ k \）与Ralph Kritzinger最近在其他设置中引入的序列相吻合。从数值上讲，这些序列的规律性与组合学或数理论的最著名构造相媲美。我们证明了平方根屏障以下的规律性结果。
We discuss a phenomenon where Optimal Transport leads to a remarkable amount of combinatorial regularity. Consider infinite sequences $(x_k)_{k=1}^{\infty}$ in $[0,1]$ constructed in a greedy manner: given $x_1, \dots, x_n$, the new point $x_{n+1}$ is chosen so as to minimize the Wasserstein distance $W_2$ between the empirical measure of the $n+1$ points and the Lebesgue measure, $$x_{n+1} = \arg\min_x ~W_2\left( \frac{1}{n+1} \sum_{k=1}^{n} δ_{x_k} + \frac{δ_{x}}{n+1}, dx\right).$$ This leads to fascinating sequences (for example: $x_{n+1} = (2k+1)/(2n+2)$ for some $k \in \mathbb{Z}$) which coincide with sequences recently introduced by Ralph Kritzinger in a different setting. Numerically, the regularity of these sequences rival the best known constructions from Combinatorics or Number Theory. We prove a regularity result below the square root barrier.
