On Robust Wasserstein Barycenter: The Model and Algorithm
Xu Wang Jiawei Huang Qingyuan Yang Jinpeng Zhang
The Wasserstein barycenter problem is to compute the average of $m$ given
probability measures, which has been widely studied in many different areas;
however, real-world data sets are often noisy and huge, which impedes its
applications in practice. Hence, in this paper, we focus on improving the
computational efficiency of two types of robust Wasserstein barycenter problem
(RWB): fixed-support RWB (fixed-RWB) and free-support RWB (free-RWB); actually,
the former is a subroutine of the latter. Firstly, we improve efficiency
through model reducing; we reduce RWB as an augmented Wasserstein barycenter
problem, which works for both fixed-RWB and free-RWB. Especially, fixed-RWB can
be computed within $\widetilde{O}(\frac{mn^2}{\epsilon_+})$ time by using an
off-the-shelf solver, where $\epsilon_+$ is the pre-specified additive error
and $n$ is the size of locations of input measures. Then, for free-RWB, we
leverage a quality guaranteed data compression technique, coreset, to
accelerate computation by reducing the data set size $m$. It shows that running
algorithms on the coreset is enough instead of on the original data set. Next,
by combining the model reducing and coreset techniques above, we propose an
algorithm for free-RWB by updating the weights and locations alternatively.
Finally, our experiments demonstrate the efficiency of our techniques.