Optimal Transport: intuition and solution

NB: tentative script from Tanguy's proposition


  • have a consistent color code (red to blue? transport in orange?)
  • use always actual values for the examples, ideally the same all around (or "similar" ones e.g. float close to previous int), ideally tunable to see how things change
  • not too much history or applications

TODO: intro sentence on the goal of the post?

global QUESTION: do we transition to a continuous version somewhere (punctually though) to be able to show 1D dense examples?

TODO: history OT and intro of it

  • 1 sentence for monge-like, explain moving mass

    TK: P1 1 sentence for Monge. Moving mass explanation.Image of 1D OT with barycentre

  • image for 1D transport + barycenter? (not sure how to introduce it right now)
  • ant with bricks? if people want to have something slow to understand
  • maybe insist (and start some maths) on the fact that the cost depends on the distance and the mass transported (linearly)
  • always put the unit in the cost as "cost/mass" (e.g. "effort/brick" "effort/kg")
  • see that we need to split the mass
  • switch to float mass?
  • maybe instead of soldier, use some liquid (water? beer? wine?) or if we took bricks some quantity of sand or gravel or something else continuous

TODO: Visualizing the transport plan

  • more 1D transports? (small videos like in ot-demo) to get an intuition of the intermediate state / barycenter (idea set of curves with small offset, to see as a no-animation, maybe a gridmesh... but manually to avoid the density/precision compromise)
  • an precomputed example with very few points to make the transition (saying that each point has the same mass for simplification)
  • explain that all points are moved at the same time (e.g. we have an army of ants), and we see their intermediate position, (and that this is the equivalent of a barycenter ?)
  • more examples using the precomputed
α = 0.50

TODO: How to solve it: Sinkhorn Algorithm

TK: The real word is in 2D: Kantorovich. Soldier experiment and representation, this give a "real" application that will be kept during the entire experiment thus the value of the cost matrix should be taken from a real 2D space to allow representation. Detail that one function can not define all, representation that allow to modify the transport plan (interactively ?) or just video that search manually for the OT. Put all the mathematical detail with clear explanation. For each mathematical detail, use the basic example in the figure with real number ()