  Wasserstein 1 optimal transport maps provide a natural correspondence between
points from two probability distributions, $\mu$ and $\nu$, which is useful in
many applications. Available algorithms for computing these maps do not appear
to scale well to high dimensions. In deep learning applications, efficient
algorithms have been developed for approximating solutions of the dual problem,
known as Kantorovich potentials, using neural networks (e.g. [Gulrajani et al.,
2017]). Importantly, such algorithms work well in high dimensions. In this
paper we present an approach towards computing Wasserstein 1 optimal transport
maps that relies only on Kantorovich potentials. In general, a Wasserstein 1
optimal transport map is not unique and is not computable from a potential
alone. Our main result is to prove that if $\mu$ has a density and $\nu$ is
supported on a submanifold of codimension at least 2, an optimal transport map
is unique and can be written explicitly in terms of a potential. These
assumptions are natural in many image processing contexts and other
applications. When the Kantorovich potential is only known approximately, our
result motivates an iterative procedure wherein data is moved in optimal
directions and with the correct average displacement. Since this provides an
approach for transforming one distribution to another, it can be used as a
multipurpose algorithm for various transport problems; we demonstrate through
several proof of concept experiments that this algorithm successfully performs
various imaging tasks, such as denoising, generation, translation and
deblurring, which normally require specialized techniques.
