Computational Optimal Transport 精読会 記録 (#2: 2.4)

# 背景

- 前回: [Computational Optimal Transport 精読会 記録 (#1: 2.1-2.3)](https://qiita.com/takilog/items/3f150a6868a8f58b2ed6)
- 職場で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$となり，距離であるかれこれが最適であるので，主張が正しい


- 三角不等式について
    - ヒストグラムと離散測度についてのみ読む場合，2.4章の最大の山場（特に証明を細かく追う場合）　
    - 上に書いた通り，$n=m$と設定すると，真面目に$0$が入っているヒストグラムを扱う場合がある
    - これを回避するため，$0$である要素を$1$にして回避する新しいヒストグラム$\tilde{\mathbf{b}}$を扱うというテクニックが出てきて，これが賢い


- 前提
    - ヒストグラム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$をイメージすれば良い（はず）

- このとき以下が成り立つ

```math
\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を読み解く