  The Wasserstein distance received a lot of attention recently in the
community of machine learning, especially for its principled way of comparing
distributions. It has found numerous applications in several hard problems,
such as domain adaptation, dimensionality reduction or generative models.
However, its use is still limited by a heavy computational cost. Our goal is to
alleviate this problem by providing an approximation mechanism that allows to
break its inherent complexity. It relies on the search of an embedding where
the Euclidean distance mimics the Wasserstein distance. We show that such an
embedding can be found with a siamese architecture associated with a decoder
network that allows to move from the embedding space back to the original input
space. Once this embedding has been found, computing optimization problems in
the Wasserstein space (e.g. barycenters, principal directions or even
archetypes) can be conducted extremely fast. Numerical experiments supporting
this idea are conducted on image datasets, and show the wide potential benefits
of our method.
