Finite-metric transport duality

Take a representation $x={\sum }_{i=1}^N{\lambda }_i{g}_i$ with every ${\lambda }_i\ge 0$ and let $S=\{i:{\lambda }_i>0\}$. If the sublist indexed by $S$ is dependent, [F2] gives coefficients $c_i$, not all zero, with ${\sum }_{i\in S}{c}_i{g}_i=0$. Reverse all signs if needed so $J=\{i\in S:c_i>0\}$ is nonempty, and set $t={\min }_{i\in J}{\lambda }_i\mathrm{/}{c}_i>0$ using [F4]. Define ${\lambda }_i^{\mathrm{\prime }}={\lambda }_i-t{c}_i$ for $i\in S$ and ${\lambda }_i^{\mathrm{\prime }}=0$ for $i\mathrm{\notin }S$. For $i\in S$ with $c_i>0$, the minimum choice makes ${\lambda }_i^{\mathrm{\prime }}\ge 0$ and makes at least one such coefficient zero; when $c_i\le 0$, ${\lambda }_i^{\mathrm{\prime }}\ge {\lambda }_i>0$. Thus every ${\lambda }_i^{\mathrm{\prime }}\ge 0$, the positive support strictly shrinks, and ${\sum }_{i=1}^N{\lambda }_i^{\mathrm{\prime }}{g}_i=x$. Each reduction loses at least one index and adds none to the support, which starts with at most $N$ indices, so after at most $N$ reductions the support is empty or linearly independent; the empty support is independent as well.

Fix a nonempty independent sublist indexed by $S=\{i_1,\dots ,i_s\}$, let $A:{\mathbb{R}}^s\to {\mathbb{R}}^r$ have these columns, and let $G=A^{\mathsf{T}}A$. If $Gz=0$, then $0=z^{\mathsf{T}}Gz=\mathrm{\parallel }Az{\mathrm{\parallel }}_2^2$, so [F1] gives $Az=0$ and [F2] gives $z=0$. Thus $G$ is invertible by [F3]. Put $B=G^{-1}{A}^{\mathsf{T}}$ and $P=AB$, so $BA=I$. The cone $C_S$ generated by this sublist is exactly $\{x\in {\mathbb{R}}^r:Px=x,(Bx{)}_k\ge 0\text{ for }k<s\}$: if $x=Az$ with $z\ge 0$, then $Bx=z$ and $Px=x$; conversely those displayed conditions give $x=Px=A(Bx)$ with nonnegative coefficients. Each coordinate of $Bx$ and $Px-x$ is a finite linear form $\mathrm{\ell }(x)={\sum }_{j<r}{c}_j{x}_j$. For $u\in {\mathbb{R}}^r$ and $k<r$, [F7] gives $u_k^2\le {\sum }_{j<r}{u}_j^2$; by [F5] and [F8], $\mathrm{\mid }{u}_k{\mathrm{\mid }}^2=u_k^2\le \mathrm{\parallel }u{\mathrm{\parallel }}_2^2$, and both $\mathrm{\mid }{u}_k\mathrm{\mid }$ and $\mathrm{\parallel }u{\mathrm{\parallel }}_2$ are nonnegative, so [F8] gives $\mathrm{\mid }{u}_k\mathrm{\mid }\le \mathrm{\parallel }u{\mathrm{\parallel }}_2$. For any finite list $a_0,\dots ,a_{n-1}$, induction using the two-term triangle inequality in [F8] gives $\mathrm{\mid }{\sum }_{j<n}{a}_j\mathrm{\mid }\le {\sum }_{j<n}\mathrm{\mid }{a}_j\mathrm{\mid }$: the empty case is equality and the successor step is the two-term triangle inequality. Applying this, the absolute-value product law, multiplication by nonnegative coefficients, and finite-sum monotonicity in [F7,F8] gives $\mathrm{\mid }\mathrm{\ell }(x)-\mathrm{\ell }(y)\mathrm{\mid }\le {\sum }_{j<r}\mathrm{\mid }{c}_j\mathrm{\mid }\mathrm{\mid }{x}_j-y_j\mathrm{\mid }\le ({\sum }_{j<r}\mathrm{\mid }{c}_j\mathrm{\mid })\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$. If an equation $\mathrm{\ell }(x)=0$ fails at $x_0$, then $C_{\mathrm{\ell }}:={\sum }_{j<r}\mathrm{\mid }{c}_j\mathrm{\mid }>0$: otherwise [F7,F8] force every $c_j=0$, so $\mathrm{\ell }$ is identically zero. For $\mathrm{\parallel }x-x_0{\mathrm{\parallel }}_2<\mathrm{\mid }\mathrm{\ell }(x_0)\mathrm{\mid }\mathrm{/}(2C_{\mathrm{\ell }})$, the estimate gives $\mathrm{\mid }\mathrm{\ell }(x)-\mathrm{\ell }(x_0)\mathrm{\mid }<\mathrm{\mid }\mathrm{\ell }(x_0)\mathrm{\mid }\mathrm{/}2$, hence $\mathrm{\ell }(x)\mathrm{\ne }0$. The same positivity of $C_{\mathrm{\ell }}$ holds when an inequality $\mathrm{\ell }(x)\ge 0$ fails; throughout the ball of radius $-\mathrm{\ell }(x_0)\mathrm{/}(2C_{\mathrm{\ell }})$, the estimate gives $\mathrm{\ell }(x)<\mathrm{\ell }(x_0)\mathrm{/}2<0$. Thus every point outside $C_S$ has a ball in its complement; by [F5,F6] that complement is open and $C_S$ is closed. For the empty sublist, $C_{\mathrm{\varnothing }}=\{0\}$: if $x\mathrm{\ne }0$, then $d_2(x,0)>0$ by [F5,F9], and every $y$ with $d_2(x,y)<d_2(x,0)\mathrm{/}2$ is nonzero, since otherwise the triangle inequality would give $d_2(x,0)<d_2(x,0)\mathrm{/}2$. Thus the complement of $\{0\}$ is open by [F6], so $C_{\mathrm{\varnothing }}$ is closed.

By step 1.1, every $x\in C$ belongs to $C_S$ for some independent subset $S$ of the $N$ generators; conversely every such $C_S$ is contained in $C$. There are only finitely many subsets $S$, and the empty subset is included. For any $x\mathrm{\notin }C$, each closed $C_S$ has an open complement containing $x$; choosing one positive ball radius for each of the finitely many such complements and taking their positive minimum gives a ball about $x$ disjoint from their union. Thus $C$ has open complement and is closed. For $x,y\in C$, choose coefficients ${\lambda }_i,{\mu }_i\ge 0$ with $x={\sum }_{i=1}^N{\lambda }_i{g}_i$ and $y={\sum }_{i=1}^N{\mu }_i{g}_i$. Then $\alpha x+\beta y={\sum }_{i=1}^N(\alpha {\lambda }_i+\beta {\mu }_i)g_i\in C$ for all $\alpha ,\beta \ge 0$, proving the stated closure under nonnegative linear combinations.

Define ${\pi }_{ij}=p_i{q}_j$. These entries are nonnegative by [F1], and their row sums are $p_i{\sum }_j{q}_j=p_i$ while their column sums are $q_j{\sum }_i{p}_i=q_j$. Thus $\pi \in \mathrm{\Gamma }(p,q)$ and the coupling set is nonempty.

Flatten a matrix into ${\mathbb{R}}^{m^2}$ in row-major order, assigning entry ${\pi }_{ij}$ to library coordinate $k=(i-1)m+(j-1)<m^2$; likewise potential coordinate $f_i$ corresponds to library coordinate $i-1<m$. In any dimension $n\ge 1$, for $u\in {\mathbb{R}}^n$ and $k<n$, [F11] gives $u_k^2\le {\sum }_{j<n}{u}_j^2$; by [F5,F11], $\mathrm{\mid }{u}_k{\mathrm{\mid }}^2=u_k^2\le d_2(u,0{)}^2$, and both $\mathrm{\mid }{u}_k\mathrm{\mid }$ and $d_2(u,0)$ are nonnegative, so [F11] gives $\mathrm{\mid }{u}_k\mathrm{\mid }\le d_2(u,0)$. By induction on $n$, every finite list satisfies $\mathrm{\mid }{\sum }_{k<n}{a}_k\mathrm{\mid }\le {\sum }_{k<n}\mathrm{\mid }{a}_k\mathrm{\mid }$: the empty case is equality and the successor step follows from $\mathrm{\mid }a+b\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }+\mathrm{\mid }b\mathrm{\mid }$ in [F11]. Thus for every finite linear form $L(z)={\sum }_{k<n}{c}_k{z}_k$, this bound, $\mathrm{\mid }ab\mathrm{\mid }=\mathrm{\mid }a\mathrm{\mid }\mathrm{\mid }b\mathrm{\mid }$, the coordinate estimate, multiplication by nonnegative coefficients, finite-sum monotonicity and scaling in [F11] give $\mathrm{\mid }L(z)-L(w)\mathrm{\mid }\le ({\sum }_{k<n}\mathrm{\mid }{c}_k\mathrm{\mid })d_2(z,w)$. The same estimate holds for every affine form $H(z)=L(z)+b$, since the constant cancels in $H(z)-H(w)$. The set $\mathrm{\Gamma }(p,q)$ is defined by finitely many affine equalities and weak inequalities. Each row or column equality, after moving its marginal to one side, has $m$ coefficients equal to $1$; each entrywise nonnegativity constraint has one coefficient equal to $1$, so the coefficient sum $C=\sum \mathrm{\mid }{c}_k\mathrm{\mid }$ is positive for every constraint. If an affine equality $H(z)=0$ fails at $z_0$, then for $d_2(z,z_0)<\mathrm{\mid }H(z_0)\mathrm{\mid }\mathrm{/}(2C)$ the estimate gives $\mathrm{\mid }H(z)-H(z_0)\mathrm{\mid }<\mathrm{\mid }H(z_0)\mathrm{\mid }\mathrm{/}2$, so $H(z)\mathrm{\ne }0$. If an affine inequality $H(z)\ge 0$ fails at $z_0$, then for $d_2(z,z_0)<-H(z_0)\mathrm{/}(2C)$ the estimate gives $H(z)<H(z_0)\mathrm{/}2<0$. Thus every point outside $\mathrm{\Gamma }(p,q)$ has a ball in its complement, so [F5,F6] make $\mathrm{\Gamma }(p,q)$ closed. Also $0\le {\pi }_{ij}\le p_i\le 1$ by [F1,F2], so the set is bounded. Since $m^2\ge 1$, [F6] makes $\mathrm{\Gamma }(p,q)$ compact.

For a matrix difference $z-w$, the objective changes by at most $C{d}_2(z,w)$, where $C={\sum }_{i,j}d(x_i,x_j)\ge 0$ is finite; the coordinate bound is the same as in step 1.2. For any $\epsilon >0$, taking $\delta =\epsilon \mathrm{/}(C+1)$ shows that inputs within $\delta$ have output difference less than $\epsilon$, so the objective is continuous by [F8] and lower semicontinuous by [F9]. It is real-valued because all distances are finite reals; by [F4] and [F1] its values are nonnegative. The nonempty compact set from steps 1.1–1.2 and [F7] therefore give a finite attained minimum, which is $W_1(p,q)$ by [F10].

The set ${\mathcal{L}}_1(X,d)$ contains the zero vector. It is closed because its constraints are finitely many linear equalities and weak inequalities: $f_1=0$ has one nonzero coefficient, and writing each $\mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le d(x_i,x_j)$ as $d(x_i,x_j)-(f_i-f_j)\ge 0$ and $d(x_i,x_j)+(f_i-f_j)\ge 0$ gives two nonzero coefficients in each inequality when $i\mathrm{\ne }j$; when $i=j$ the constraint is the identity $0\le 0$. Thus every violated constraint has positive coefficient sum and the strict-violation ball argument in step 1.2 applies using [F5,F6,F11]. Since $f_1=0$ and $\mathrm{\mid }{f}_i-f_1\mathrm{\mid }\le d(x_i,x_1)$, every $f\in {\mathcal{L}}_1(X,d)$ satisfies $\mathrm{\mid }{f}_i\mathrm{\mid }\le d(x_i,x_1)\le 1+{\sum }_{k=1}^{m}d(x_k,x_1)$ by [F3,F4]; thus the set is bounded. Since $m\ge 1$, [F6] makes it compact.

The objective $f\mapsto {\sum }_i(p_i-q_i)f_i$ changes by at most $C^{\mathrm{\prime }}{d}_2(f,g)$, where $C^{\mathrm{\prime }}={\sum }_i\mathrm{\mid }{p}_i-q_i\mathrm{\mid }\ge 0$; taking $\delta =\epsilon \mathrm{/}(C^{\mathrm{\prime }}+1)$ for each $\epsilon >0$ proves continuity by [F8] and upper semicontinuity by [F9]. The nonempty compact set from step 2.2 and [F7] give an attained maximum.

For any $\pi \in \mathrm{\Gamma }(p,q)$ and any $f\in {\mathbb{R}}^m$ with $f_1=0$ and $\mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le d(x_i,x_j)$, the marginal equations give ${\sum }_i(p_i-q_i)f_i={\sum }_{i,j}{\pi }_{ij}(f_i-f_j)\le {\sum }_{i,j}{\pi }_{ij}d(x_i,x_j)$. The inequality uses ${\pi }_{ij}\ge 0$ and $f_i-f_j\le \mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le d(x_i,x_j)$. Thus every feasible dual value is at most every feasible primal cost.

Write $d_{ij}=d(x_i,x_j)$, and for $i=1,\dots ,m$ let $e_i\in {\mathbb{R}}^m$ have value $1$ at library coordinate $k=i-1$ and $0$ at every other coordinate. For alphabet-indexed tuples $u=(u_i{)}_{i=1}^m$ and $v=(v_j{)}_{j=1}^m$, identify $(u,v,t)$ with the vector in ${\mathbb{R}}^{2m+1}$ whose coordinate $k<m$ is $u_{k+1}$, whose coordinate $m+k$ is $v_{k+1}$, and whose coordinate $2m$ is $t$. Let $K$ be the nonnegative span of $(e_i,e_j,d_{ij})$ for all $i,j$, together with $(0,0,1)$. By [F7], $K$ is closed and closed under nonnegative linear combinations. For $x,y\in K$ and $s\in [0,1]$, [F7] gives $sx+(1-s)y\in K$, so [F11] makes $K$ convex; the zero representation gives $0\in K$. Put $c_{\ast }=W_1(p,q)$, which is finite and attained by [F6]. For every $\epsilon >0$, the vector $y_{\epsilon }=(p,q,c_{\ast }-\epsilon )$ under this identification is outside $K$: if it had a representation with coefficients ${\lambda }_{ij}\ge 0$ and $t\ge 0$, its first two coordinate blocks would make $\lambda \in \mathrm{\Gamma }(p,q)$ and its last coordinate would give $c_{\ast }-\epsilon ={\sum }_{i,j}{d}_{ij}{\lambda }_{ij}+t\ge c_{\ast }$, contradicting minimality.

Apply [F8] to $K$ and $y_{\epsilon }$. It gives a vector $h$ and threshold $\beta$ with $⟨h,z⟩\le \beta <⟨h,y_{\epsilon }⟩$ for all $z\in K$. Since $0\in K$, $\beta \ge 0$. By [F7], $sz\in K$ for every $z\in K$ and $s\ge 0$. If $c:=⟨h,z⟩>0$ for some $z\in K$, take $s=(\beta +1)\mathrm{/}c>0$; then $sz\in K$ but $⟨h,sz⟩=\beta +1>\beta$, a contradiction. Hence $⟨h,z⟩\le 0$ for every $z\in K$, while $⟨h,y_{\epsilon }⟩>0$.

Decompose $h=(a,b,g)$ with $a,b\in {\mathbb{R}}^m$ and $g\in \mathbb{R}$. By [F10], pairing with $(0,0,1)\in K$ gives $g\le 0$. If $g=0$, pairing with every $(e_i,e_j,d_{ij})$ gives $a_i+b_j\le 0$. Multiplying by $p_i{q}_j\ge 0$ and summing yields ${\sum }_i{p}_i{a}_i+{\sum }_j{q}_j{b}_j={\sum }_{i,j}{p}_i{q}_j(a_i+b_j)\le 0$. When $g=0$ this left-hand side is $⟨h,y_{\epsilon }⟩$, contrary to step 2.1. Therefore $g<0$.

Define $u_i=a_i\mathrm{/}(-g)$ and $v_j=b_j\mathrm{/}(-g)$. The generator inequalities and $g<0$ give $u_i+v_j\le d_{ij}$ for all $i,j$. Dividing the strict point inequality by $-g>0$ gives ${\sum }_i{p}_i{u}_i+{\sum }_j{q}_j{v}_j>c_{\ast }-\epsilon$.

Set $f_i={\min }_{1\le j\le m}(d_{ij}-v_j)$, whose minimum is attained by [F9]. From $u_i+v_j\le d_{ij}$ we have $u_i\le f_i$. For any $i,k,j$, the triangle inequality gives $d_{ij}-v_j\le d_{ik}+d_{kj}-v_j$; taking finite minima yields $f_i\le d_{ik}+f_k$, and symmetry gives $\mathrm{\mid }{f}_i-f_k\mathrm{\mid }\le d_{ik}$. Also $f_j\le d_{jj}-v_j=-v_j$, so $-f_j\ge v_j$. Since $p,q$ are nonnegative, ${\sum }_i(p_i-q_i)f_i\ge {\sum }_i{p}_i{u}_i+{\sum }_j{q}_j{v}_j>c_{\ast }-\epsilon$. Replacing $f_i$ by $f_i-f_1$ preserves all Lipschitz inequalities and the objective because ${\sum }_i{p}_i={\sum }_i{q}_i=1$; the resulting vector is normalized with first coordinate zero.

Let $D$ be the attained maximum in [F6]. Step 5.1 shows $D>c_{\ast }-\epsilon$ for every $\epsilon >0$, so $D\ge c_{\ast }$; otherwise $\epsilon =(c_{\ast }-D)\mathrm{/}2$ contradicts that inequality. Step 1.1 gives $D\le c_{\ast }$. Hence $D=c_{\ast }=W_1(p,q)$, and both extrema are attained by [F6].

Let $\pi$ be any minimizing coupling and $f$ any maximizing normalized potential. By the marginal equations and optimal-value equality, $0=c_{\ast }-{\sum }_i(p_i-q_i)f_i={\sum }_{i,j}{\pi }_{ij}(d_{ij}-(f_i-f_j))$. Each summand is nonnegative by feasibility. A finite sum of nonnegative reals can be zero only if each term is zero: if one term were positive, adding the other nonnegative terms would keep the total positive. Thus if ${\pi }_{ij}>0$, its factor $d_{ij}-(f_i-f_j)$ is zero, proving $f_i-f_j=d_{ij}$.