Wasserstein 重心可以在固定维度的多项式时间内计算
本文证明了计算 Wasserstein barycenters 的困难性,在任何维度上都具有指数时间复杂度,这揭示了一个 “维度诅咒” 现象,并延伸到其他 Optimal Transport 度量的概率分布。
Jan, 2021
该论文提出了一种可扩展的算法,用于计算 Wasserstein-2 重心,针对输入测量,其不仅限于离散形式,并使用输入凸神经网络和周期一致性正则化以避免引入偏差,并提供了误差界的理论分析,以及在低维定性情景和高维定量实验中提出的方法的实证证据。
Feb, 2021
通过引入随机算法,该研究提出了一种计算连续分布的 Wasserstein 重心的有效在线算法,该算法基于优化输运理论和 Wasserstein 重心,并使用其对偶势隐式地参数化了该问题。
Aug, 2020
本文介绍了一种半离散的无障碍通信、并行算法用于计算连续输入分布的 Wasserstein barycenter,该算法能够跟踪输入的分布情况,适用于 Bayesian 推理和连续数据流处理任务。
May, 2017
本文提出两种算法来计算一组经验概率测度的 Wasserstein barycenters,其中包括使用 entropic 正则化来平滑 Wasserstein distance 的方法,并使用矩阵缩放算法计算其梯度,这些算法可用于可视化大量图像并解决约束聚类问题。
Oct, 2013
本文研究分布存储在网络上的一组连续概率测度的正则 Wasserstein 重心的分散分布计算,提出了一种新的基于加速原始对偶随机梯度方法的分布式半离散正则 Wasserstein 重心算法,并给出了明确的非渐进复杂度。
Jun, 2018
本文通过随机算法来计算具有 Wasserstein 距离下的一组概率分布的重心,该方法不同于以往的方法,可以适用于连续输入分布,并允许在每个迭代中调整重心的支持,该算法能够恢复出一个锐利的输出,其支持集合包含在真实重心的支持集合内,并能在一些例子中恢复出比以前更有意义的重心。该方法具有广泛的适用性,可扩展到生成给定分布的超级样本和恢复蓝噪声近似等应用。
Feb, 2018
本文介绍了一种求解离散概率分布 Wasserstein 重心的方法,使用了对偶问题建模,并基于对称 Gauss-Seidel 方法的交替方向乘子法求解,可以高效地处理大规模线性规划问题。
Sep, 2018
本文研究了 Wasserstein barycenters 在离散情况下的理论结果和应用,揭示了离散 Wasserstein barycenters 必须也是离散度量,且有可证明的稀疏驻点,同时提供了一个固定货物和不同需求分布情况下的最优库存分布的 proof-of-concept 计算方法。
Jul, 2015
本文介绍了一种新的内点法,该方法充分利用了问题的特殊矩阵结构,以降低迭代复杂度和加速牛顿过程,并在各种分布条件下进行了数值比较,展示了该方法的计算优势。此外,我们还在包括 MNIST 和 Fashion-MNIST 在内的图像基准测试问题上演示了我们算法的实用性。
May, 2019