背景

エントロピー正則化付きの輸送問題
- $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)}}$
今回: Sinkhornアルゴリズムの加速

§4.3 Speeding Up Sinkhorn's Iterations

毎回$K$やら$K^T$の掛け算が必要になるので一見思い気がするが，GPUを使えばとりあえず複数本ヒストグラムの計算は同時に可能
Sinkhornの更新式はほとんどそのまま行列形になる
- $U^{(l+1)} = \frac{A}{KV^{(l)}}$
- $V^{(l+1)} = \frac{B}{K^T U^{(l+1)}}$
$V$と$U$が収束したかどうかを確認するような式として(4.26)の下に載っている式は間違っているらしい（詳細不明）
- 誰か教えて

高速化するための一つの特殊ケースとして，カーネル$K$が分割できる場合
イメージが難しいが，コスト行列が小さいコスト行列の和で書き直せるケースを言っている
- $i=(i_k)_{k=1}^d, j=(j_k)_{k=1}^d \in [n_1]\times\dots\times[n_d]$
- $C_{ij} = \sum_{k=1}^d C^k_{i_k, j_k}$
- Sinkhornアルゴリズムでは$C$は$\exp(\cdot)$の中に入って使われるので，カーネルとしては$K=\prod_{k=1}^d K^k_{i_k, j_k}$となる
例: 格子上のヒストグラムで，各次元ごとの距離の和になるようなケース($q$-ノルム)
あまりよくわかってない
ノートには謎の図だけ残されていた