Optimal Transportation: A Comprehensive Review and Novel Approaches Público

Abstract

This thesis explores optimal transport (OT) with a focus on improving computational efficiency and generalization through novel partitioning strategies in no-collision transportation maps. The first part provides a comprehensive review of the theoretical foundations and computational techniques in classical OT, including the Monge and Kantorovich problems, Kantorovich duality, and various transportation distances such as the Wasserstein metric and Linearized Optimal Transport (LOT). It critically examines established computational methods like the North-West Corner Method, Network Simplex Algorithm, and Auction Algorithm, highlighting their strengths and limitations.

The second part introduces alternative partitioning strategies that challenge the traditional vertical-horizontal partitioning methods in no-collision transportation maps. It proposes and rigorously tests two new partitioning techniques—random and PCA-based partitioning—analyzing their computational efficiency and generalization capabilities. The results demonstrate the potential of these strategies to improve both the scalability and robustness of OT solutions, offering new avenues for their application in complex fields such as finance and economics.

Table of Contents

Contents

Introduction

2. State of the Art

2.1. Optimal Transportation Preliminaries

2.1.1. Measures

2.1.2. Monge Problem

2.1.3. Kantorovich Problem

2.1.4. Kantorovich Duality

2.2. Review of Computational Techniques for Optimal Transportation

2.2.1. North-West Corner Method

2.2.2. Network Simplex Algorithm

2.2.3. Auction Algorithm

2.3. Limitations of Current Works

3. lternative Transportation Distances

3.1. Wasserstein Metric

3.1.1. Intuition Behind Wasserstein Metric

3.1.2. Concept Definitions

3.1.3. Advantages of Wasserstein Metric

3.2. Sliced Wasserstein Matrix

3.3. Linearized Optimal Transportation (LOT)

3.3.1. Intuition Behind LOT

3.3.2. Concept Definitions

3.3.3. Procedures of Linearized Optimal Transportation

3.3.4. Analysis of LOT

3.4. No-Collision Transportation Maps

3.4.1. Intuition Behind No-Collision

3.4.2. Concepts Definition

3.4.3. Construction of No-Collision Maps

4. Theoretical Framework

4.1. Traditional Horizontal and Vertical Splits

4.1.1. Rationale

4.1.2. Theoretical Robustness

4.2. Random Split

4.2.1. Rationale

4.2.2. Visualization

4.2.3. Theoretical Robustness

4.3. PCA-based Split

4.3.1. Rationale

4.3.2. Visualization

4.3.3. Theoretical Robustness

4.4. Comparative Analysis of Robustness

5. Computational Results

5.1. Experimental Settings

5.2. Methodology Implementation

5.2.1. Pseudo-code

5.3. Results

5.3.1. Exponential Distribution

5.3.2. Normal Distribution

6. Conclusion and Future Work

6.1. Conclusion

6.2. Implications for Future Research

About this Honors Thesis

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Mathematics
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Mathematics Computer Science Operations Research
Palavra-chave	No-collision Maps Optimal Transport
Committee Chair / Thesis Advisor	Levon Nurbekyan, Emory University
Committee Members	Elizabeth Newman, Emory University Ruoxuan Xiong, Emory University

Última modificação

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Optimal Transportation: A Comprehensive Review and Novel Approaches ()	2024-12-11 11:52:22 -0500	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions