2  Optimal Transport

$$ \newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}} \newcommand{\ForceToBe}[2]{\renewcommand{#1}{#2}} \newcommand{\forceToBe}[3]{\renewcommand{#1}[#2]{#3}} \newcommand{\MayThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\mayThereBe}[3]{\newcommand{#1}[#2]{#3}} % Declare mathematics (so they can be overwritten for PDF) \newcommand{\declareMathematics}[2]{\DeclareMathOperator{#1}{#2}} \newcommand{\declareMathematicsStar}[2]{\DeclareMathOperator*{#1}{#2}} % striked integral \newcommand{\avint}{\mathop{\mathchoice{\,\rlap{-}\!\!\int} {\rlap{\raise.15em{\scriptstyle -}}\kern-.2em\int} {\rlap{\raise.09em{\scriptscriptstyle -}}\!\int} {\rlap{-}\!\int}}\nolimits} % \d does not work well for PDFs \LetThereBe{\d}{\differential} \LetThereBe{\Im}{\IM} \LetThereBe{\Re}{\RE} \LetThereBe{\Cpls}{\mathrm{C{\scriptsize PL}}} \LetThereBe{\OptCpls}{\mathrm{O{\scriptsize pt}}} \letThereBe{\linefrac}{2}{#1/#2} \LetThereBe{\ExtProd}{\mathsf{\Lambda}} \letThereBe{\unicodeInt}{1}{\mathop{\vcenter{\mathchoice{\huge\unicode{#1}}{\unicode{#1}}{\unicode{#1}}{\unicode{#1}}}}\nolimits} \letThereBe{\Oiint}{1}{\underset{ #1 \;}{ {\rlap{\mspace{1mu} \boldsymbol{\bigcirc}}{\rlap{\int}{\;\int}}} }} \letThereBe{\sOiint}{1}{\unicodeInt{x222F}_{#1}} $$ $$ % Simply for testing \LetThereBe{\foo}{\textrm{FIXME: this is a test!}} % Font styles \letThereBe{\mcal}{1}{\mathcal{#1}} \letThereBe{\chem}{1}{\mathrm{#1}} % Sets \LetThereBe{\C}{\mathbb{C}} \LetThereBe{\R}{\mathbb{R}} \LetThereBe{\Z}{\mathbb{Z}} \LetThereBe{\N}{\mathbb{N}} \LetThereBe{\Q}{\mathbb{Q}} \LetThereBe{\K}{\mathbb{K}} \LetThereBe{\im}{\mathrm{i}} % Sets from PDEs \LetThereBe{\boundaryOf}{\partial} \letThereBe{\closureOf}{1}{\overline{#1}} \letThereBe{\Contf}{1}{\mcal C^{#1}} \letThereBe{\contf}{2}{\Contf{#2}(#1)} \letThereBe{\compactContf}{2}{\mcal C_c^{#2}(#1)} \letThereBe{\ball}{2}{B\brackets{#1, #2}} \letThereBe{\closedBall}{2}{B\parentheses{#1, #2}} \LetThereBe{\compactEmbed}{\subset\subset} \letThereBe{\inside}{1}{#1^o} \LetThereBe{\neighborhood}{\mcal O} \letThereBe{\neigh}{1}{\neighborhood \brackets{#1}} % Basic notation - vectors and random variables \letThereBe{\vi}{1}{\boldsymbol{#1}} %vector or matrix \letThereBe{\dvi}{1}{\vi{\dot{#1}}} %differentiated vector or matrix \letThereBe{\vii}{1}{\mathbf{#1}} %if \vi doesn't work \letThereBe{\dvii}{1}{\vii{\dot{#1}}} %if \dvi doesn't work \letThereBe{\rnd}{1}{\mathup{#1}} %random variable \letThereBe{\vr}{1}{\mathbf{#1}} %random vector or matrix \letThereBe{\vrr}{1}{\boldsymbol{#1}} %random vector if \vr doesn't work \letThereBe{\dvr}{1}{\vr{\dot{#1}}} %differentiated vector or matrix \letThereBe{\vb}{1}{\pmb{#1}} %#TODO \letThereBe{\dvb}{1}{\vb{\dot{#1}}} %#TODO \letThereBe{\oper}{1}{\mathsf{#1}} \letThereBe{\quotient}{2}{{^{\displaystyle #1}}/{_{\displaystyle #2}}} % Basic notation - general \letThereBe{\set}{1}{\left\{#1\right\}} \letThereBe{\seqnc}{4}{\set{#1_{#2}}_{#2 = #3}^{#4}} \letThereBe{\Seqnc}{3}{\set{#1}_{#2}^{#3}} \letThereBe{\brackets}{1}{\left( #1 \right)} \letThereBe{\parentheses}{1}{\left[ #1 \right]} \letThereBe{\dom}{1}{\mcal{D}\, \brackets{#1}} \letThereBe{\complexConj}{1}{\overline{#1}} \LetThereBe{\divider}{\; \vert \;} \LetThereBe{\gets}{\leftarrow} \letThereBe{\rcases}{1}{\left.\begin{aligned}#1\end{aligned}\right\}} \letThereBe{\rcasesAt}{2}{\left.\begin{alignedat}{#1}#2\end{alignedat}\right\}} \letThereBe{\lcases}{1}{\begin{cases}#1\end{cases}} \letThereBe{\lcasesAt}{2}{\left\{\begin{alignedat}{#1}#2\end{alignedat}\right.} \letThereBe{\evaluateAt}{2}{\left.#1\right|_{#2}} \LetThereBe{\Mod}{\;\mathrm{mod}\;} \LetThereBe{\bigO}{O} \letThereBe{\BigO}{1}{\bigO\brackets{#1}} % Special symbols \LetThereBe{\const}{\mathrm{const}} \LetThereBe{\konst}{\mathrm{konst.}} \LetThereBe{\vf}{\varphi} \LetThereBe{\ve}{\varepsilon} \LetThereBe{\tht}{\theta} \LetThereBe{\Tht}{\Theta} \LetThereBe{\after}{\circ} \LetThereBe{\lmbd}{\lambda} \LetThereBe{\Lmbd}{\Lambda} % Shorthands \LetThereBe{\xx}{\vi x} \LetThereBe{\yy}{\vi y} \LetThereBe{\AA}{\vi A} \LetThereBe{\bb}{\vi b} \LetThereBe{\vvf}{\vi \vf} \LetThereBe{\ff}{\vi f} \LetThereBe{\gg}{\vi g} % Basic functions \letThereBe{\absval}{1}{\left| #1 \right|} \LetThereBe{\id}{\mathrm{id}} \letThereBe{\floor}{1}{\left\lfloor #1 \right\rfloor} \letThereBe{\ceil}{1}{\left\lceil #1 \right\rceil} \declareMathematics{\image}{im} %image \declareMathematics{\domain}{dom} %image \declareMathematics{\tg}{tg} \declareMathematics{\sign}{sign} \declareMathematics{\card}{card} %cardinality \letThereBe{\setSize}{1}{\left| #1 \right|} \LetThereBe{\countElements}{\#} \declareMathematics{\exp}{exp} \letThereBe{\Exp}{1}{\exp\brackets{#1}} \LetThereBe{\ee}{\mathrm{e}} \letThereBe{\indicator}{1}{\mathbb{I}_{#1}} \declareMathematics{\arccot}{arccot} \declareMathematics{\gcd}{gcd} % Greatest Common Divisor \declareMathematics{\lcm}{lcm} % Least Common Multiple \declareMathematics{\epi}{epi} %epigraph of a function \letThereBe{\limInfty}{1}{\lim_{#1 \to \infty}} \letThereBe{\limInftyM}{1}{\lim_{#1 \to -\infty}} % Useful commands \letThereBe{\onTop}{2}{\mathrel{\overset{#2}{#1}}} \letThereBe{\onBottom}{2}{\mathrel{\underset{#2}{#1}}} \letThereBe{\tOnTop}{2}{\mathrel{\overset{\text{#2}}{#1}}} \letThereBe{\tOnBottom}{2}{\mathrel{\underset{\text{#2}}{#1}}} \LetThereBe{\EQ}{\onTop{=}{!}} \LetThereBe{\letDef}{:=} %#TODO: change the symbol \LetThereBe{\isPDef}{\onTop{\succ}{?}} \LetThereBe{\inductionStep}{\tOnTop{=}{induct. step}} \LetThereBe{\fromDef}{\triangleq} % Optimization \declareMathematicsStar{\argmin}{argmin} \declareMathematicsStar{\argmax}{argmax} \letThereBe{\maxOf}{1}{\max\set{#1}} \letThereBe{\minOf}{1}{\min\set{#1}} \declareMathematics{\prox}{prox} \declareMathematics{\loss}{loss} \declareMathematics{\supp}{supp} \letThereBe{\Supp}{1}{\supp\brackets{#1}} \LetThereBe{\constraint}{\text{s.t.}\;} $$ $$ % Operators - Analysis \LetThereBe{\hess}{\nabla^2} \LetThereBe{\lagr}{\mcal L} \LetThereBe{\lapl}{\Delta} \declareMathematics{\grad}{grad} \declareMathematics{\divergence}{div} \declareMathematics{\Dgrad}{D} \LetThereBe{\gradient}{\nabla} \LetThereBe{\jacobi}{\nabla} \LetThereBe{\Jacobi}{\vi{\mathrm J}} \letThereBe{\jacobian}{2}{\Dgrad_{#1}\brackets{#2}} \LetThereBe{\d}{\mathrm{d}} \LetThereBe{\dd}{\,\mathrm{d}} \letThereBe{\partialDeriv}{2}{\frac {\partial #1} {\partial #2}} \letThereBe{\npartialDeriv}{3}{\partialDeriv{^{#1} #2} {#3^{#1}}} \letThereBe{\partialOp}{1}{\frac {\partial} {\partial #1}} \letThereBe{\npartialOp}{2}{\frac {\partial^{#1}} {\partial #2^{#1}}} \letThereBe{\pDeriv}{2}{\partialDeriv{#1}{#2}} \letThereBe{\npDeriv}{3}{\npartialDeriv{#1}{#2}{#3}} \letThereBe{\deriv}{2}{\frac {\d #1} {\d #2}} \letThereBe{\nderiv}{3}{\frac {\d^{#1} #2} {\d #3^{#1}}} \letThereBe{\derivOp}{1}{\frac {\d} {\d #1}\,} \letThereBe{\nderivOp}{2}{\frac {\d^{#1}} {\d #2^{#1}}\,} % Convergence \LetThereBe{\pointwiseTo}{\to} \LetThereBe{\uniformlyTo}{\rightrightarrows} \LetThereBe{\normallyTo}{\tOnTop{\longrightarrow}{norm}} \LetThereBe{\compactlyTo}{\tOnTop{\longrightarrow}{comp.}} \LetThereBe{\locallyUnifTo}{\tOnTop{\longrightarrow}{l.u.}} % Curves \letThereBe{\graphOf}{1}{\parentheses{#1}} \declareMathematics{\interior}{Int} % complex \LetThereBe{\Cinfty}{\tilde{\C}} \declareMathematics{\residual}{res} \letThereBe{\resAt}{1}{\residual_{#1}} \declareMathematics{\complexarg}{arg} \declareMathematics{\complexArg}{Arg} \LetThereBe{\carg}{\complexarg} \LetThereBe{\cArg}{\complexArg} \LetThereBe{\IM}{\mathfrak{Im}} \LetThereBe{\RE}{\mathfrak{Re}} \letThereBe{\imOf}{1}{\IM\,#1} \letThereBe{\reOf}{1}{\RE\,#1} \letThereBe{\ImOf}{1}{\IM \brackets{#1}} \letThereBe{\ReOf}{1}{\RE \brackets{#1}} % Convex \letThereBe{\cconj}{1}{#1^*} $$ $$ % Linear algebra \letThereBe{\norm}{1}{\left\lVert #1 \right\rVert} \letThereBe{\seminorm}{1}{{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert #1 \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}} \letThereBe{\scal}{2}{\left\langle #1, #2 \right\rangle} \letThereBe{\avg}{1}{\overline{#1}} \letThereBe{\Avg}{1}{\bar{#1}} \letThereBe{\linspace}{1}{\mathrm{lin}\set{#1}} \letThereBe{\algMult}{1}{\mu_{\mathrm A} \brackets{#1}} \letThereBe{\geomMult}{1}{\mu_{\mathrm G} \brackets{#1}} \LetThereBe{\Nullity}{\mathrm{nullity}} \letThereBe{\nullity}{1}{\Nullity \brackets{#1}} \LetThereBe{\nulty}{\nu} \declareMathematics{\SpanOf}{span} \letThereBe{\Span}{1}{\SpanOf\set{#1}} \LetThereBe{\projection}{\Pi} % Linear algebra - Matrices \LetThereBe{\tr}{\top} \LetThereBe{\Tr}{^\tr} \LetThereBe{\pinv}{\dagger} \LetThereBe{\Pinv}{^\dagger} \LetThereBe{\Inv}{^{-1}} \LetThereBe{\ident}{\vi{I}} \letThereBe{\mtr}{1}{\begin{pmatrix}#1\end{pmatrix}} \letThereBe{\bmtr}{1}{\begin{bmatrix}#1\end{bmatrix}} \declareMathematics{\trace}{tr} \declareMathematics{\diagonal}{diag} \declareMathematics{\rank}{rank} % Multilinear algebra \LetThereBe{\tensorProd}{\otimes} \LetThereBe{\tprod}{\tensorProd} \LetThereBe{\extProd}{\wedge} \LetThereBe{\wdg}{\extProd} \LetThereBe{\wedges}{\wedge \dots \wedge} \declareMathematics{\altMap}{Alt} $$ $$ % Statistics \LetThereBe{\iid}{\overset{\text{i.i.d.}}{\sim}} \LetThereBe{\ind}{\overset{\text{ind}}{\sim}} \LetThereBe{\condp}{\,\vert\,} \letThereBe{\complementOf}{1}{{#1^{\mathrm{c}}}} \LetThereBe{\acov}{\gamma} \LetThereBe{\acf}{\rho} \LetThereBe{\stdev}{\sigma} \LetThereBe{\procMean}{\mu} \LetThereBe{\procVar}{\stdev^2} \declareMathematics{\variance}{var} \letThereBe{\Variance}{1}{\variance \brackets{#1}} \declareMathematics{\cov}{cov} \declareMathematics{\corr}{cor} \letThereBe{\sampleVar}{1}{\rnd S^2_{#1}} \letThereBe{\populationVar}{1}{V_{#1}} \declareMathematics{\expectedValue}{\mathbb{E}} \declareMathematics{\rndMode}{Mode} \letThereBe{\RndMode}{1}{\rndMode\brackets{#1}} \letThereBe{\expect}{1}{\expectedValue #1} \letThereBe{\Expect}{1}{\expectedValue \brackets{#1}} \letThereBe{\expectIn}{2}{\expectedValue_{#1} #2} \letThereBe{\ExpectIn}{2}{\expectedValue_{#1} \brackets{#2}} \LetThereBe{\betaF}{\mathrm B} \LetThereBe{\fisherMat}{J} \LetThereBe{\mutInfo}{I} \LetThereBe{\expectedGain}{I_e} \letThereBe{\KLDiv}{2}{D\brackets{#1 \parallel #2}} \LetThereBe{\entropy}{H} \LetThereBe{\diffEntropy}{h} \LetThereBe{\probF}{\pi} \LetThereBe{\densF}{\vf} \LetThereBe{\att}{_t} %at time \letThereBe{\estim}{1}{\hat{#1}} \letThereBe{\estimML}{1}{\hat{#1}_{\mathrm{ML}}} \letThereBe{\estimOLS}{1}{\hat{#1}_{\mathrm{OLS}}} \letThereBe{\estimMAP}{1}{\hat{#1}_{\mathrm{MAP}}} \letThereBe{\predict}{3}{\estim {\rnd #1}_{#2 | #3}} \letThereBe{\periodPart}{3}{#1+#2-\ceil{#2/#3}#3} \letThereBe{\infEstim}{1}{\tilde{#1}} \letThereBe{\predictDist}{1}{{#1}^*} \LetThereBe{\backs}{\oper B} \LetThereBe{\diff}{\oper \Delta} \LetThereBe{\BLP}{\oper P} \LetThereBe{\arPoly}{\Phi} \letThereBe{\ArPoly}{1}{\arPoly\brackets{#1}} \LetThereBe{\maPoly}{\Theta} \letThereBe{\MaPoly}{1}{\maPoly\brackets{#1}} \letThereBe{\ARmod}{1}{\mathrm{AR}\brackets{#1}} \letThereBe{\MAmod}{1}{\mathrm{MA}\brackets{#1}} \letThereBe{\ARMA}{2}{\mathrm{ARMA}\brackets{#1, #2}} \letThereBe{\sARMA}{3}{\mathrm{ARMA}\brackets{#1}\brackets{#2}_{#3}} \letThereBe{\SARIMA}{3}{\mathrm{ARIMA}\brackets{#1}\brackets{#2}_{#3}} \letThereBe{\ARIMA}{3}{\mathrm{ARIMA}\brackets{#1, #2, #3}} \LetThereBe{\pacf}{\alpha} \letThereBe{\parcorr}{3}{\rho_{#1 #2 | #3}} \LetThereBe{\noise}{\mathscr{N}} \LetThereBe{\jeffreys}{\mathcal J} \LetThereBe{\likely}{\mcal L} \letThereBe{\Likely}{1}{\likely\brackets{#1}} \LetThereBe{\loglikely}{\mcal l} \letThereBe{\Loglikely}{1}{\loglikely \brackets{#1}} \LetThereBe{\CovMat}{\Gamma} \LetThereBe{\covMat}{\vi \CovMat} \LetThereBe{\rcovMat}{\vrr \CovMat} \LetThereBe{\AIC}{\mathrm{AIC}} \LetThereBe{\BIC}{\mathrm{BIC}} \LetThereBe{\AICc}{\mathrm{AIC}_c} \LetThereBe{\nullHypo}{H_0} \LetThereBe{\altHypo}{H_1} \LetThereBe{\rve}{\rnd \ve} \LetThereBe{\rtht}{\rnd \theta} \LetThereBe{\rX}{\rnd X} \LetThereBe{\rY}{\rnd Y} \LetThereBe{\rZ}{\rnd Z} \LetThereBe{\rA}{\rnd A} \LetThereBe{\rB}{\rnd B} \LetThereBe{\rU}{\rnd U} \LetThereBe{\vrZ}{\vr Z} \LetThereBe{\vrY}{\vr Y} \LetThereBe{\vrX}{\vr X} \LetThereBe{\vrU}{\vr U} \LetThereBe{\rW}{\rnd W} \LetThereBe{\rS}{\rnd S} \LetThereBe{\rM}{\rnd M} \LetThereBe{\rtau}{\rnd \tau} % Bayesian inference \LetThereBe{\paramSet}{\mcal T} \LetThereBe{\sampleSet}{\mcal Y} \LetThereBe{\bayesSigmaAlg}{\mcal B} % Different types of convergence \LetThereBe{\inDist}{\onTop{\to}{d}} \letThereBe{\inDistWhen}{1}{\onBottom{\onTop{\longrightarrow}{d}}{#1}} \LetThereBe{\inProb}{\onTop{\to}{P}} \letThereBe{\inProbWhen}{1}{\onBottom{\onTop{\longrightarrow}{P}}{#1}} \LetThereBe{\inMeanSq}{\onTop{\to}{\ltwo}} \LetThereBe{\inltwo}{\onTop{\to}{\ltwo}} \letThereBe{\inMeanSqWhen}{1}{\onBottom{\onTop{\longrightarrow}{\ltwo}}{#1}} \LetThereBe{\convergeAS}{\tOnTop{\to}{a.s.}} \letThereBe{\convergeASWhen}{1}{\onBottom{\tOnTop{\longrightarrow}{a.s.}}{#1}} % Asymptotic qualities \LetThereBe{\simAsymp}{\tOnTop{\sim}{as.}} % Stochastic analysis \letThereBe{\diffOn}{2}{\diff #1_{[#2]}} % \LetThereBe{\timeSet}{\Theta} \LetThereBe{\eventSet}{\Omega} \LetThereBe{\filtration}{\mcal F} % TODO: Rename allFiltrations and the like \letThereBe{\allFiltrations}{1}{\set{\filtration_t}_{#1}} \letThereBe{\natFilter}{1}{\filtration_t^{#1}} \letThereBe{\NatFilter}{2}{\filtration_{#2}^{#1}} \letThereBe{\filterAll}{1}{\set{#1}_{t \geq 0}} \letThereBe{\FilterAll}{2}{\set{#1}_{#2}} \LetThereBe{\borelAlgebra}{\mcal B} \LetThereBe{\sAlgebra}{\mcal A} \LetThereBe{\quadVar}{Q} \LetThereBe{\totalVar}{V} \LetThereBe{\adaptIntProcs}{\mcal M} \letThereBe{\reflectProc}{2}{#1^{#2}} $$ $$ % Distributions \letThereBe{\WN}{2}{\mathrm{WN}\brackets{#1,#2}} \declareMathematics{\uniform}{Unif} \declareMathematics{\binomDist}{Bi} \declareMathematics{\negbinomDist}{NBi} \declareMathematics{\betaDist}{Beta} \declareMathematics{\betabinomDist}{BetaBin} \declareMathematics{\gammaDist}{Gamma} \declareMathematics{\igammaDist}{IGamma} \declareMathematics{\invgammaDist}{IGamma} \declareMathematics{\expDist}{Ex} \declareMathematics{\poisDist}{Po} \declareMathematics{\erlangDist}{Er} \declareMathematics{\altDist}{A} \declareMathematics{\geomDist}{Ge} \LetThereBe{\normalDist}{\mathcal N} %\declareMathematics{\normalDist}{N} \letThereBe{\normalD}{1}{\normalDist \brackets{#1}} \letThereBe{\mvnormalD}{2}{\normalDist_{#1} \brackets{#2}} \letThereBe{\NormalD}{2}{\normalDist \brackets{#1, #2}} \LetThereBe{\lognormalDist}{\log\normalDist} $$ $$ % Game Theory \LetThereBe{\doms}{\succ} \LetThereBe{\isdom}{\prec} \letThereBe{\OfOthers}{1}{_{-#1}} \LetThereBe{\ofOthers}{\OfOthers{i}} \LetThereBe{\pdist}{\sigma} \letThereBe{\domGame}{1}{G_{DS}^{#1}} \letThereBe{\ratGame}{1}{G_{Rat}^{#1}} \letThereBe{\bestRep}{2}{\mathrm{BR}_{#1}\brackets{#2}} \letThereBe{\perf}{1}{{#1}_{\mathrm{perf}}} \LetThereBe{\perfG}{\perf{G}} \letThereBe{\imperf}{1}{{#1}_{\mathrm{imp}}} \LetThereBe{\imperfG}{\imperf{G}} \letThereBe{\proper}{1}{{#1}_{\mathrm{proper}}} \letThereBe{\finrep}{2}{{#2}_{#1{\text -}\mathrm{rep}}} %T-stage game \letThereBe{\infrep}{1}{#1_{\mathrm{irep}}} \LetThereBe{\repstr}{\tau} %strategy in a repeated game \LetThereBe{\emptyhist}{\epsilon} \letThereBe{\extrep}{1}{{#1^{\mathrm{rep}}}} \letThereBe{\avgpay}{1}{#1^{\mathrm{avg}}} \LetThereBe{\succf}{\pi} %successor function \LetThereBe{\playf}{\rho} %player function \LetThereBe{\actf}{\chi} %action function $$ $$ \LetThereBe{\fourierOp}{\mcal{F}} \letThereBe{\fourier}{1}{\widehat{#1}} \letThereBe{\ifourier}{1}{\check{#1}} % Shortcuts \letThereBe{\FT}{1}{\fourier{#1}} \letThereBe{\iFT}{1}{\ifourier{#1}} \LetThereBe{\FTOp}{\fourierOp} \LetThereBe{\XX}{\mcal X} \LetThereBe{\YY}{\mcal Y} \LetThereBe{\cc}{\mathsf{c}} \LetThereBe{\lspace}{\mcal L} \LetThereBe{\lone}{\lspace^{1}} \letThereBe{\Lone}{1}{\lone\brackets{#1}} \LetThereBe{\ltwo}{\lspace^2} \letThereBe{\Ltwo}{1}{\ltwo\brackets{#1}} \letThereBe{\lp}{1}{\lspace^{#1}} \letThereBe{\Lp}{2}{\lp{#1}\brackets{#2}} \LetThereBe{\linfty}{\lspace^{\infty}} \letThereBe{\Linfty}{1}{\linfty\brackets{#1}} \LetThereBe{\ltwoEq}{\onTop{=}{\ltwo}} \letThereBe{\decayContf}{1}{\mcal C_0\brackets{#1}} \letThereBe{\cinftyContf}{1}{\mcal C^{\infty}_c\brackets{#1}} \LetThereBe{\bddMeasFs}{\mcal M_{\mathrm{b}}} \LetThereBe{\contBddFs}{\mcal C_{\mathrm{b}}} \LetThereBe{\contFs}{\mcal C} \LetThereBe{\Borel}{\mathscr{B}} \LetThereBe{\FinSignMeas}{\mathscr{M}} \LetThereBe{\Probs}{\mathscr{P}} \letThereBe{\probs}{1}{\Probs\brackets{#1}} \LetThereBe{\SCMProbs}{\Probs_2} \letThereBe{\scmProbs}{1}{\SCMProbs\brackets{#1}} \LetThereBe{\ACProbs}{\SCMProbs^{\mathrm{ac}}} \letThereBe{\acProbs}{1}{\ACProbs\brackets{#1}} \letThereBe{\pushforward}{2}{#1_{\sharp}#2} \letThereBe{\pf}{2}{\pushforward{#1}{#2}} \declareMathematics{\Law}{Law} \declareMathematics{\Project}{pr} \letThereBe{\project}{1}{\Project^{#1}} \letThereBe{\pr}{1}{\project{#1}} \declareMathematics{\TV}{TV} \letThereBe{\cpls}{1}{\Cpls\brackets{#1}} \letThereBe{\optCpls}{1}{\OptCpls\brackets{#1}} \LetThereBe{\OT}{\mathrm{OT}} \LetThereBe{\wasserstein}{\mcal W_2} \LetThereBe{\wsGrad}{\gradient_{\mcal W}} \LetThereBe{\csubseteq}{\onTop{\subseteq}{\mathrm{c}}} \LetThereBe{\bddsubseteq}{\onTop{\subseteq}{\mathrm{bdd}}} \letThereBe{\cTr}{1}{#1^{\cc}} \letThereBe{\cbTr}{1}{#1^{\overline{\cc}}} $$ $$ % ODEs \LetThereBe{\timeInt}{\mcal I} \LetThereBe{\stimeInt}{\mcal J} \LetThereBe{\Wronsk}{\mcal W} \letThereBe{\wronsk}{1}{\Wronsk \parentheses{#1}} \LetThereBe{\prufRadius}{\rho} \LetThereBe{\prufAngle}{\vf} \LetThereBe{\weyr}{\sigma} \LetThereBe{\linDifOp}{\mathsf{L}} \LetThereBe{\Hurwitz}{\vi H} \letThereBe{\hurwitz}{1}{\Hurwitz \brackets{#1}} % Cont. Models \LetThereBe{\dirac}{\delta} \LetThereBe{\torus}{\mathbb{T}} % PDEs % \avint -- defined in format-respective tex files \LetThereBe{\fundamental}{\Phi} \LetThereBe{\fund}{\fundamental} \letThereBe{\normaDeriv}{1}{\partialDeriv{#1}{\vec{n}}} \letThereBe{\volAvg}{2}{\avint_{\ball{#1}{#2}}} \LetThereBe{\VolAvg}{\volAvg{x}{\ve}} \letThereBe{\surfAvg}{2}{\avint_{\boundaryOf \ball{#1}{#2}}} \LetThereBe{\SurfAvg}{\surfAvg{x}{\ve}} \LetThereBe{\corrF}{\varphi^{\times}} \LetThereBe{\greenF}{G} \letThereBe{\reflect}{1}{\tilde{#1}} \LetThereBe{\conv}{*} \letThereBe{\dotP}{2}{#1 \cdot #2} \letThereBe{\translation}{1}{\tau_{#1}} \declareMathematics{\dist}{dist} \letThereBe{\regularizef}{1}{\eta_{#1}} \letThereBe{\fourier}{1}{\widehat{#1}} \letThereBe{\ifourier}{1}{\check{#1}} \LetThereBe{\fourierOp}{\mcal F} \LetThereBe{\ifourierOp}{\mcal F^{-1}} \letThereBe{\FourierOp}{1}{\fourierOp\set{#1}} \letThereBe{\iFourierOp}{1}{\ifourierOp\set{#1}} \LetThereBe{\laplaceOp}{\mcal L} \letThereBe{\LaplaceOp}{1}{\laplaceOp\set{#1}} \letThereBe{\Norm}{1}{\absval{#1}} % SINDy \LetThereBe{\Koop}{\mcal K} \letThereBe{\oneToN}{1}{\left[#1\right]} \LetThereBe{\meas}{\mathrm{m}} \LetThereBe{\stateLoss}{\mcal J} \LetThereBe{\lagrm}{p} % Stochastic analysis \LetThereBe{\RiemannInt}{(\mcal R)} \LetThereBe{\RiemannStieltjesInt}{(\mcal {R_S})} \LetThereBe{\LebesgueInt}{(\mcal L)} \LetThereBe{\ItoInt}{(\mcal I)} \LetThereBe{\Stratonovich}{\circ} \LetThereBe{\infMean}{\alpha} \LetThereBe{\infVar}{\beta} % Dynamical systems \LetThereBe{\nUnit}{\mathrm N} \LetThereBe{\timeUnit}{\mathrm T} % Masters thesis \LetThereBe{\evolOp}{\oper{\vf}} \letThereBe{\obj}{1}{\mathbb{#1}} \LetThereBe{\timeSet}{\obj T} \LetThereBe{\stateSpace}{\obj X} \LetThereBe{\contStateSpace}{\stateSpace_{C}} \LetThereBe{\orbit}{Or} \letThereBe{\Orbit}{1}{\orbit\brackets{#1}} \LetThereBe{\limitSet}{\obj \Lambda} \LetThereBe{\crossSection}{\obj \Sigma} \declareMathematics{\codim}{codim} % Left and right closed-or-open intervals \LetThereBe{\lco}{\langle} \LetThereBe{\rco}{\rangle} \letThereBe{\testInt}{1}{\mathrm{Int}_{#1}} \letThereBe{\evalOp}{1}{\oper{\eta}_{#1}} \LetThereBe{\nonzeroEl}{\bullet} \LetThereBe{\zeroEl}{\circ} \LetThereBe{\solOp}{\oper{S}} \LetThereBe{\infGen}{\oper{A}} \LetThereBe{\indexSet}{\mcal I} \letThereBe{\indicesOf}{1}{\indexSet\parentheses{#1}} \letThereBe{\IndicesOf}{2}{\indexSet_{#2}\parentheses{#1}} \LetThereBe{\meshGrid}{\obj M} \declareMathematics{\starter}{starter} \declareMathematics{\indexer}{indx} \declareMathematics{\enumerator}{enum} \LetThereBe{\inSS}{_{\infty}} \LetThereBe{\manifold}{\mcal M} \LetThereBe{\curve}{\mcal C} % Numerical methods \declareMathematics{\globErr}{err} \declareMathematics{\locErr}{le} \declareMathematics{\locTrErr}{lte} \declareMathematics{\estimErr}{est} \declareMathematics{\incrementFunc}{Inc} \letThereBe{\incrementF}{1}{\incrementFunc \brackets{#1}} \LetThereBe{\discreteNodes}{\mcal T} \LetThereBe{\stableFunc}{R} \letThereBe{\stableF}{1}{\stableFunc\brackets{#1}} \LetThereBe{\stableRegion}{\Omega} %Stochastic analysis \LetThereBe{\RiemannInt}{(\mcal R)} \LetThereBe{\RiemannStieltjesInt}{(\mcal {R_S})} \LetThereBe{\LebesgueInt}{(\mcal L)} \LetThereBe{\ItoInt}{(\mcal I)} \LetThereBe{\Stratonovich}{\circ} \LetThereBe{\infMean}{\alpha} \LetThereBe{\infVar}{\beta} %Optimization \LetThereBe{\goldRatio}{\tau} %Interpolation \LetThereBe{\lagrPoly}{l} $$

Let us fix the following notation and convention: Let \((\mcal X, d_{\mcal X})\) and \((\mcal Y, d_{\mcal Y})\) be Polish 3.1 metric spaces, and

Typically, \(\R^{\infty} := \R \cup \set{+\infty}\), \(\mu \in \probs{\mcal X}, \nu \in \probs{\mcal Y}\) and \(\cc \colon \mcal X \times \mcal Y \to \R^{\infty}\) is a measurable cost function.

2.1 Monge Formulation

Definition 2.1 (Pushforward) Given a Borel map \(T \colon \XX \to \YY\) the pushforward measure \(\pf{T}{\mu} \in \probs{\YY}\) of \(\mu \in \probs{\XX}\) through \(T\) is given by \[ \forall A \in \Borel(\YY): \quad \pf{T}{\mu}(A) = \mu(T^{-1}(A)) \] or, equivalently, in the language of random variables \(\rnd{X} \sim \mu \implies T(\rnd{X}) \sim \pf{T}{\mu}\).

Definition 2.2 (Transport map) A measurable map \(T \colon \XX \to \YY\) is called a transport map from \(\mu\) to \(\nu\) if \(\pf{T}{\mu} = \nu\), equivalently \(\rnd{X} \sim \mu \implies T(\rnd{X}) \sim \nu\).

Example 2.1 Assume \(\mu \in \probs{\R}\) continuous and \(\nu \in \probs{\R}\). Now \(T = F_{\nu}^{-1} \circ F_{\mu}\), where \(F_{\mu}\) is the cumulative distribution function \(\mu((-\infty, x])\) and \(F_{\nu}^{-1}\) is the quantile function of \(\nu\), i.e., \(F^{-1}_{\nu}(u) = \inf \set{x \in \R \mid F_{\nu}(x) > u}\), is the monotone transport map from \(\mu\) to \(\nu\).

Indeed, for \(\mu\) continuous and \(\rnd X \sim \mu\) one has \(F_{\mu}(\rnd X) \sim \uniform(0,1)\). Further, \(\rnd U \sim \uniform(0, 1)\) implies \(F_{\nu}^{-1}(\rnd U) \sim \nu\). Hence, \[ \rnd X \sim \mu \implies F_{\mu}(\rnd X) \sim \uniform(0,1) \implies \brackets{F^{-1}_{\nu} \circ F_{\mu}}(\rnd X) = T(\rnd X) \sim \nu. \]

Then the first (and naive) way of defining optimal transport problem is again the Monge formulation \[ V^{\mathrm{Monge}}_{\cc}(\mu, \nu) := \inf_{\pf{T}{\mu} = \nu} \int_{\XX} \cc(x, T(x)) \dd \mu(x). \tag{2.1}\]

However, the set \(\set{T \mid \pf{T}{\mu} = \nu}\) might be empty, non-convex or non-compact.

2.2 Kantorovich Formulation

Let us now fix the further notation for projections: \[\begin{align*} \pr{\XX} &\colon \XX \times \YY \to \XX & &\& & \pr{\YY} &\colon \XX \times \YY \to \YY. \\ &(x,y) \mapsto x &&& &(x,y) \mapsto y \end{align*}\]

Definition 2.3 (Coupling) A probability measure \(\pi \in \probs{\XX \times \YY}\) is called a coupling on \(\mu\) and \(\nu\) if \(\pf{\pr{\XX}}{\pi} = \mu\) and \(\pf{\pr{\YY}}{\pi} = \nu\). Equivalently, \[ (\rnd X, \rnd Y) \sim \pi \implies \lcases{ \rnd X \sim \mu, \\ \rnd Y \sim \nu. } \]

A set of all couplings of \(\mu\) and \(\nu\) is denoted by \(\cpls{\mu, \nu}\).

Example 2.2  

  1. Let \(T\) be a transport map from \(\mu\) to \(\nu\), then \[ \underbrace{\pf{\brackets{\id, T}}{\mu}}_{\Law(\rnd X, T(\rnd X)) \text{ if } \rnd X \sim \mu} = \pi \in \cpls{\mu, \nu}; \]
  2. Take \(\rnd U \sim \uniform(0, 1) = \lmbd\), then \[ \pf{\brackets{F^{-1}_{\mu}, F^{-1}_{\nu}}}{\lmbd} = \Law\brackets{F^{-1}_{\mu}(\rnd U), F^{-1}_{\nu}(\rnd U)} \in \cpls{\mu, \nu} \] is called a monotone coupling;
  3. Lastly, consider independent random variables \(\rX \sim \mu\) and \(\rY \sim \nu\), then the product measure \(\mu \otimes \nu = \Law(\rX, \rY) \in \cpls{\mu, \nu}\) is the independent (product) coupling.

This finally leads to the Kantorovich formulation of the optimal transport problem, \[ V^{\OT}_{\cc}(\mu, \nu) = \inf_{\pi \in \cpls{\mu, \nu}} \int \cc(x, y) \dd \pi(x, y). \tag{2.2}\]

Naturally, let our goal now be to study the attainment and properties of \(V^{\OT}_{\cc}\). In principle, we would like to have a lower semi-continuous functional to be optimizer over a compact set. More precisely, we want

  1. \(\cpls{\mu, \nu}\) to be non-empty (trivially satisfied), convex1 and compact (to be shown), and
  2. \(\pi \mapsto \int \cc \dd \pi =: \pi(\cc)\) to be lower semi-continuous.

Indeed, the above 2 properties yield attainment of \(V^{\OT}_{\cc}\), as we could pick a minimizing sequence \((\pi^k)_{k \in \N} \in \cpls{\mu, \nu}\) and by compactness extract a converging subsequence with the limit \(\pi\). Lastly, by lower semi-continuity we get \[ V^{\OT}_{\cc}(\mu, \nu) = \lim_k \pi^k(\cc) \geq \pi(\cc) \geq V^{\OT}_{\cc}(\mu, \nu) \] for \((\pi^k)_{k \in \N}\) the minimizing sequence. As such, we need a topology on \(\probs{\XX}\) (to study compactness).

Definition 2.4 The weak topology of measures on \(\FinSignMeas(\XX)\) is the initial topology2 with respect to \(\FinSignMeas(\XX) \ni \mu \mapsto \mu(f)\) for \(f \in \contBddFs(\XX)\).

We will endow \(\probs{\XX} \subseteq \FinSignMeas(\XX)\) with this topology.

Remark 2.1. Let us state some (easy to show) facts concerning the weak topology on \(\probs{\XX}\):

  1. \(x \mapsto \dirac_{x}\) is the topological embedding3 \(\XX \hookrightarrow \probs{\XX}\);
  2. this topology is Hausdorff4, i.e., for \(\mu, \nu \in \FinSignMeas(\XX)\) with \(\mu(f) = \nu(f)\) \(\forall f \in \contBddFs(\XX)\) implies by monotone class argument \(\mu(f) = \nu(f)\) \(\forall f \in \bddMeasFs(\XX)\), which in turn means \(\mu = \nu\);
  3. it is countably generated, i.e., there exists a countable family \((f_n)_{n \in \N} \subseteq \contBddFs(\XX)\) such that the family \(\mu \mapsto \mu(f_n)\) generates the weak topology (which also means that for testing convergence a countable set suffices) — in particular, the weak topology is second countable;
  4. it is completely metrizable, e.g., by Prokhorov metric \[ d_{\mathrm{Prokhorov}}(\mu, \nu) := \inf \set{ \ve > 0 \mid \forall A \in \Borel(\XX): \rcases{\lcases{ \mu(A) \leq \nu(A_{\ve}) + \ve, \\ \nu(A) \leq \mu(A_{\ve}) + \ve }} \; \text{ where } A_{\ve} := \bigcup_{x \in A} \ball{x}{\ve} }; \tag{2.3}\]
  5. lastly, it is a separable space, i.e., let \((x_k)_{k \in \N} \subseteq \XX\) be dense (such sequence exists since \(\XX\) is Polish), then \[ \set{ \sum_{k = 1}^n \alpha_k \dirac_{x_k} \mid n \in \N \; \& \; \alpha_k \in \Q \cap [0,1] \; \& \; \sum_{k = 1}^n \alpha_k = 1 } \] is countable and even dense in \(\probs{\XX}\).

Proposition 2.1 Let \(\XX\) be a Polish space. Then the space \(\probs{\XX}\) of probability measures over \(\XX\) is also Polish.

Proof. Above we show that \(\probs{\XX}\) is completely metrizable separable topological space, i.e., by Definition 3.1 it is Polish.

Corollary 2.1 For \(\XX\) and \(\YY\) Polish spaces, both \(\XX \times \YY\) and the space \(\probs{\XX \times \YY}\) of probability measures over their product are also Polish.

Proof. Easy but omitted.

Remark 2.2. Let \(\XX\) be a compact metric space, then \(\probs{\XX}\) is compact.

Proof. By the Riesz-Markov 3.9 representation one has \(\brackets{\contFs(\XX), \norm{\cdot}_{\infty}}' \cong \brackets{\FinSignMeas(\XX), \TV}\), where \(\TV(\mu) = \sup_{\substack{f \in \contFs(\XX)\\ \norm{f}_{\infty} \leq 1}} \mu(f)\).

Further, denote \(\FinSignMeas_{\leq 1}(\XX) := \set{\mu \mid \TV(\mu) \leq 1}\) a closed unit ball in the dual of \(\contFs(\XX)\). By Banach-Alaoglu 3.10 \(\FinSignMeas_{\leq 1}(\XX)\) is compact in the weak* topology (i.e., in the weak convergence 3.5 of measures). Now, taking \(\oper 1\) to be the constant-\(1\) function on the compact space \(\XX\), \[ \FinSignMeas_{\leq 1}(\XX) \supseteq \probs{\XX} = \bigcap_{\substack{f \in \contFs(\XX) \\ f \geq 0}} \set{ \mu \mid \mu(f) \geq 0 } \cap \set{ \mu \mid \mu(\oper 1) = 1 }, \] where the first set can be replaced, by monotone class argument, by the set of all non-negative measures. Now both are closed sets with respect to the weak* topology. Hence \(\probs{\XX}\) is weak* closed subset of a weak* compact set, thus itself is weak* compact in \((\FinSignMeas(\XX), \contFs(\XX))\). As \(\XX\) is compact, \(\contFs(\XX)\) coincides with \(\contBddFs(\XX)\) which gives us compactness in the sense of Definition 2.4.

Definition 2.5 (Tightness) A family \(\mcal E \subseteq \probs{\XX}\) is called tight, if for all \(\ve > 0\) there exists \(K \csubseteq \XX\) such that \[ \sup_{\mu \in \mcal E} \mu(\complementOf{K}) \leq \ve \quad \text{or, equivalently,} \quad \inf_{\mu \in \mcal E} \mu(K) \geq 1 - \ve. \]

Theorem 2.1 (Prokhorov’s) A family \(\mcal E \subseteq \probs{\XX}\) is tight if and only if \(\mcal E\) is relatively compact5.

Proof (A sketch of proof). “\(\implies\)”: The more difficult direction, but loosely speaking one uses tightness to restrict themselves to large compacts, then employ Remark 2.2 and use a diagonalization argument. For more information refer to [1].

“\(\impliedby\)”: Choose \(\ve > 0\) arbitrary. Our aim is now to construct a compact \(K \csubseteq \XX\) such that \(\inf_{\mu \in \mcal E} \mu(K) \geq 1 - \ve\). As \(\XX\) is separable (by being Polish), there exists a countable family \((x_k)_{k \in \N} \subseteq \XX\) that is dense in \(\XX\). Fix \(n \in \N\), then by relative compactness of \(\mcal E\), the closure \[ \closureOf{\mcal E} \subseteq \bigcup_{N \in \N} \underbrace{\set{\mu \mid \mu\brackets{\bigcup_{i = 1}^N \ball{x_i}{\frac 1 n}} > 1 - \frac {\ve} {2^n}}}_{\text{open}} \] is compact, and using this with continuity of measures gives existence of \(N_n \in \N\) such that \(\inf_{\mu \in \mcal E} \mu\brackets{K_n} \geq 1 - \frac{\ve}{2^n}\), where \(K_n := \bigcup_{i = 1}^{N_n} \ball{x_i}{\frac 1 n}\) (not necessarily compact at the moment). Define \(K := \bigcap_{n\in \N} \closureOf{K_n}\), which is closed and totally bounded (i.e., we can cover it with finitely many balls of any given radius). Completeness of \(\XX\) further yields \(K\) is compact, hence \(\inf_{\mu \in \mcal E} \mu(K) = 1 - \sup_{\mu \in \mcal E} \mu(\complementOf{K})\) where \(\complementOf{K} = \bigcup_{n \in \N} \complementOf{\closureOf{K_n}} \subseteq \bigcup_{n \in \N} \complementOf{K_n}\). Lastly, by subadditivity of measures \[ \inf_{\mu \in \mcal E} \mu(K) \geq 1 - \sup_{\mu \in \mcal E} \sum_{n \in \N} \underbrace{\mu(\complementOf{K_n})}_{\leq \frac {\ve} {2^n}} \geq 1 - \ve. \]

Interestingly, we can make the following observations:

  • The direction tightness \(\implies\) relative compactness holds even if \(\XX\) is just a metric space.
  • On the other hand, “\(\impliedby\)” requires both separability and completeness, i.e., \(\XX\) to be Polish.

Corollary 2.2 The set of all couplings \(\cpls{\mu, \nu}\) is compact.

Proof. First, we prove that \(\cpls{\mu, \nu}\) is a closed set. For this recall that \(\pr{\XX}\) is a continuous function. Then its pushforward \(\pf{\pr{\XX}}{} \colon \probs{\XX \times \YY} \to \probs{\XX}\) defined as \(\pi \mapsto \pf{\pr{\XX}}{\pi}\) is also continuous since for any \(f \in \contBddFs(\XX)\) we have \[ \int f \dd \pf{\pr{\XX}}{\pi} = \int \underbrace{\brackets{f \circ \pr{\XX}}}_{\in \contBddFs(\XX \times \YY)}(x,y) \dd \pi(x,y). \] Now, we can write \[ \cpls{\mu, \nu} = \set{\pi \in \probs{\XX \times \YY} \mid \pf{\pr{\XX}}{\pi} = \mu} \cap \set{\pi \in \probs{\XX \times \YY} \mid \pf{\pr{\YY}}{\pi} = \nu}, \] where both of the “partial” sets are closed by continuity of \(\pr{\XX}\) and \(\pr{\YY}\), respectively. Thus, set \(\cpls{\mu, \nu}\) is also closed.

Figure 2.1: Role of \(K^{\XX}\) and \(K^{\YY}\)

Second, we show that \(\cpls{\mu, \nu}\) is a tight set. Again, choose \(\ve > 0\) arbitrarily. By Theorem 2.1 on (trivially compact) \(\mcal E = \set{\mu}\) and \(\set{\nu}\), respectively, there exist compact subsets \(K_{\XX} \csubseteq \XX\) and \(K_{\YY} \csubseteq \YY\), see Figure 2.1, such that \[ \mu(K_{\XX}) \geq 1 - \frac{\ve} 2 \quad \& \quad \nu(K_{\YY}) \geq 1 - \frac {\ve} 2 \] and that \(K := K_{\XX} \times K_{\YY} \csubseteq \XX \times \YY\). Then for \(\pi \in \cpls{\mu, \nu}\), \[\begin{align*} \pi(\complementOf{K}) &= \pi\brackets{\complementOf{K_{\XX}} \times \YY \cup \XX \times \complementOf{K_{\YY}}} \\ &\tOnTop{\leq}{subadditivity} \pi \underbrace{\brackets{\complementOf{K_{\XX}} \times \YY}}_{\Project_{\XX}^{-1}(\complementOf{K_{\XX}})} + \pi\brackets{\XX \times \complementOf{K_{\YY}}} = \underbrace{\mu(\complementOf{K_{\XX}})}_{\leq \frac {\ve} 2} + \underbrace{\nu(\complementOf{K_{\YY}})}_{\leq \frac {\ve} 2} \leq \ve. \end{align*}\] Hence \(\cpls{\mu, \nu}\) is tight.

Finally, by Prokhorov’s theorem 2.1 we get relative compactness of \(\cpls{\mu, \nu}\), which yields compactness (under the weak* topology) by \(\cpls{\mu, \nu}\) being closed.

Remark 2.3. If \(\cc \in \contBddFs(\XX \times \YY)\), then by the Definition 2.4 of weak topology/convergence (see also Definition 3.5), the map \(\probs{\XX \times \YY} \to \R\) defined as \(\pi \mapsto \pi(\cc)\) is continuous.

As a reminder, let us recall the definition of lower semi-continuity.

Definition 2.6 (Lower semi-continuity) A function \(f\colon \XX \to \R^{\infty}\) is called lower semi-continuous at a point \(x_0 \in \XX\) if \(\liminf_{x \to x_0} f(x) \geq f(x_0)\).

Equivalently, \(f\) is lower semi-continuous at \(x_0\) if for every \(\alpha < f(x_0)\) there exists neighborhood \(\neigh{x_0}\) of \(x_0\) such that \(f(x) > \alpha\) for all \(x \in \neigh{x_0}\).

Lemma 2.1 Let \(f\colon \XX \to \R^{\infty}\) be lower bounded, i.e., \(\exists C \in \R\) so that \(f \geq C\), then \(f\) is lower semi-continuous if and only if there exists a family \((f_k)_{k \in \N} \subset \contBddFs(\XX)\) such that \(f_k \uparrow f\).

Moreover, \((f_k)\) can be chosen \(k\)-Lipschitz.

Proof. “\(\impliedby\)”: Take a sequence \(x_n \to x\). Then \[ f(x) = \sup_{k \in \N} f_k(x) = \sup_{k \in \N} \lim_{n \to \infty} f_k(x_n) \leq \liminf_{n \to \infty} \sup_{k \in \N} f_k(x_n) = \liminf_{n \to \infty} f(x_n). \]

“\(\implies\)”: Let us define \(f_k(x) = \inf_{y \in \XX} f(y) + k d_{\XX}(x,y)\), then \(C \leq f_k \leq f_{k+1} \leq f\). Moreover, \(f_k\) are \(k\)-Lipschitz (thus continuous) as for any \(\tilde{y} \in \XX\) \[\begin{align*} f_k(x) &\leq f(\tilde{y}) + k d_{\XX}(x, \tilde{y}) \tOnTop{\leq}{triangle} f(\tilde{y}) + k \brackets{d_{\XX}(x, \tilde{x}) + d_{\XX}(\tilde{x}, \tilde{y})} \\ &\Downarrow \\ f_k(x) &\leq k d_{\XX}(x, \tilde{x}) + \inf_{\tilde{y} \in \XX} \brackets{f(\tilde{y}) + kd_{\XX}(\tilde{x}, \tilde{y})} \\ &=k d_{\XX}(x, \tilde{x}) + f_k(\tilde{x}) \\ &\Downarrow \\ f_k(x) - f_k(\tilde{x}) &\leq k d_{\XX}(x, \tilde{x}) \onTop{\implies}{\text{symmetry in } x, \tilde{x}} \absval{f_k(x) - f_k(\tilde{x})} \leq k d_{\XX}(x, \tilde{x}). \end{align*}\] Finally, by lower semi-continuity we get point-wise convergence. Indeed, for every \(\alpha < f(x_0)\) we have a ball neighborhood \(\ball{x_0}{\delta} = U\) such that for \(y \in U\) we immediately get \(f(y) + kd_{\XX}(x_0,y) > \alpha\). On the other hand, for \(y \notin U,\) we can see \[ \underbrace{f(y)}_{\geq C} + k\underbrace{d_{\XX}(x_0,y)}_{\geq \delta > 0} \geq C + k\delta \geq \alpha \] for large enough values of \(k\). In total, \(f_k(x_0) \geq \alpha\) for large values of \(k\). As \(\alpha\) was chosen arbitrarily, we can combine it with the (trivial) inequality \(f_k \leq f\) to get the desired point-wise limit. Finally, one can take \(g_k := \min\set{f_k, k} \in \contBddFs(\XX)\) which also converge monotonically to \(f\) from below and are \(k\)-Lipschitz, as \(\absval{g_k(x) - g_k(\tilde{x})}\) is either \(0\) (both are truncated), \(\absval{f_k(x) - f_k(\tilde{x})}\) (see above) or, without loss of generality assume \(f_k(x) > f_k(\tilde{x})\) by symmetry, \[ \absval{g_k(x) - g_k(\tilde{x})} = \absval{k - f_k(\tilde{x})} \leq \absval{f_k(x) - f_k(\tilde{x})} \leq kd_{\XX}(x, \tilde{x}). \]

Corollary 2.3 If \(\cc \colon \XX \times \YY \to \R^{\infty}\) is lower semi-continuous and lower bounded, then \(\pi \mapsto \pi(\cc)\) is also lower semi-continuous for \(\pi \in \probs{\XX \times \YY}\).

Proof. By Lemma 2.1, there exists \((\cc_k)_{k \in \N} \subseteq \contBddFs(\XX \times \YY)\) such that \(\cc_k \uparrow \cc\). By Remark 2.3 \(\pi \mapsto \pi(\cc_k)\) is continuous. Lastly, by Theorem 3.1 (possibly using offset by the lower bound of \(\cc\)), we get \(\pi(\cc) = \sup_{k \in \N} \pi(\cc_k)\), and that \(\pi \mapsto \pi(\cc)\) lower semi-continuous as for sequence \(\pi_j \to \pi\) it holds \[ \pi(\cc) = \sup_{k \in \N} \pi(\cc_k) = \sup_{k \in \N} \lim_{j \to \infty} \pi_j(\cc_k) \leq \liminf_{j \to \infty} \sup_{k \in \N} \pi_j(\cc_k) = \liminf_{j \to \infty} \pi_j(\cc). \]

Proposition 2.2 The Kantorovich optimal transport cost \(V^{\OT}_{\cc}\colon \probs{\XX} \times \probs{\YY} \to \R^{\infty}\), where \(\cc\) is lower semi-continuous and lower bounded, is lower semi-continuous and convex.

Proof. Problem 3 of Exercise sheet 1.

Tip

Our goal will now be to find the dual formulation of \(V^{\OT}_{\cc}\).

Remark 2.4. Assume \(\XX, \YY\) are compact. Using \[ \cpls{\mu, \nu} = \bigcap_{(f,g) \in \contBddFs(\XX) \times \contBddFs(\YY)} \set{ \pi \in \probs{\XX \times \YY} \mid \pi(f \oplus g) = \mu(f) + \nu(g) }, \] where \((f \oplus g)(x,y) := f(x) + g(y)\) we get \[ V^{\OT}_{\cc}(\mu, \nu) = \inf_{\pi \in \probs{\XX \times \YY}} \sup_{(f,g) \in \contBddFs(\XX) \times \contBddFs(\YY)} \pi(\cc - f \oplus g) + \mu(f) + \nu(g). \]

Intuitively, the supremum finds the “most significant violation” of the intersection used to express \(\cpls{\mu, \nu}\) above.

By the minimax theorem since we are taking \(\inf\) over a compact set and \(\sup\) over a vector space and

  • \(\pi \mapsto \pi(\cc - f \oplus g)\) is lower semi-continuous and linear,
  • \((f,g) \mapsto \pi(\cc - f \oplus g) + \mu(f) + \nu(g)\) is linear,

we get \[ V^{\OT}_{\cc} = \sup_{(f,g)} \inf_{\pi} \pi(\cc - f \oplus g) + \mu(f) + \nu(g). \] Setting \(\pi = \dirac_{(x,y)}\) yields \[ \inf_{\pi \in \probs{\XX \times \YY}} \pi(\cc - f \oplus g) \leq \inf_{\pi = \dirac_{(x,y)}} \pi(\cc - f \oplus g) = \inf_{(x,y) \in \XX \times \YY} \brackets{\cc(x,y) - f(x)-g(y)} =: \alpha(f,g) \] and together with \(\pi(\cc - f \oplus g) \geq \inf_{(x,y)} \cc - f \oplus g\) for every \(\pi\) (and diracs are admissible), we get even an equality. Thus \(f(x) + g(y) + \alpha(f,g) \leq \cc(x,y)\) and note that \(\alpha(f,g)\) is finite as \(f,g\) are bounded and \(\cc\) is lower-bounded. Replacing \(f\) with \(\tilde{f} := f + \alpha(f,g)\) (so \(\tilde{f} \oplus g \leq \cc\)) finally produces the duality result: \[ V^{\OT}_{\cc}(\mu, \nu) = \inf_{\pi \in \cpls{\mu, \nu}} \pi(\cc) = \sup_{\substack{(f,g) \in \contBddFs(\XX) \times \contBddFs(\YY) \\ f \oplus g \leq \cc}} \mu(f) + \nu(g). \tag{2.4}\]

Tip

Can we extend the duality result (2.4) for compact \(\XX, \YY\) also to other cases?

2.2.1 Excursion to Convex Analysis

Let us make the following assumptions on the setting we shall be working in:

  1. \(\XX\) is locally convex topological vector space;
  2. \(\XX'\) is the continuous dual space with weak* topology;
  3. \(F \colon \XX \to \R^{\infty}\) is a given proper function.

Definition 2.7 (Convex conjugate) The convex conjugate of \(F\) is said to be the function \(\cconj{F} \colon \XX' \to \R^{\infty}\) such that \[ \cconj{F}(y) = \sup_{x \in \XX} y(x)-F(x). \]

Theorem 2.2 (Fenchel-Moreau duality) Let \(F\) be proper, lower semi-continuous and convex. Then \[ F(x) = \sup_{y \in \XX'} y(x) - \cconj{F}(y). \]

Proof (A sketch of proof).

See also Problem 4 of the Exercise sheet 1.

One always has \(\cconj{F}(y) \geq y(x) - F(x)\) simply by the Definition 2.7, i.e., \(F(x) \geq y(x) - \cconj{F}(y)\). For the other direction, take \((\tilde{y}, \tilde{c}) \in (\XX \times \R)' = \XX' \times \R\) such that \(\tilde{y} - \tilde{c} \leq F\). Then \(\cconj{F}(\tilde{y}) \leq \tilde{c}\) and set \[ R(x) := \sup_{y \in \XX'} y(x) - \cconj{F}(y) \implies R(x) \geq \tilde{y}(x) - \tilde{c}. \] Put differently, \(R(x)\) is greater than all affine minorants \(a\) of \(F\), see Figure 2.2.

Figure 2.2: Affine minorants of \(F(x)\)

Further, \(\epi F = \set{(x,y) \mid F(x) \leq y}\) is closed, convex and non-empty since \(F\) is proper, lower semi-continuous and convex. By applying geometric Hahn-Banach theorem 3.8 we can separate \(\epi F\) and \((\tilde{x}, \tilde{c}) \neq \epi F\) (corresponding to any affine minorant of \(F\)), which gives us the desired inequality.

2.2.2 Disintegration of Measures

Definition 2.8 (Probability Kernel) The mapping \(K\colon \XX \to \probs{\YY}\) is a (probability) kernel if it is measurable with respect to \(\Borel(\XX)\) and the Borel \(\sigma\)-algebra on \(\probs{\YY}\).

Proposition 2.3 The following are equivalent:

  1. \(K\) is measurable,
  2. \(\forall f \in \contBddFs(\YY)\) the mapping6 \(x \mapsto \int f(y) K(x; \d y)\) is measurable, and
  3. \(\forall f \in \bddMeasFs(\XX \times \YY)\) the mapping \(x \mapsto \int f(x,y) K(x; \d y)\) is measurable.

Proof. Firstly, the weak topology on \(\probs{\YY}\) is generated by countable subsets, see Remark 2.1 (3, and possibly 5), \[ \mathscr{C} := \set{\set{\mu \mid \mu(f_k) < \alpha} \mid \alpha \in \Q, k \in \N} \] with \((f_k)_{k \in \N} \subset \contBddFs(\YY)\). Therefore, \(\sigma(\mathscr{C}) = \Borel(\probs{\YY})\).

Then \(K\) is measurable \[\begin{align*} &\iff \forall C \in \mathscr{C}: \; K^{-1}(C) \in \Borel(\XX) \\ &\iff \forall (k,q) \in \N \times \Q: \; \set{x \in \XX \mid \int f_k(y) K(x; \d y) < q} \in \Borel(\XX) \\ &\iff \forall (k,q) \in \N \times \Q: \; x \mapsto \int f_k(y) K(x; \d y) \text{ is measurable}. \end{align*}\] The last remaining equivalence (2) \(\iff\) (3) follows by monotone class argument.

Definition 2.9 (Gluing) Let \(K \colon \XX \to \probs{\YY}\) be a kernel and \(\mu \in \probs{\XX}\). The gluing \(\mu \otimes K \in \probs{\XX \times \YY}\) of \(\mu\) and \(K\) is defined by \[ \forall f \in \bddMeasFs(\XX \times \YY): \; \int f \d \mu \otimes K := \iint f(x,y) K(x; \d y) \mu(\d x). \]

Note that the right-hand side of the gluing definition is well-defined by Proposition 2.3 (3).

Theorem 2.3 (Disintegration) Let \(\pi \in \probs{\XX \times \YY}\), then there exists a probability kernel \(K \colon \XX \to \probs{\YY}\) such that \(\pi = \mu \otimes K\) with \(\mu := \pf{\pr{\XX}}{\pi}\). Secondly, let \(\tilde{K}: \XX \to \probs{\YY}\) be another disintegration kernel, i.e., it satisfies the above equality. Then \(\tilde{K} = K\) \(\mu\)-almost everywhere.

Proof. Omitted.

Note

The disintegration of \(\pi\) with respect to \(\mu\) is denoted \((\pi_x)_{x \in \XX}\).

Example 2.3  

  1. Let \(T : \XX \to \YY\) be measurable and \(\rnd X \sim \mu\), then \[ \pi \Law (\rnd X, T(\rnd X)) = \pf{\brackets{\id, T}}{\mu} \in \probs{\XX \times \YY} \implies \pi_x = \dirac_{T(x)}. \]
  2. Let \((\rnd X, \rnd Y) \sim \pi\), then \(\pi_x = \Law(\rnd Y \mid \rnd X)\) a.s.
  3. Consider \(\XX = \YY = \R^d\) and \(\pi(\d x, \d y) = f(x,y) \d x \d y\), then \[ \pi_x(\d y) = \frac{f(x,y)}{\int_{\R^d} f(x,y'),\d y'},\d y \quad \text{for } \mu\text{-a.e. } x. \]
(a) Disintegration of example 1
(b) Disintegration of example 2,3
Figure 2.3: Visualizations of disintegrations of various measures.

Theorem 2.4 (Duality) Consider the usual setting of optimal transport (see beginning of this chapter). Let \(\cc \colon \XX \times \YY \to \R^{\infty}\) be lower semi-continuous and lower bounded cost function, then \[ V^{\OT}_{\cc} = \sup_{\substack{(f,g) \in \contBddFs(\XX) \times \contBddFs(\YY) \\ f \oplus g \leq \cc}} \mu(f) + \nu(g), \tag{2.5}\] \[ \hphantom{V^{\OT}_{\cc}} = \sup_{\substack{(f,g) \in \lone(\mu) \times \lone(\nu) \\ f \oplus g \leq \cc}} \mu(f) + \nu(g). \tag{2.6}\]

Remark 2.5.

  1. Weak duality: let \((f,g) \in \lone(\mu) \times \lone(\nu)\) such that \(f \oplus g \leq \cc\), and \(\pi \in \cpls{\mu, \nu}\), then \[ \mu(f) + \nu(g) = \pi(f \oplus g) \leq \pi(\cc), \] which implies \(V^{\OT}_{\cc} \geq\) (2.6).
  2. (2.6) holds even when \(\cc \in \bddMeasFs(\XX \times \YY)\) (via Choquet capacitability theory).
  3. When \(\cc\) is even Lipchitz, one can restrict \((f,g)\) in (2.5) to be Lipschitz as well.
  4. For \((f,g) \in \contBddFs(\XX) \times \contBddFs(\YY)\) admissible, the \(\cc\)-transforms \[\begin{align*} \cbTr{f}(y) &:= \inf_{x \in \XX} \brackets{\cc(x,y) - f(x)} \geq g(y), \\ \cTr{g}(x) &:= \inf_{y \in \YY} \brackets{\cc(x,y) - g(y)} \geq f(x) \end{align*}\] satisfy \(f \oplus g \leq f \oplus \cbTr{f} \leq \cc\), so replacing \(f \oplus g\) by \(f \oplus \cbTr{f}\) improves the value in (2.6).

  1. Convex combinations of probability measures are still probability measures and the marginals are conserved.↩︎

  2. Also known as induced topology, as is the topology on the set \(X\) with respect to a family of functions on \(X\) such that it is the coarsest topology on \(X\) that makes those functions continuous.↩︎

  3. Namely, every embedding is injective and continuous.↩︎

  4. Hausdorff topology is that such distinct points have disjoint neighborhoods — that is why one goes to the indicators of such neighborhoods being in \(\bddMeasFs(\XX)\) by a monotone class argument.↩︎

  5. A set \(X\) is relatively compact when \(\closureOf{X}\) is compact.↩︎

  6. Here \(K(x; \d y)\) designates that \(x\) determines the measure from \(\probs{\YY}\) used for integration in the variable \(y\).↩︎