Linear Optimal Transport

The classical optimal transport problem seeks to determine how to rearrange one pile of dirt to look like a different pile of dirt using the least amount of effort. By interpreting piles of dirt as pixel intensities, discrete optimal transport has desirable properties for machine learning algorithms but often times is an impractical method for processing large-scale data sets of images. To offset computational cost, Wang et al. introduced a linearized optimal transport (LOT) approximation scheme which significantly reduces the computational complexity associated with the image comparison task. This project investigates the relationship between linearized optimal transport and discrete optimal transport by proving inequalities relating the metrics and numerically investigating their sharpness. —