Opening book details…
Can I read On the computational complexity of finding a sparse Wasserstein barycenter on EtoBox?
On the computational complexity of finding a sparse Wasserstein barycenter by Steffen Borgwardt; Stephan Patterson is a Computer Science article available to read on EtoBox.
What is On the computational complexity of finding a sparse Wasserstein barycenter about?
The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of probability measures with finite support. In this paper, we show that finding a barycenter of sparse support is hard, even in dimension 2 and for only 3 measures. We prove this claim by showing that a special case of an intimately related decision problem SCMP-does there exist a measure with a non-mass-splitting transport cost and support size below prescribed bounds? Is NP-hard for all rational data. Our proof is based on a reduction from planar 3-dimensional matching and follows a strategy laid out by Spieksma and Woeginger (Eur J Oper Res 91:611-618, 1996) for a reduction to planar, minimum circumference 3-dimensional matching. While we closely mirror the actual steps of their proof, the arguments themselves differ fundamentally due to the complex nature of the discrete barycenter problem. Containment of SCMP in NP will remain open. We prove that, for a given measure, sparsity and cost of an optimal transport to a set of measures can be verified in polynomial time in the size of a bit encoding of the measure. However, the encoding size of a barycenter may be exponential in the encod
Who reads On the computational complexity of finding a sparse Wasserstein barycenter?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Steffen Borgwardt; Stephan Patterson
- Publisher
- Springer Science and Business Media LLC
- Published
- 2021
- Language
- EN
- Field
- Computer Science (Physical Sciences)