综述:大规模最优运输问题的简化技术

《WIREs Computational Statistics》:Sparsification Techniques for Large-Scale Optimal Transport Problems

【字体: 大 中 小 】 时间:2026年01月13日 来源:WIREs Computational Statistics 5.4

编辑推荐:

  最优传输(OT)方法因几何特性与计算能力受限于高成本,正则化OT及Sinkhorn算法虽提升效率但仍存在迭代成本高、收敛慢的问题。本文系统综述了基于核的稀疏化和Hessian的稀疏化两类方法,分析其动机、算法差异及理论保证。

  

摘要

由于最优传输(Optimal Transport, OT)方法及其变体具有吸引人的几何特性和强大的功能,它们在计算机科学和机器学习领域变得越来越重要。尽管应用广泛,但这些方法的计算成本却非常高,即使对于中等规模的数据集也限制了其可扩展性。为了解决这一挑战,正则化的OT公式及其对应的Sinkhorn算法作为提高效率的标准替代方案应运而生。然而,这些方法仍然面临每次迭代成本高和收敛速度慢的缺点。稀疏化技术作为一种有效且实用的方法,通过利用OT优化中涉及的矩阵的固有或诱导稀疏性来缓解这些计算瓶颈。大致上,稀疏化方法可以分为两大类:(1)基于核的稀疏化,它建立在原始正则化OT公式之上;(2)基于Hessian的稀疏化,它源自对偶公式。在这篇综述中,我们全面回顾了为OT问题开发的稀疏化技术,强调了它们的基本动机、算法差异和理论保证。

本文属于以下分类:

  • 统计与图形数据分析方法 > 抽样
  • 算法与计算方法 > 计算复杂性

图形摘要

本文概述了为加速原始Sinkhorn算法而提出的稀疏化方法。这些方法大致可以分为两类:(1)基于核的稀疏化;(2)基于Hessian的稀疏化,每种方法根据不同的选择标准对相应的矩阵进行稀疏化。

利益冲突

作者声明没有利益冲突。

数据可用性声明

支持本研究结果的数据可在https://people.csail.mit.edu/sumner/research/deftransfer/data.html#caveats以及https://doi.org/10.1145/1015706.1015736公开获取,参考文献编号为Sumner和Popovi?(2004)。

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号