dba31bb5c75992690f20c2d3b370ec7c-Supplemental.pdf

Optimal partial transport: We prove the contraposition of Theorem 2 for the optimal partial transport distance. Suppose there exists an algorithm that computes the optimal partial transport distance inO(n2 ε)timeforsomeε>0ind=ω(logn)dimensionalLpmetric space. In a leaf nodev, tv is convex from Eq.(1). Iftx is convex,ex is convex from Eq. (2) because both|x| w(v,p(v)) and tx are convex. Ifev and eu are convex,tp,x is convex from Eq. (3).