Supplement to " On Robust Optimal Transport: Computational Complexity and Barycenter Computation "

In this supplementary material, we collect several proofs and remaining materials that are deferred from the main paper. In Appendix A, we introduce and recall necessary notations for the supplementary material. In Appendix B, we provide key lemmas and proofs for the computational complexity of robust semi-constrained optimal transport (RSOT), and those regarding ROT are in Appendix D. Appendix C is devoted to the lemmas and proofs for the computational complexity of robust semi-constrained barycenter (RSBP). We provide the proof for computational complexity of robust Sinkhorn algorithms via Nyström approximation in Appendix E. Finally, we present additional experiment studies with the proposed robust algorithms in Appendix F. This appendix aims to introduce some notations that will be used intensively in the subsequent parts of the appendix. We start with the meaning of notations for the general case, and those for remaining cases follow similarly (see the table content).