A Fast Algorithm for Optimal Transport
summary
An algorithm alternates gradient ascent on duals with fast computation of the c-transform and uses the known explicit c-transform gradient (McCann) so each iteration runs in time essentially independent of image size; it computes optimal transport maps on high‑resolution (megapixel) 2D images and produces particle trajectories and W2 gradient‑flow simulations that keep sharp interfaces. Implementation discretizes last, uses H1 metric for descent, works best for separable or strictly convex costs, and currently lacks a global convergence rate (one step provably improves).
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:30The optimal transport problem
- 0:592-dimensional example
- 1:49Displacement interpolant (BFM)
- 2:12The back-and-forth method (BFM) • Dual problem has two equivalent
- 3:59Some key details Correct metric for the infinite dimensional problem is the HA1 metric L^2 nom of function
- 5:12Monge to Kantorovich
- 5:30Application to W2 gradient flows
- 6:26Interesting/open directions
related talks
01h 04mOptimal Transport and PDE: Gradient Flows in the Wasserstein Metric (continued)
01h 22mComputational Optimal Transport
55mCrash Course on Optimal Transport (continued)
01h 02mCrash Course on Optimal Transport
59mOptimal Transport and PDE: Gradient Flows in the Wasserstein Metric
48mSketching Techniques for Kernel Density Estimation or for Optimal Transport Computations
01h 18mOptimization I
01h 19mGradient Flows and Optimal Transport in Discrete and Quantum Systems