Abstract: We consider a general task called partial Wasserstein covering with the goal
of emulating a large dataset (e.g., application dataset) using a small dataset
(e.g., development dataset) in terms of the empirical distribution by selecting
a small subset from a candidate dataset and adding it to the small dataset. We
model this task as a discrete optimization problem with partial Wasserstein
divergence as an objective function. Although this problem is NP-hard, we prove
that it has the submodular property, allowing us to use a greedy algorithm with
a 0.63 approximation. However, the greedy algorithm is still inefficient
because it requires linear programming for each objective function evaluation.
To overcome this difficulty, we propose quasi-greedy algorithms for
acceleration, which consist of a series of techniques such as sensitivity
analysis based on strong duality and the so-called $C$-transform in the optimal
transport field. Experimentally, we demonstrate that we can efficiently make
two datasets similar in terms of partial Wasserstein divergence, including
driving scene datasets.