Optimal Transportation
次元がd * dのコスト行列$ Mが与えられた時, 輸送行列$ Pを用いて確率分布$ rを$ cにマッピングすることを考える. この問題を最適輸送という 定式化: $ d_M (r, c) \stackrel{\mathrm{def}}{=} \underset{P \in U(r,c)}{min}〈P, M 〉.
コスト行列$ Mが円錐型の距離行列に属する時 ($ Mが距離行列の時), 最適解の$ dM (r, c)は距離と定義する
定義: $ \mathcal{M} = {M \in \R^{d\times d}_+ : ∀i ≤ d, m_{ii} = 0; ∀i, j, k ≤ d, m_{ij} ≤ m_{ik} + m_{kj} }.
Mはコスト行列
$ \forallは全称記号. ここでは任意のiということ 一般的な行列$ Mの最悪計算量は, どのアルゴリズムでも$ O(d^3 logd). 立法体以上に増加する これに制約を設け, 近似的な解を出す場合には計算速度が出る
ここの英語だけ異様に難しい
Much faster speeds can be obtained however when placing all sorts of restrictions on M and accepting approximated solutions, albeit at a cost in performance (Grauman and Darrell, 2004) and a loss in applicability.
all sorts of restrictionsで様々な種類の制約