背景

前回: Computational Optimal Transport 精読会記録 (#1: 2.1-2.3)
職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている

今回の範囲の内容

$p$-Wasserstein distanceが距離であること

§2.4

これまでの議論と同じく $n$ 次元ヒストグラムを考えていく（もしくは離散測度 $\alpha, \beta$ ）
同種のヒストグラムを考え，ビン (砂山の位置に対応) 間の移動コストなどに対応する ground metric $\mathbf{C}$を仮定
- (補足) 精読回中に議論が出たが，ここのmetricはdistanceと同意味で使われていると思われる
以降ではしばらく，ビンの個数が同じ2つのヒストグラムを想定
- (補足) これまでビンは重さ$0$ではないと想定していたが，長さを揃えると重さが$0$になる場合を扱う必要があるのだと思う(特にProp 2.2)

Prop 2.2

前提
- Monge Problemで利用するコスト行列 $\mathbf{C}$ として，ある距離 $\mathbf{D}$の$p$乗を利用すると
- $\mathbf{D}$ は距離である
  - (i) $\mathbf{D}$ はsymmetric
  - (ii) $\mathbf{D}(i,j) = 0$ は $i=j$ に限る
  - (iii) $\mathbf{D}$ は三角不等式を満たす
- $p$-Wasserstein distanceを $\mathrm{W}_p(\mathbf{a,b}) = L_{\mathbf{D}^p} (\mathbf{a, b})^{1/p}$ で定める
主張
- $\mathrm{W}_p(\mathbf{a,b})$ はヒストグラム間の距離である (つまり (i)-(iii)を満たす)

Prop 2.2 証明の精読

対称性について: 以下の2つの事実から導かれる
- $L(\mathbf{a,b}) = \min_{P\in U(\mathbf{a,b})} \sum C_{i,j} P_{i, j}$
- $P\in U(\mathbf{a,b})$であるとき，$P^T\in U(\mathbf{a,b})$である
- $C_{i,j}$ が対称行列であるので，$C_{i,j}=C^T_{i,j}$
正性(?)について
- $\mathbf{a} \neq \mathbf{b}$ であるとき，$P$は対角成分以外に非ゼロ要素を持つ
  - 非ゼロ要素の和は0より真に大きいため，$\mathrm{W}(\mathbf{a,b}) > 0$である
- $\mathbf{a} = \mathbf{b}$ であるとき，$P$を$\mathrm{diag}(\mathbf{a})$と置くと，$\mathrm{W}(\mathbf{a,b})=0$となり，距離であるかれこれが最適であるので，主張が正しい
三角不等式について
前提
- ヒストグラム3つ: $\mathbf{a,b,c}$
- Monge Problemの解: $\mathbf{P, Q}$ ($\mathbf{P}\in U(\mathbf{a,b})$, $\mathbf{Q}\in U(\mathbf{b,c})$)
- ゼロ要素を回避するため，coupling matrix $\mathbf{S} = \mathbf{P} \mathrm{diag}(1 / \tilde{\mathbf{b}}) \mathbf{Q} \in \mathrm{R}_+^{n\times n} \in U(\mathbf{a, b})$ を導入するのがポイント　
  - 本文中の解説通り，$\mathbf{S}\mathbb{1}_n = \mathbf{a}$となる
三角不等式の証明のポイント
- $\frac{\mathbf{P}_{ij} \mathbf{Q}_{jk}}{\tilde{\mathbf{b}_j}}$ という一見分からない項がMinkowski's inequalityを適用するときに出てくる
  - (補足) 個人的に悩んだが，これはよく見るとタダの数なので，$((\cdot)^{1/p})^p$ という式変形をしてカッコの中に入れる．あとは適当に文字を置き換えて，通常のMinkowski's inequalityを利用し，不等式を展開する．

Remark 2.15

$0 < p \leq 1$の場合，Minkowski's inequalityが利用できないため，特殊ケースとして扱う必要がある

その1

$\mathbf{D}^p$が 証明なしに 距離であるとする
すると$\mathrm{W}_p(\mathbf{a,b})^p = L_{\mathbf{D}^p}(\mathbf{a,b})$ は Prop 2.2より距離になっている

その0: $\mathbf{D}^p$ が距離の(i)-(iii) を満たす証明

精読会でいろいろ議論されたが，概ね次のような手法で証明された（自分はよく分からなかったので聞いていた）　
パターン1
- 三角不等式を直接(何らかの手法で)証明する
パターン2
- 今$p \leq 1$であるため，これが$q=1/p$であれば$q > 1$となって，Minkowski's inequalityが利用できるように式変形する
教えてもらったパターン2の証明(概略)を以下にメモする

$\mathbf{D}$自体が三角不等式を満たしているとき，これを$p$乗した場合に成り立つかどうかを示す

今 $0 < p$であるため，$a \leq b + c$である3要素について，$a^p \leq (b + c)^p$が成り立つ

ここで右辺を$(b + c)^p = {(b^p)^{1/p} + (c^p)^{1/p})}^p = {((b + \mathbf{0})^p)^{1/p} + ((c + \mathbf{0})^p)^{1/p})}^p$ というやばい気がする式展開を信じると

結果としてMinkowski's inequalityより$b^p + q^p$となる

Remark 2.16, 2.18, 2.20

Skip

Remark 2.19

測度の積分を扱う必要があり，簡単には理解できないが，**仮にこの議論を離散測度でやったら？**という観点から議論したのでメモしておく
離散測度の場合， $\alpha = \sum \mathbf{a}_i \delta_{x_i}$ である砂の地位が，$\tau$分だけずらされるイメージで$T_\tau$をイメージすれば良い（はず）
このとき以下が成り立つ

\begin{align}
\mathcal{W}_2^2(T_{\tau\#}\alpha, T_{\tau'\#}\beta) &= L_{\mathbf{D}^2}(T_{\tau\#}\alpha,  T_{\tau'\#}\beta) \\
&= \min_{P\in U(a,b)} \langle \mathbf{D}^2, P\rangle \\
\end{align}

距離$\mathbf{D}^2$について，それぞれ$\tau, \tau'$分だけスライドさせられているので以下のように展開する
- $||x - y||^2 = ||x - y||^2 - 2\langle \tau - \tau', x - y\rangle + ||\tau - \tau'||^2$
- つまり$\mathbf{D}^2$の部分は，これら3つの項の和に分けて評価すれば良さそう
第一項: 最適化問題の対象としてそのまま残り，これが$\mathcal{W}_2^2(\alpha, \beta)$ となる
第二項: それぞれ$\sum_{i,j}$を考えると，$x$の場合は$\sum_{j} y_j$が，$y$の場合はその逆が計算され，結果として平均的なものになる
第三項: 最適化問題に寄与しない定数項として，シフト分が残る
これらを考慮してRemark 2.19の意味が概ね理解できる（離散測度，ヒストグラムの場合）

次回

2.5のDual Problemを読み解く