Ph.D. Proposal Defense: Dongsheng An, 'The Computation of Optimal Transport and its Applications'

Friday, December 3, 2021 - 1:30pm to 2:30pm
Zoom - contact for Zoom information.
Event Description: 

Optimal transport (OT) finds the most economical way to transport one measure to another and plays an important role in the areas including geometric modeling and processing, computer vision, machine learning, economics and even life science. However, the computation of optimal transport with high efficiency and accuracy is still challenging. In this work, we propose different methods to solve the optimal transport problem under different settings.

 We propose a novel algorithm based on Nesterov's smoothing technique to improve the accuracy for solving the discrete OT problem. The c-transform of the Kantorovich potential is approximated by the smooth Log-Sum-Exp function, and the smoothed Kantorovich functional can be solved by FISTA efficiently. Theoretically, the computational complexity of the proposed method is given by $O(n^{2.5} \sqrt{\log n} /\varepsilon)$, which is lower than current estimation of the Sinkhorn method. For the semi-discrete optimal transport problem, we introduce a novel method to improve the computational efficiency and robustness of the OT map from any given piecewise linear source measure to the discrete target measure based on the geometric variational approach. Specifically, the generalized Lawson's edge flip method is used to improve the efficiency when updating the convex hull, and the sweep convex polygon algorithm can efficiently and robustly compute the overlay of two cell decomposition. Our experiments show that the proposed method is 5 to 10 times faster than the conventional methods, and more robust when handling complex source measures. To solve the continuous optimal transport problem, we propose the FFT-OT method. According to the Brenier theory, under the quadratic distance cost, finding the solution to the OT problem is equivalent to solving the Monge-Amp\`ere equation, which can be linearized as a sequence of variant coefficient elliptic PDEs. Later, the variant coefficient PDEs are approximated by constant coefficient PDEs and solved by Fast Fourier Transformation. We also prove that the proposed method converges linearly. Finally, we give a theoretic explanation for the mode collapse and mode mixture phenomena of the current generative models including GANs and VAEs by Brenier's theory and Figalli's regularity theory of optimal transport maps. When the target measure has concave support, the OT map is discontinuous on the singular sets. But DNNs can only represent continuous functions, this conflict causes both problems. In order to solve them, we propose the AE-OT model which separates the manifold embedding and measure transformation. The former step is computed using an autoencoder, and the latter is carried out using the extended semi-discrete OT map based on GPUs.

Title: The Computation of Optimal Transport and its Applications

Computed Event Type: 
Event Title: 
Ph.D. Proposal Defense: Dongsheng An, 'The Computation of Optimal Transport and its Applications'