Johnson and Lindenstrauss Lemmaとその構成論的証明

f:id:yumaloop:20190620010600p:plain:w500

JL-補題
構成論的証明
参考文献

ランダム行列理論（Random projection）の基本定理であるJohnson and Lindenstrauss Lemmaについて解説します． JL-補題は「変換前後でサンプル点どうしのユークリッド距離を変えない」ような関数 $f$ の存在を主張しており，これは具体的にランダム行列 $A$ を用いた線形写像として構成できます．

JL-補題

$d$ 次元空間 $Q \subset {\mathbb{R}}^{d}$ 上にある $n$ 個のサンプル点を考える．任意の $\epsilon \in (0,1)$ について，

$$ k \geq \frac{4 \log n}{ {\epsilon}^{2}/2 - {\epsilon}^{3}/{3}} $$

をみたす整数 $k$ に対して，以下をみたす $f: \mathbb{R}^{d} \to \mathbb{R}^{k}$ が存在する．

$$ \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \forall u,v \in Q \subset {\mathbb{R}}^{d}, \\ (1 - \epsilon)\norm{u - v}^{2} \leq \norm{ f(u) - f(v) }^{2} \leq (1 + \epsilon) \norm{ u - v }^{2} $$

構成論的証明

写像 $f: \mathbb{R}^{d} \to \mathbb{R}^{k}$ として， $k \times d$ のランダム行列 $A$ で定義される線形写像 $f_A$ を考える．

$$ {f}_{A}(x) = \frac{1}{\sqrt{k}} Ax \\ where~A_{ij} ~ {\scriptsize i.i.d.} \sim \mathcal{N}(0,1) $$

まず，正規分布の線形性・再生性*1より，

$$ \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \begin{eqnarray} A_{ij}(x_{j}) &\sim& \mathcal{N}\left( 0, {x_{j}}^{2} \right) \\ {\{Ax\}}_{j} &\sim& \mathcal{N}\left( 0, \norm{ x }^{2} \right) \end{eqnarray} $$

が成り立つ．正規化して変数 $Z_j$ を定義すれば，これは標準正規分布に従う．

$$ Z_j = \frac{{\{Ax\}}_{j}}{\norm{x}} \sim \mathcal{N}\left( 0, 1 \right) $$

さらに，

$$ \norm{Ax}^{2} = \sum_{j=1}^{k} {\{Ax\}}_{j}^{2} $$

が成り立つことに注意すると，

$$ \frac{\norm{Ax}^{2}}{\norm{x}^{2}} = \sum_{j=1}^{k} \frac{{\{Ax\}}_{j}^{2}}{\norm{x}^{2}} = \sum_{j=1}^{k} {Z_j}^{2} \sim \chi_{k}^{2} $$

となる．すなわち，行列 $A$ による線形変換の前後で，ノルムを考えるとき，これはカイ二乗分布によって評価できる．

$$ \begin{eqnarray} Pr\left( \norm{f_{A}(x)}^{2} \lt (1 + \varepsilon) \norm{x}^{2} \right) &=&Pr\left( \norm{ \frac{1}{\sqrt{k}} Ax }^{2} \lt (1 + \varepsilon) \norm{x}^{2} \right) \\ &=& Pr\left( \norm{ Ax }^{2} \gt (1 + \varepsilon) k \norm{x}^{2} \right) \\ &=& Pr\left( \frac{\norm{ Ax }^{2}}{\norm{x}^{2}} \gt (1 + \varepsilon) k \right) \\ &=& Pr\left( \sum_{j=1}^{k} {Z_j}^{2} \gt (1 + \varepsilon)k \right) \\ &=& Pr\left( \chi_{k}^{2} \geq (1 + \varepsilon)k \right) \end{eqnarray} $$

次に自由度 $k$ のカイ二乗分布 $\chi_{k}^{2}$ を表す確率密度関数を考え，上式の右辺を上から抑えたい．

$$ p(\cdot | k) = \frac{1}{{2}^{\frac{k}{2}} \Gamma \left( \frac{k}{2} \right) } {x}^{\frac{k}{2} - 1} {e}^{- \frac{x}{2}} $$

ややテクニカルだが，確率密度分布から不等式を整理していく．途中で定数 $\lambda \in (0, \frac{1}{2})$ を導入している．

$$ \begin{eqnarray} Pr \left( \chi_{k}^{2} \geq (1 + \varepsilon)k \right) & = & Pr \left( \sum_{i=1}^{k} Z_{i}^{2} \gt (1 + \varepsilon)k \right) \\ & = & Pr \left( e^{\sum_{i=1}^{k} Z_{i}^{2}} \gt e^{(1 + \varepsilon)k} \right) \\ & = & Pr \left( e^{\lambda \sum_{i=1}^{k} Z_{i}^{2}} \gt e^{ \lambda (1 + \varepsilon)k} \right) ~~~ (0 \lt \lambda \lt \frac{1}{2}) \\ & \leq & \frac{\mathbb{E}[e^{\lambda \sum_{i=1}^{k} Z_{i}^{2}}] }{e^{(1 + \varepsilon)k \lambda}} \\ & = & \frac{{ \left( \mathbb{E}[ e^{\lambda {Z_{1}^{2}}} ] \right) }^{k}}{e^{(1 + \varepsilon)k \lambda}} \\ & = & e^{-(1 + \varepsilon) k \lambda } {\left( \frac{1}{1 - 2 \lambda} \right)}^{\frac{k}{2}} \end{eqnarray} $$

ここで， $\lambda = \frac{\varepsilon}{2(1 + \varepsilon)}$ を代入すれば，

$$ \begin{eqnarray} Pr \left( \chi_{k}^{2} \geq (1 + \varepsilon)k \right) & = & {\left( (1 + \varepsilon)e^{- \varepsilon} \right) }^{\frac{k}{2}} \\ & \leq & \exp \left( - \frac{k}{4} ( {\varepsilon}^{2} - {\varepsilon}^{3} ) \right) \end{eqnarray} $$

が求められる．ただし．

$$ 1 + \varepsilon \leq \exp \left( \varepsilon - \frac{{\varepsilon}^{2} - {\varepsilon}^{3}}{2} \right) $$

を使った．以上をまとめると，ランダム行列 $A$ を用いて構成される写像

$$ {f}_{A}(x) = \frac{1}{\sqrt{k}} Ax \\ where~A_{ij} ~ {\scriptsize i.i.d.} \sim \mathcal{N}(0,1) $$

に対して，

$$ \begin{eqnarray} Pr\left( \norm{f_{A}(x)}^{2} \geq (1 + \varepsilon) \norm{x}^{2} \right) & \leq & \exp \left( - \frac{k}{4} ( {\varepsilon}^{2} - {\varepsilon}^{3} ) \right) \\ Pr\left( \norm{f_{A}(x)}^{2} \leq (1 + \varepsilon) \norm{x}^{2} \right) & \geq & \exp \left( - \frac{k}{4} ( {\varepsilon}^{2} - {\varepsilon}^{3} ) \right) \end{eqnarray} $$

が成り立つ．よって，JL-補題をみたす写像 $f$ が構成された．