UE Numerical optimal transport and geometry

Degrees incorporating this pedagocial element :

Description

Optimal transport is an important field of mathematics that was originally introduced in the 1700's by the French mathematician and engineer Gaspard Monge to solve the following very applied problem: what is the cheapest way of sending a pile of sand to a hole, knowing the cost of transportation of each sand grain of the pile to a possible target location ? This very applied problem gave the birth of the theory of optimal transport. This theory has connections with PDEs, geometry and probability and has been used in many fields such as computer vision, economy, non-imaging optics… In the last 15 years, this problem has been extensively studied from a computational point of view and different efficient algorithms have been proposed.

The goal of this course is to introduce basics on the optimal transport theory and to present the recent algorithms that have been shown to be very efficient. We will first focus on the discrete setting that corresponds to the transportation between discrete measures, with the entropic relaxation and the Sinkorn algorithm. We will then study the semi-discrete setting that corresponds to transporting a continuous measure to a discrete one. This has connections with computational geometry and can be solved efficiently with Newton algorithms. We will also present applications in different fields such as image processing and geometric optics.

Evaluation : written test/presentation of a research paper.

Prerequisites

Not particularly