Monge, Bregman and Occam: Interpretable Optimal Transport in High-Dimensions with Feature-Sparse Maps

Optimal transport (OT) theory focuses, among all maps that can morph a probability measure onto another, on those that are the “thriftiest”, i.e. such that the averaged cost between and its image be as small as possible. Many computational approaches have been proposed to estimate such Monge maps when is the distance, e.g., using entropic maps (Pooladian and Niles-Weed, 2021), or neural networks (Makkuva et al., 2020;
Korotin et al., 2020). We propose a new model for transport maps, built on a family of translation invariant costs , where and is a regularizer. We propose a generalization of the entropic map suitable for , and highlight a surprising link tying it with the Bregman centroids of the divergence generated by , and the proximal operator of . We show that choosing a sparsity-inducing norm for results in maps that apply Occam‘s razor to transport, in the sense that the displacement vectors they induce are sparse, with a sparsity pattern that varies depending on . We showcase the ability of our method to estimate meaningful OT maps for high-dimensional single-cell transcription data, in the – space of gene counts for cells, without using dimensionality reduction, thus retaining the ability to interpret all displacements at the gene level.