论文标题
最佳传输上图和光谱边界上分布良好的顶点的序列
Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport
论文作者
论文摘要
给定一个图$ g =（v，e）$，假设我们有兴趣选择一个顶点$（x_j）_ {j = 1}^n $的序列，以便$ \ weft \ weft \ {x_1，\ dots，x_k \ right \} $是$ k $的均匀分布的'srifertifuted'。我们描述了一种贪婪的算法，该算法是由潜在理论和连续环境中相应发展的相应发展动机的。该算法在图表上表现良好，可能用于抽样问题。我们可以将算法解释为试图最大程度地减少负面的Sobolev规范。我们解释了为什么这与Wasserstein距离有关，通过在图表上建立纯粹的光谱结合在瓦斯恒星距离上，以反映R. Peyre在连续环境中的估计值。我们用许多例子说明了这一点，并讨论了几个开放问题。
Given a graph $G=(V,E)$, suppose we are interested in selecting a sequence of vertices $(x_j)_{j=1}^n$ such that $\left\{x_1, \dots, x_k\right\}$ is `well-distributed' uniformly in $k$. We describe a greedy algorithm motivated by potential theory and corresponding developments in the continuous setting. The algorithm performs nicely on graphs and may be of use for sampling problems. We can interpret the algorithm as trying to greedily minimize a negative Sobolev norm; we explain why this is related to Wasserstein distance by establishing a purely spectral bound on the Wasserstein distance on graphs that mirrors R. Peyre's estimate in the continuous setting. We illustrate this with many examples and discuss several open problems.
