Computational Optimal Transport 精読会 記録 (#15: 4.3 その2，4.4 その1)

# 背景


- 前回: [Computational Optimal Transport 精読会 記録 (#14: 4.3 その1)](https://qiita.com/takilog/items/48adb8e9c29df8f30ee8)は7/4に開催，今回は7/16に開催
- 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている


### 前回の振り返りと今回の内容

- エントロピー正則化付きの輸送問題
    - $L^\varepsilon\_C({\bf a}, {\bf b}) = \min_{{\bf P}\in U({\bf a},{\bf b})} \langle {\bf P}, C\rangle - \varepsilon H({\bf P})$
- Sinkhornアルゴリズム最高 → ちゃんと収束するよ
  - $\mathbf{u}^{(l+1)} = \frac{\mathbf{a}}{\mathbf{Kv}^{(l)}}$, $\mathbf{v}^{(l+1)} = \frac{\mathbf{b}}{\mathbf{K}^T\mathbf{u}^{(l + 1)}}$
- カーネル$K$がうまい形をしているとき，高速な計算ができる（特にGPU利用）
- 今回: 詳細を確認していく

----

## Remark 4.18

- 行列積の計算は頑張って高速化する枠組みがたくさんある（おそらく）
- 例えばカーネルがインデクスの間についてのみ依存する場合（＝前回の謎の図がこれに相当）: $K_{i,j}=k_{i-j}$
    - 格子状に区切るような問題
    - このとき，$Kv$などの計算は，新しく作った$k_{i-j}$との畳込み計算になっている: $Kv = k \star v$
    - 畳み込み計算は，例えばフーリエ変換すればよい: $\mathcal{F}(k\times v) = \mathcal{F}(k) \odot \mathcal{F}(v)$
    - フーリエ変換を高速に計算したり，近似する手法はいろいろ研究されている


## Remark 4.19

- 熱(heat)に関する方程式についての知見を使ってみる(Varadhan's formula, 1967)
- 熱の拡散方程式的な文脈
    - ここで熱は平面を伝わっていくのではないので，曲がった空間（CS的には多様体）を考えられる
    - コストはその曲がった空間上での距離としておく: $C_{ij} = d_\mathcal{M}(x_i, y_j)^p$
        - 熱量をイメージ
    - カーネル $K=\exp(-d_\mathrm{M} / \varepsilon)$ をベクトルに作用させる点を近似しよう

- とくに$p=1, p=2$の場合に議論がされている(Varadhan's formula)
    - $p=1$
        - $-\frac{\sqrt{t}}{2} \log(\mathcal{P}_t (x, y)) = d\_\mathcal{M}(x, y) + o(t), \mathcal{P}\_t = (\mathrm{Id} - t\Delta\_\mathcal{M})^{-1}$
        - この$\Delta\_\mathcal{M}$は多様体上で熱が拡散していく様を表すオペレータ（たぶん）
        - ここで$ g - t\Delta\_\mathcal{M}g = f$という高等な関係がある
    - $p=2$
        - $\sqrt{-4t\log(\mathcal{H}_t(x,y))} = d\_\mathcal{M}(x,y) + o(t)$
        - ここで$g_t = \int\_\mathcal{M} \mathcal{H}\_t(x,y)f(y)dy$ は $\frac{\partial g_t(x)}{\partial t} = (\Delta\_\mathcal{M} g_t)(x)$という高等な関係がある（謎）

- まったくわからないが，式が言っていることはこういうこと
    - 多様体$\mathcal{M}$上の$\Delta_\mathcal{M}$は直接扱えないので，離散化してラプラシアン$L$で扱う
    - $p=1$の場合，$\varepsilon = \frac{\sqrt{t}}{2}$と設定し，$K$を掛けるところを$(\mathrm{Id}-tL)^{-1}$に置き換える．
    - $p=2$の場合，$4t=\varepsilon$と設定し，$K$の掛け算のところを$(\mathrm{Id}-\frac{t}{R}L)^{-R}$で置き換える．
- これらの方程式(linear system)は，単純に解くのは難しそうに見えるが，たとえばコレスキー分解でシステム行列を分解してうまくやると効率的に計算できる


## Remark 4.20

- 最適化の世界では最適化法を加速させる手法があるが，これを利用できる

# §4.4 Stability and Log-Domain Computations

- 以前Sinkhornアルゴリズムの紹介をしたときに，$\log$ ドメインじゃないとつらいという話があったが，それに関係する話
- ついでにdual側の話をする

## Prop 4.4 エントロピー正則化付き輸送問題のデュアル側について

- 次のような目的関数(4.30)の制約なし最適化問題を考える
    - これまでと同じデュアルのベクトル$f, g$だが面倒なので細字

$$L_C^\varepsilon(a,b) = \max_{f, g} \langle f, a\rangle + \langle g, b\rangle - \varepsilon \langle \exp(f/\varepsilon), K\exp(g/\varepsilon)\rangle$$

- このとき最適解$f^\star, g^\star$は，以前出てきた$u, v$と$u = \exp(f/\varepsilon), v=\exp(g/\varepsilon)$という関係を持っている(4.31)

### Prop 4.4の証明

- 以前の証明から，ラグランジュの未定定数$f, g$を用いてPrimalの最適解は $P_{ij} = \exp(f_i/\varepsilon) \exp(-C_{ij}/\varepsilon) \exp(g_j/\varepsilon)$ という形になるという話があった（3回前ぐらい）
- ラグランジュ関数(日本語がダメ)にこの最適解を代入することで，式(4.32)を得る．これはラグランジュ関数についていた制約に関する項は消える（なぜなら最適解は条件を満たしているから）（下の式はexpを書くのが面倒でもうu, vになっている）

$$\langle u, (K \odot C) v\rangle - \varepsilon H(\mathrm{diag}(u) K \mathrm{diag}(v)$$

- エントロピー正則化の項は書き直すと $\varepsilon \langle P, \log P - 1\rangle$で，これを$P$に上の解の形を代入することで

$$-\langle u, (K\odot C) v\rangle + \langle f, a\rangle + \langle g, b\rangle - \varepsilon \langle u, Kv\rangle$$

- となる．第一項同士が打ち消し合うので，双対定理からProp 4.4を得る．

# Next

- §4.4をやっていく(7/26)