Numerical analysis and extensions for 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.