More Like this

1. A geometric variational framework for computing optimal transportation maps, I

   https://doi.org/10.4310/MCGD.2021.v1.n2.a3  

   An, Dongsheng; Lei, Na; Cui, Li; Su, Kehua; Xu, Xiaoyin; Luo, Feng; Gu, Xianfeng; Yau, Shing-Tung (January 2021, Mathematics, Computation and Geometry of Data)

   Optimal transportation (OT) maps play fundamental roles in many engineering and medical fields. The computation of optimal transportation maps can be reduced to solve highly non-linear Monge-Ampere equations. In this work, we summarize the geometric variational framework to solve optimal transportation maps in Euclidean spaces. We generalize the method to solve worst transportation maps and discuss about the symmetry between the optimal and the worst transportation maps. Many algorithms from computational geometry are incorporated into the method to improve the efficiency, the accuracy and the robustness of computing optimal transportation. 

   more » « less
2. AE-OT: A new generative Model Based on Extended Semi-discrete Optimal Transport

   An, Dongsheng; Guo, Yang; Lei, Na; Luo, Zhongxuan; Yau, Shing-Tung; Gu, Xianfeng. (January 2019, ICLR 2020)

   Generative adversarial networks (GANs) have attracted huge attention due to its capability to generate visual realistic images. However, most of the existing models suffer from the mode collapse or mode mixture problems. In this work, we give a theoretic explanation of the both problems by Figalli’s regularity theory of optimal transportation maps. Basically, the generator compute the transportation maps between the white noise distributions and the data distributions, which are in general discontinuous. However, DNNs can only represent continuous maps. This intrinsic conflict induces mode collapse and mode mixture. In order to tackle the both problems, we explicitly separate the manifold embedding and the optimal transportation; the first part is carried out using an autoencoder to map the images onto the latent space; the second part is accomplished using a GPU-based convex optimization to find the discontinuous transportation maps. Composing the extended OT map and the decoder, we can finally generate new images from the white noise. This AE-OT model avoids representing discontinuous maps by DNNs, therefore effectively prevents mode collapse and mode mixture. 

   more » « less
3. FFT-OT: A Fast Algorithm for Optimal Transportation

   Lei, Na; Gu, Xianfeng (July 2021, Proceedings of International Conference on Computer Vision (ICCV))

   null (Ed.)

   An optimal transportation map finds the most economical way to transport one probability measure to the other. It has been applied in a broad range of applications in vision, deep learning and medical images. By Brenier theory, computing the optimal transport map is equivalent to solving a Monge-Amp\`ere equation. Due to the highly non-linear nature, the computation of optimal transportation maps in large scale is very challenging. This work proposes a simple but powerful method, the FFT-OT algorithm, to tackle this difficulty based on three key ideas. First, solving Monge-Amp\`ere equation is converted to a fixed point problem; Second, the obliqueness property of optimal transportation maps are reformulated as Neumann boundary conditions on rectangular domains; Third, FFT is applied in each iteration to solve a Poisson equation in order to improve the efficiency. Experiments on surfaces captured from 3D scanning and reconstructed from medical imaging are conducted, and compared with other existing methods. Our experimental results show that the proposed FFT-OT algorithm is simple, general and scalable with high efficiency and accuracy. 

   more » « less
4. Throughput-Optimal Scheduling for Multi-Hop Networked Transportation Systems With Switch-Over Delay

   https://doi.org/10.1145/3084041.3084065  

   Hsieh, Ping-Chun; Liu, Xi; Jiao, Jian; Hou, I-Hong; Zhang, Yunlong; Kumar, P. R. (January 2017, 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing)

   The emerging connected-vehicle technology provides a new dimension for developing more intelligent traffic control algorithms for signalized intersections. An important challenge for scheduling in networked transportation systems is the switchover delay caused by the guard time before any traffic signal change. The switch-over delay can result in significant loss of system capacity and hence needs to be accommodated in the scheduling design. To tackle this challenge, we propose a distributed online scheduling policy that extends the wellknown Max-Pressure policy to address switch-over delay by introducing a bias factor favoring the current schedule. We prove that the proposed policy is throughput-optimal with switch-over delay. Furthermore, the proposed policy remains optimal when there are both connected signalized intersections and conventional fixed-time ones in the system. With connected-vehicle technology, the proposed policy can be easily incorporated into the current transportation systems without additional infrastructure. Through extensive simulation in VISSIM, we show that our policy indeed outperforms the existing popular policies. 

   more » « less
5. A Moving Mesh Adaption Method By Optimal Transport

   An, Dongsheng; Lei, Na; Zhao, Tong; Si, Hang; Gu, Xianfeng (October 2021, Proceedings of International Meshing Roundtable)

   null (Ed.)

   Optimal transportation finds the most economical way to transport one probability measure to another, and it plays an important role in geometric modeling and processing. In this paper, we propose a moving mesh method to generate adaptive meshes by optimal transport. Given an initial mesh and a scalar density function defined on the mesh domain, our method will redistribute the mesh nodes such that they are adapted to the density function. Based on the Brenier theorem, solving an optimal transportation problem is reduced to solving a Monge-Amp\`ere equation, which is difficult to compute due to the high non-linearity. On the other hand, the optimal transportation problem is equivalent to the Alexandrov problem, which can finally induce an effective variational algorithm. Experiments show that our proposed method finds the adaptive mesh quickly and efficiently. 

   more » « less