Numerical analysis and extensions for optimal transport

最佳运输的数值分析和扩展

• 批准号: 403056140
• 负责人: Professor Dr. Bernhard Schmitzer
• 金额: --
• 依托单位: Institut für Informatik (IfI)
• 依托单位国家: 德国
• 项目类别: Independent Junior Research Groups
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/403056140?language=en
• 关键词: Numerical; analysis; extensions; optimal; transport

The acquisition of images and 3D-data through microscopes, medical imaging devices, satellites, video cameras and depth sensors has become standard in science and technology. To keep track of the overwhelming amount of data we are in need of capable mathematical methods for their automated and quantitative analysis. The choice of a meaningful metric on the set of observations is crucial as it provides the basis for most higher level tasks such as clustering, classification and regression. It must reflect the similarity between samples, be able to separate common from atypical variations, and be resilient to noise and discretization errors.Optimal transport provides a geometrically intuitive and robust way to define a metric on probability measures over a metric space. It is useful in the analysis of stochastic systems and partial differential equations. Additionally, it is becoming increasingly popular as numerical tool in data analysis applications where, due to its intuitive nature and robustness, it has been shown to be vastly superior to simple pointwise similarity measures.However, it is still far from being the ubiquitous powerful tool it could be.This is due to three major restrictions. Optimal transport is only defined for probability measures, i.e. normalized non-negative scalar signals (so multi-channel signals cannot be compared). The induced metric is only a geodesic metric if the base space is geodesic (implying the lack of a notion of interpolation between data points). Finally, its numerical evaluation is costly. This imposes considerable limitations on the practical applicability in terms of problem size and data type.Recently, the systematic study of more general transport-type distances for measures of varying mass, for non-scalar signals or for discrete base spaces has attracted growing attention. These developments are still in their very early steps, fundamental questions are open at this point and I am convinced that many exciting developments are yet to come.Besides, although there is already a broad spectrum of numerical methods for optimal transport the situation today is not yet satisfactory. The computationally most efficient methods are often not very flexible and the more flexible methods tend to be considerably less efficient. Moreover, many heuristic methods to reduce computational complexity provide no mathematical guarantees for their validity.This project intends to address both theoretical and practical aspects of optimal transport. We will develop new transport-type distances for both non-scalar data and for discrete base spaces. Moreover, we will work towards a deeper understanding of the geometry of the transport optimization problem to develop new algorithms that are fast, flexible, and yet mathematically sound.Together, these goals will widen the theoretical and practical scope of optimal transport for data analysis applications.

通过显微镜、医学成像设备、卫星、摄像机和深度传感器获取图像和3D数据已成为科学技术的标准。为了跟踪大量的数据，我们需要能够进行自动化和定量分析的数学方法。在观测集上选择一个有意义的度量是至关重要的，因为它为大多数更高级别的任务（如聚类、分类和回归）提供了基础。它必须反映样本之间的相似性，能够区分常见和非典型的变化，并对噪声和离散化错误具有弹性。最优传输提供了一种几何直观和鲁棒的方法来定义度量空间上的概率度量。它在随机系统和偏微分方程的分析中是有用的。此外，它在数据分析应用中作为数值工具越来越受欢迎，由于其直观性和鲁棒性，它已被证明大大上级简单的逐点相似性度量。然而，它仍然远未成为无处不在的强大工具。这是由于三个主要限制。最佳传输仅针对概率测量定义，即归一化非负标量信号（因此无法比较多通道信号）。如果基空间是测地线的（意味着数据点之间缺乏插值的概念），则导出度量仅是测地线度量。最后，其数值评估是昂贵的。这对问题大小和数据类型方面的实际适用性施加了相当大的限制。最近，更一般的运输型距离的措施，不同的质量，非标量信号或离散基空间的系统研究已引起越来越多的关注。这些发展仍处于非常早期的阶段，在这一点上，基本问题是开放的，我相信，许多令人兴奋的发展还没有到来。此外，虽然已经有一个广泛的数值方法的最佳运输今天的情况还不令人满意。计算上最有效的方法通常不是很灵活，而更灵活的方法往往效率低得多。此外，许多启发式方法，以减少计算的复杂性提供了没有数学保证，他们的validity.This项目打算解决的理论和实践方面的最佳运输。我们将为非标量数据和离散基空间开发新的传输型距离。此外，我们将努力更深入地理解传输优化问题的几何结构，以开发快速、灵活且数学上合理的新算法。这些目标将共同拓宽数据分析应用的最优传输的理论和实践范围。