Initialization Procedures for Discrete and Semi-Discrete Optimal Transport. (October 2019) - Meyron, Jocelyn
Abstract: We propose three different methods to initialize optimal transport algorithms in both the discrete and semi-discrete settings. After introducing the optimal transport problem, we start by explaining why finding "good" (in a certain sense) initial weights is an important problem in computational optimal transport. We then describe three novel procedures to find such weights. Proofs of correctness are also given. We finally show on many numerical examples how choosing these weights improves the running times of optimal transport algorithms. We also describe some applications in various fields such as non-imaging optics; matching between a point cloud and a triangulated surface; seismic imaging. Highlights: Optimal transport algorithms can be made more efficient by using correct initial weights. Initial weights can be found using different methods adapted to multiple settings. Optimal transport can be used for many applications such as optical component design or seismic data analysis.