More than 5 years have passed since last update.

Computational Optimal Transport 精読会記録 (#6: 3.3-3.4)

Last updated at 2019-04-24Posted at 2019-04-24

背景

Kantorovich problem: $L_C(\mathbf{a,b}) = \min_{\mathrm{P}\in U(\mathbf{a, b})} \langle C, P \rangle$, $U(a, b) = \{\mathrm{P}\in \mathbb{R}_+^{n\times m}\mid \mathrm{P} \mathbb{1}_m = \mathbf{a}, \mathbf{P}^T \mathbb{1}_n = \mathbf{b} \}$
Dual problem $L_C(\mathbf{a,b}) = \max_{(\mathbf{f, g})\in R(C)} \langle \mathbf{f, a}\rangle + \langle \mathbf{g, b}\rangle$, $R(C) = \{(\mathbf{f,g})\in\mathbb{R}^n\times \mathbb{R}^m \mid \mathbf{f \oplus g} \leq C\}$

arXiv版では式の参照番号がデタラメになっているので注意
- 例: arxiv版の(2.24), (2.11)はそれぞれ(2.11)と(2.20)の間違い
主張: 最適解の条件から，任意の山のインデクスペア$(i,j)$について，${\bf P}^\star_{i,j}(C_{i,j} - ({\bf f}^\star_i + {\bf g}^\star_j)) = 0$が成り立つ
- これは輸送量が0になるか，ポテンシャルが共に0になることを意味する
証明
- 強双対定理より目的関数値が一致する: $\langle P^\star, C\rangle = \langle f^\star, a\rangle + \langle g^\star, b\rangle$ ということ
- またmarginal $a, b$はcoupling matrixの定義より$P^\star 1_m = a, P^{\star T} 1_n = b$である
- また要素積の和$\langle \cdot, \cdot \rangle$は分解すると要素を左右に入れ替えられるようになる
- 式変形によって主張が成り立つ
このProp3.2から以下の名称を新しく定義
- complementary: もし$P_{i,j} > 0$ (輸送する)ならば，$C_{i,j} = f_i + g_j$であること
Complenetaryかつfeasibleな輸送について，次の定理が成り立つことが分かる

結局タイトルのComplementary Slacknessはどういう意味の単語なのかよく分からなかった
- スラック変数的なことをなにか言っているのか，それとも合わせて1単語なのか

式3.4でやることは，主に今までCoupling matrixといっていた輸送$P$がどのようなものなのか？を議論する
特に，線形計画の基本的な事実として(ここからあまり正確ではない表現)最適解が凸多面体の頂点にある(ここまで)という事実とどう関連するのかを説明していく
- 補足: extremal point: もし$x = (y + z) / 2$という点が存在するとき，$x=y=z$に限る
この節はそこそこ数式の誤りがあるが，全体的に議論展開は問題ない（だいたい）
まずヒストグラム間の輸送（左側から右側に運ぶ）というアイデアを，二部グラフで描く（本文Figure 3.1）

主張: 二部グラフのうち，$P_{i,j} > 0$である場合のみ辺を貼ったグラフを$G(P)$で表す．もし$P$が$U(a,b)$のextremal pointであるとき，$G(P)$はサイクルを持たない．つまりグラフ$G(P)$の辺は最大$n+m-1$本になる．
証明: 後半はグラフ理論から成り立つ．前半を示すために，具体的にサイクルを持った解を構成してみると良い(Figure 3.2)
- 左: 外点であるにもかかわらず，サイクルである例があったとする
- 中/右: それぞれ$\epsilon$ずつ輸送量を変化させた2つの輸送を構成する
- $\epsilon$が十分小さいとき，これはcoupling matrixになっているので，$U(a,b)$の要素である
- また$P = (Q + R) / 2$である
- しかしこのとき$P=Q=R$になっていないため，$P$が外点であるという前提が誤っており，主張が成り立つ．

次回はGW前最後の回で，§3.5をやっていく