Unbalanced optimal transport (UOT) has recently gained much attention due to
its flexible framework for handling un-normalized measures and its robustness
properties. In this work, we explore learning (structured) sparse transport
plans in the UOT setting, i.e., transport plans have an upper bound on the
number of non-sparse entries in each column (structured sparse pattern) or in
the whole plan (general sparse pattern). We propose novel sparsity-constrained
UOT formulations building on the recently explored maximum mean discrepancy
based UOT. We show that the proposed optimization problem is equivalent to the
maximization of a weakly submodular function over a uniform matroid or a
partition matroid. We develop efficient gradient-based discrete greedy
algorithms and provide the corresponding theoretical guarantees. Empirically,
we observe that our proposed greedy algorithms select a diverse support set and
we illustrate the efficacy of the proposed approach in various applications.

探索在不平衡最优输运 (UOT) 设置中学习稀疏输运规划，提出基于最大均值差异 UOT 的稀疏约束优化问题，开发了高效的基于梯度的离散贪婪算法，并在多个应用中验证了该方法的有效性。