Gaussian 行列版で JL 補題を証明します。
証明の骨格は
- 固定ベクトル $z$ について、ランダム写像後の長さが $\chi^2$ 分布で制御できる
- その tail bound を Chernoff 法で計算する
- 点集合の全ペアに union bound をかける
の 3 段です。
JL の標準的な定式化と、Dasgupta–Gupta の明示的な次元条件
k \ge 4(\varepsilon^2/2-\varepsilon^3/3)^{-1}\ln n
は文献で与えられています。Gaussian 行列で
$|f(z)|_2^2/|z|_2^2 \sim \chi_k^2/k$
になることも標準的です。(Computer Science)
1. 証明したい命題
$x_1,\dots,x_n\in\mathbb R^d$ を任意の点集合とし、
$G\in\mathbb R^{k\times d}$ の各成分を独立に $N(0,1)$ とします。写像
f(x):=\frac{1}{\sqrt{k}}Gx
を考えます。
示したいのは、適切な $k$ に対して高確率で
(1-\varepsilon)|x_i-x_j|_2^2
\le
|f(x_i)-f(x_j)|_2^2
\le
(1+\varepsilon)|x_i-x_j|_2^2
\quad(\forall i,j)
が同時に成り立つことです。これは JL 補題の Gaussian 版です。(Computer Science)
2. 固定ベクトル 1 本に対する補題
まず、任意の固定ベクトル $z\in\mathbb R^d$ に対して
\Pr!\left(
(1-\varepsilon)|z|_2^2\le |f(z)|_2^2 \le (1+\varepsilon)|z|_2^2
\right)
を評価します。
2.1 分布の同定
$G$ の第 $r$ 行を $g_r^\top$ と書くと、
f(z)=\frac1{\sqrt{k}}
\begin{pmatrix}
\langle g_1,z\rangle\\
\vdots\\
\langle g_k,z\rangle
\end{pmatrix}.
ここで
Y_r:=\frac{\langle g_r,z\rangle}{|z|_2}
とおくと、$g_r$ の成分は独立な標準正規なので、$Y_r\sim N(0,1)$ です。さらに行どうしは独立なので
Y_1,\dots,Y_k \stackrel{\text{i.i.d.}}{\sim} N(0,1).
したがって
|f(z)|_2^2 = \frac1k\sum_{r=1}^k \langle g_r,z\rangle^2
= \frac{|z|_2^2}{k}\sum_{r=1}^k Y_r^2.
ゆえに
\frac{k|f(z)|_2^2}{|z|_2^2}
= \sum_{r=1}^k Y_r^2
\sim \chi_k^2.
つまり
\frac{|f(z)|_2^2}{|z|_2^2}\sim \frac1k\chi_k^2.
これが Gaussian 版の核心です。(cgi.di.uoa.gr)
3. 上側 tail の厳密計算
S:=\sum_{r=1}^k Y_r^2 \sim \chi_k^2
とおきます。すると
|f(z)|_2^2 = \frac{|z|_2^2}{k}S.
上側 tail
\Pr!\left(|f(z)|_2^2\ge (1+\varepsilon)|z|_2^2\right)
= \Pr(S\ge (1+\varepsilon)k)
を評価します。
3.1 Markov の不等式
任意の $\lambda\in(0,1/2)$ に対して
\Pr(S\ge (1+\varepsilon)k)
= \Pr\left(e^{\lambda S}\ge e^{\lambda(1+\varepsilon)k}\right)
\le
e^{-\lambda(1+\varepsilon)k}\,\mathbb E[e^{\lambda S}].
3.2 mgf の計算
$S=\sum_{r=1}^k Y_r^2$ かつ独立性より
\mathbb E[e^{\lambda S}] = \prod_{r=1}^k \mathbb E[e^{\lambda Y_r^2}].
標準正規 $Y\sim N(0,1)$ について
\mathbb E[e^{\lambda Y^2}] = (1-2\lambda)^{-1/2}\qquad (\lambda<1/2)
なので、
\mathbb E[e^{\lambda S}] = (1-2\lambda)^{-k/2}.
したがって
\Pr(S\ge (1+\varepsilon)k)
\le
\exp!\left(
-\lambda(1+\varepsilon)k - \frac{k}{2}\ln(1-2\lambda)
\right).
3.3 最適な $\lambda$ の選択
指数部を
\phi(\lambda)
:=
-\lambda(1+\varepsilon)-\frac12\ln(1-2\lambda)
とおくと
\phi'(\lambda)=-(1+\varepsilon)+\frac1{1-2\lambda}.
$\phi'(\lambda)=0$ を解くと
\frac1{1-2\lambda}=1+\varepsilon
\quad\Longrightarrow\quad
1-2\lambda=\frac1{1+\varepsilon}
なので
\lambda_*=\frac{\varepsilon}{2(1+\varepsilon)}.
これを代入すると
-\lambda_*(1+\varepsilon) = -\frac{\varepsilon}{2},
\qquad
1-2\lambda_*=\frac1{1+\varepsilon},
ゆえに
-\frac12\ln(1-2\lambda_*) = \frac12\ln(1+\varepsilon).
よって
\phi(\lambda_*)
= -\frac{\varepsilon}{2}+\frac12\ln(1+\varepsilon)
= -\frac12\bigl(\varepsilon-\ln(1+\varepsilon)\bigr).
したがって
\Pr(S\ge (1+\varepsilon)k)
\le
\exp!\left(
-\frac{k}{2}\bigl(\varepsilon-\ln(1+\varepsilon)\bigr)
\right).
さらに
\ln(1+\varepsilon)\le \varepsilon-\frac{\varepsilon^2}{2}+\frac{\varepsilon^3}{3}
\qquad(0<\varepsilon<1)
より
\varepsilon-\ln(1+\varepsilon)\ge \frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}.
したがって
\Pr(S\ge (1+\varepsilon)k)
\le
\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
すなわち
\Pr!\left(|f(z)|_2^2\ge (1+\varepsilon)|z|_2^2\right)
\le
\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
この形の tail bound は Gaussian JL の標準形です。(cgi.di.uoa.gr)
4. 下側 tail の厳密計算
次に
\Pr!\left(|f(z)|_2^2\le (1-\varepsilon)|z|_2^2\right)
= \Pr(S\le (1-\varepsilon)k)
を評価します。
4.1 再び Markov の不等式
今度は $\lambda>0$ として
\Pr(S\le (1-\varepsilon)k)
= \Pr!\left(e^{-\lambda S}\ge e^{-\lambda(1-\varepsilon)k}\right)
\le
e^{\lambda(1-\varepsilon)k}\,\mathbb E[e^{-\lambda S}].
4.2 mgf
独立性より
\mathbb E[e^{-\lambda S}] = \prod_{r=1}^k \mathbb E[e^{-\lambda Y_r^2}].
標準正規 $Y$ に対し
\mathbb E[e^{-\lambda Y^2}] = (1+2\lambda)^{-1/2},
よって
\mathbb E[e^{-\lambda S}] = (1+2\lambda)^{-k/2}.
したがって
\Pr(S\le (1-\varepsilon)k)
\le
\exp!\left(
\lambda(1-\varepsilon)k - \frac{k}{2}\ln(1+2\lambda)
\right).
4.3 最適化
指数部を
\psi(\lambda):=\lambda(1-\varepsilon)-\frac12\ln(1+2\lambda)
とおくと
\psi'(\lambda)=(1-\varepsilon)-\frac1{1+2\lambda}.
$\psi'(\lambda)=0$ を解くと
1+2\lambda=\frac1{1-\varepsilon}
\quad\Longrightarrow\quad
\lambda_*=\frac{\varepsilon}{2(1-\varepsilon)}.
代入すると
\lambda_*(1-\varepsilon)=\frac{\varepsilon}{2},
\qquad
1+2\lambda_*=\frac1{1-\varepsilon},
なので
-\frac12\ln(1+2\lambda_*) = \frac12\ln(1-\varepsilon).
よって
\psi(\lambda_*)
= \frac{\varepsilon}{2}+\frac12\ln(1-\varepsilon)
= -\frac12\bigl(-\varepsilon-\ln(1-\varepsilon)\bigr).
したがって
\Pr(S\le (1-\varepsilon)k)
\le
\exp!\left(
-\frac{k}{2}\bigl(-\varepsilon-\ln(1-\varepsilon)\bigr)
\right).
ここで
-\ln(1-\varepsilon)=\varepsilon+\frac{\varepsilon^2}{2}+\frac{\varepsilon^3}{3}+\cdots
なので
-\varepsilon-\ln(1-\varepsilon)
= \frac{\varepsilon^2}{2}+\frac{\varepsilon^3}{3}+\cdots
\ge
\frac{\varepsilon^2}{2}.
特に
-\varepsilon-\ln(1-\varepsilon)\ge \frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}
も成り立つので、
\Pr(S\le (1-\varepsilon)k)
\le
\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
ゆえに
\Pr!\left(|f(z)|_2^2\le (1-\varepsilon)|z|_2^2\right)
\le
\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
5. 固定ベクトル版の結論
上側・下側を合わせると
\Pr!\left(\left||f(z)|_2^2-|z|_2^2\right| > \varepsilon|z|_2^2\right)
\le
2\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
すなわち、任意の固定 $z\neq 0$ について
\Pr!\left(
(1-\varepsilon)|z|_2^2
\le
|f(z)|_2^2
\le
(1+\varepsilon)|z|_2^2
\right)
\ge
1 - 2\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
これは Achlioptas が述べている Gaussian 行列版の tail bound と同じ形です。(cgi.di.uoa.gr)
6. 点集合全体への持ち上げ
いま、点集合 ${x_1,\dots,x_n}$ を固定します。
各ペア $(i,j)$ について
z_{ij}:=x_i-x_j
とおけば、
f(x_i)-f(x_j)=f(z_{ij})
です。
したがって、各固定ペアに対し
\Pr!\left(
(1-\varepsilon)|x_i-x_j|_2^2
\le
|f(x_i)-f(x_j)|_2^2
\le
(1+\varepsilon)|x_i-x_j|_2^2
\right)
は少なくとも
1-2\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right)
です。
ペアの個数は
\binom n2
なので、union bound から
\Pr(\text{どこかのペアで失敗})
\le
\binom n2\cdot
2\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right).
したがって右辺が 1 未満なら、成功確率は正であり、そのような $G$ は存在します。
たとえば
k \ge \frac{4\ln n}{\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}}
なら
2\exp!\left(
-\frac{k}{2}\left(\frac{\varepsilon^2}{2}-\frac{\varepsilon^3}{3}\right)
\right)
\le
\frac{2}{n^2},
よって
\Pr(\text{どこかのペアで失敗})
\le
\binom n2\frac{2}{n^2}
= \frac{n-1}{n}
<1.
ゆえに成功確率は正で、少なくとも 1 つは所望の写像が存在します。これで JL 補題が証明されました。
この明示的な $k$ の条件は Dasgupta–Gupta の定理と一致します。(Computer Science)
7. どこが本質だったか
この証明の要点は 2 つだけです。
まず、Gaussian 行列を使うと、固定ベクトル $z$ の像の二乗ノルムが
|f(z)|_2^2 = |z|_2^2\cdot \frac{1}{k}\chi_k^2
になることです。これで問題は $\chi^2$ 分布の濃度不等式に落ちます。(cgi.di.uoa.gr)
次に、距離保存したい対象は有限個の差分ベクトル
x_i-x_j
だけなので、固定ベクトル版の tail bound を全ペアに対して union bound でまとめれば終わりです。Dasgupta–Gupta の証明も本質的にこの構造です。(Computer Science)
8. もう一歩だけ補足
同じ証明は、Gaussian 以外にも Rademacher 行列やより一般の sub-Gaussian 行列へ拡張できます。ただし Gaussian の場合は
\langle g_r,z\rangle \sim N(0,|z|_2^2)
がぴったり成り立つため、$\chi^2$ に直接落ちて最も見通しがよいです。Gaussian 版は JL の入門としていちばんきれいです。(cgi.di.uoa.gr)