Numerical analysis and extensions for optimal transport

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

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.