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

In Appendix A, we introduce and recall necessary notations for the supplementary material. Appendix D. Appendix C is devoted to the lemmas and proofs for the computational complexity of B.1 Useful Lemmas We first start with the following useful lemmas for the proof of Theorem 1. Lemma 3. The following inequalities are true for all positive x Proof of Lemma 3. (a) It follows from the assumption x This directly leads to the conclusion. The desired inequalities are equivalent to upper and lower bounds for the second term of the RHS. W e have following upper bounds for the optimal solutions of RSOT's dual form, which is Proof of Lemma 5. First, we will show that null u Finally, applying Lemma 5, we obtain the conclusion.B.2 Detailed Proof of Theorem 1 Denoting k Subsequently, the two terms in the right-hand side can be bounded separately as follows. The main idea for deriving this bound comes from the geometric convergence rate (i.e.