Initialization Procedures for Discrete and Semi-Discrete Optimal Transport. (October 2019)

• Record Type: Journal Article
• Authors: Meyron, Jocelyn
• Is Part Of: Computer aided design. Volume 115(2019)
• Page Start: 13
• Page End: 22
• Publication Date: 2019-10
• Subjects: Optimal transport -- Laguerre diagram -- Computational geometry -- Newton method -- Entropic regularization; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2019.05.037
• Languages: English
• ISSNs: 0010-4485

Abstract

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.