従って、\(n\)に対して\(M\)や\(s\)が非常に大きいような場合は最初にデータ構造を作ってしまうべきである。小さい\(M\)が保障されておりサンプリングの回数が大きくない場合は棄却サンプリングは有効である。二つ目は\(M\)の計算コストである。上記では\(M\)の計算コストは無視した。一般に二つの分布が与えられたとき、その間の\(M\)がどの程度に収まるかを計算するのは\(O(n)\)の時間が必要となる。n)\)となり常にセグメント木を用いるアプローチより低速である。従って、棄却サンプリングを有効に用いるには、目的分布の既知の性質から近いと確信が持てる提案分布が構成できなければならない。y\)を求める計算は\(O(n)\)を要する。\(x,y\)についていくつか追加の操作が許されているとき、ある誤差の範囲内でより高速に内積の値を推定することができる。\frac{y_i}{x_i}|x|^2\)をとる乱数\(z\)を考える。|x|^2|y|^2\)となる。"estimation")plt.legend()plt.show()乱数の平均と分散が与えられたとき、median-of-meansと呼ばれるテクニックで精度を保証できるサンプル数を導くことができる。\rangle\)を計算する。\delta^{-1}\)回行い、その中央値を取り出す。|x||y|\)以内にいる確率は\(1-\delta\)以上であることが保証できる。\delta^{-1})\)である。ここまでのまとめ¶ここまでで紹介した要素をいったんまとめよう。nm)\)の時間で実現する。S_{ij}^2\)としておけば、上記のノルムはL2-normの二乗に、要素総和はフロベニウスノルムの二乗に、サンプリングは二乗重みでのサンプリングになる。AB\)と表されるとき、\((A,B)\)を\(V\)の簡潔表現と呼ぶ。簡潔表現\((A,B)\)を\(k,\epsilon^{-1}\)に対して多項式時間で与える。SVD}\)はSVDを用いて得られる\(T\)に対する最良のrank-\(k\)近似である。F}\)は行列のフロベニウスノルムである。棄却サンプリング¶\(n\)個のシンボルに対する目的分布\(\{p_i\}\)と提案分布\(\{q_i\}\)を考える。これらの分布は以下を満たすとする。n)\)で可能になる。長さ\(n\)のベクトル\(x,y\)について、以下が満たされるとする。与えられた添え字\(i\)について、\(x_i,y_i\)が効率的に計算できる。ノルム\(|x|\)を効率的に計算できる。添え字\(i\)を\(\frac{x_i}{|x|}\)の確率で得るサンプリングを効率的に行える。\delta^{-1})\)で行うことができる。上記までのテクニックが分かっていれば、後は組み合わせるだけである。Tangによる論文の殆どは、上記を組み合わせた時に要請される条件が満たされることの証明と、誤差や計算量の解析である。poly}(\epsilon)\)に抑えられるという結果だけ述べておく。Tangの論文は現時点(2019年3月)で3本[1][2][3]からなるが、この記事では最初の二つを紹介する。いっても、二本目の論文の結果は一本目の論文の中間結果として得られるものなので、実質一本目の紹介である。Tangのアルゴリズムは全体のアルゴリズムの前半部分として\(i\)行ベクトルの主成分分析を行う。主成分分析とは以下のような手続きである。V_k\)の要素を\(A_i\)のTop-\(k\)主成分と呼ぶ。行列\(A\)はセグメント行列を用いた行列に格納することで、FKVアルゴリズムを実施できる。T},UD^+)\)を効率的に得ることができる。この時、\(A_p\)は\(p\)個の行が\(A\)からサンプリングされたセグメント木行列表現を持つ。D_k^+\]を計算することである。D_k^+)_j\]を求める操作を\(k\)回繰り返せばよい。poly}(k)\)で計算可能である。従って、内積の推定を行う条件を満たしている。\(V_k\)の列ベクトルはユニタリ行列の列を近似したものであるから、ノルムは\(O(1)\)である。|A_i|\)である。行列\(A\)の右特異値行列のTop-\(k\)特異値に相当する行を取り出したものを\(V_k\)とする。V_k^{\dagger}\]という計算を行うことと等しい。我々の目的は与えられた添え字\(i\)について、上記のように求まる\(A_i'\)から、成分のL2-normの重みでサンプリングを行うことである。A_p\]からサンプリングすることである。これを棄却サンプリングを用いて行う。T}\)と定義すると、以下のようになる。B\)の任意の列ベクトルはサンプリング可能であることを示す。B^{(j)}\)である。B^{(j)}|^2}\]である。\frac{|(A_p)_{jl}|^2}{|(A_p)_l|^2}\]という提案分布を考えると、これは効率的にサンプリング可能であり、かつコーシーシュワルツの不等式と\(V'\)の列は\(V'\)が等長行列であることから列ノルムが1であることを用いると、\(M\)が\(k\)の多項式で抑えられることが示せる。B\)の任意の列ベクトルはサンプリング可能である。T}\)は効率的にサンプリング可能であることを示す。\frac{|C_{il}|^2}{|C^{(l)}|^2}\]を提案分布として用いる。この提案分布の積の左はセグメント木の性質を用いてサンプリング可能であり、右は直前の棄却サンプリングで可能である。左部は特定の\(i\)について計算することが難しいため、近似的に以下の値を用いる。distanceの誤差は乗るものの、効率的に棄却サンプリングが可能となる。