03.JL-Transformation.md

JL-Transformation

[toc]

Johnson-Lindenstrauss.

JL 引理

(Johnson-Lindenstrauss Lemma) 给定一个点集 $P\subset R^d$, $|P|=n$, 对 $\forall \epsilon\in(0,1)$, 令 $k=O(\frac{logn}{\epsilon^2})$, 存在一个线性变换 $f:R^d\rightarrow R^k$, s.t. $\forall u,v\in P$, $$(1-\epsilon)|u-v|^2\le|f(u)-f(v)|^2\le(1+\epsilon)|u-v|^2$$

构造 JL 变换的基本方法

令 $A\in R^{k\times d}$, A中每个元素服从 $\mathcal{N}(0,1)$, A 是个随机矩阵.

让 $f=\frac{1}{\sqrt{k}}A$, 称作 JL-Transform $A=\left[\begin{array}{c} A_1\A_2\\vdots\A_k \end{array}\right]$, $\forall A_j=[A_{j1},\cdots,A_{jd}]$

$\forall x\in R^d$, 考虑 $y=\frac{1}{\sqrt{k}}Ax$

性质证明

1. 期望不变: $\begin{aligned} E[|y|^2]&=\frac{1}{k}E[|Ax|^2]\ &=\frac{1}{k}\sum\limits_{j=1}^kE[(A_jx)^2]\ &=E\left[\sum\limits_{1\le i,i'\le d}A_{ji}A_{ji'}x_ix_{i'}\right]\ &=E\left[\sum\limits_{i=1}^dA_{ji}^2x_i^2\right]\ &=\sum\limits_{i=1}^dx_i^2=|x|^2 \end{aligned}$
2. $Pr\left[|y|^2>(1+\epsilon)|x|^2\right]$ 的概率足够小: 定义$z_j=\frac{A_jx}{|x|}=\sum\limits_{i=1}^d\frac{A_{ji}x_i}{|x|}$, 则 $z_j\sim\mathcal{N}(0,1)$ $\begin{aligned} Pr\left[|y|^2>(1+\epsilon)|x|^2\right]&=Pr\left[\frac{|Ax|^2}{|x|^2}>(1+\epsilon)k\right]\ &=Pr\left[\sum\limits_{j=1}^kz_j^2>(1+\epsilon)k\right]\ &=Pr\left[e^{\lambda\sum\limits_{j=1}^kz_j^2}>e^{(1+\epsilon)k\lambda}\right]\ &\le\frac{1}{e^{(1+\epsilon)k\lambda}}E[e^{\lambda\sum\limits_{j=1}^kz_j^2}] (Markov's)\ &=\frac{1}{e^{(1+\epsilon)k\lambda}}\prod\limits_{j=1}^kE[e^{\lambda z_j^2}]\ &=\frac{1}{e^{(1+\epsilon)k\lambda}}\left(\frac{1}{1-2\lambda}\right)^{k/2} (积分可得)\ (令\lambda=\frac{\epsilon}{2(1+\epsilon)})&=\left((1+\epsilon)e^{-\epsilon}\right)^{k/2}\ &\le e^{-k(\epsilon^2-\epsilon^3)/4} \end{aligned}$ 同理 $$Pr\left[|y|^2>(1+\epsilon)|x|^2\right]< e^{-k(\epsilon^2-\epsilon^3)/4}$$ 故 $$Pr\left[|y|^2\in (1\pm\epsilon)|x|^2\right]< 1-2e^{-k(\epsilon^2-\epsilon^3)/4}$$ 要同时让 $C_n^2$ 个向量满足这个不等式, 则 成功概率 $>1-2C_n^2e^{-k(\epsilon^2-\epsilon^3)/4}$, 试图使之$>1-1/n$

算法复杂度

矩阵乘法: $\Theta(ndk)=\Theta(nd\frac{logn}{\epsilon^2})$

实际应用中的构造方法

前面提到的正态分布采样方法是直接采用 $\mathcal{N}(0,1)$ 的分布采样来构造 A的, 得到的矩阵会很稠密, 我们希望能比较稀疏以减小计算代价.

Database-Friendly:

用 0-1矩阵 构造 $A\in \mathbb{R}^{k\times d}$. 有两种主要方法:

• $A_{ij}=\left{\begin{array}{ll}+1 & 1/2概率\-1 & 1/2 概率\end{array}\right.$
• $A_{ij}=\left{\begin{array}{ll}+1 & 1/6概率\0 & 2/3概率 \-1 & 1/6 概率\end{array}\right.$

该方法实际效果比较好, 运算时间也短.

Fast JL-Transform(FJLT)

构造投影矩阵 $\Phi=P\cdot H\cdot D$, 其中各个矩阵构造法如下:

• $P\in R^{k\times d}$, $P_{ij}=\left{\begin{array}{l}\mathcal{N}(0,1/q)\sim q\0 \sim 1-q \end{array}\right.$ 这里 $q=\min\left{\Theta(\frac{\log n^2}{d}),1\right}$
  • 这样能够保证 $P$ 的非零值有 $kdq=kd\Theta(\frac{\log n^2}{d})=\theta(k\log n^2)\ll kd$
• $H$ 是 Hadamard 矩阵, $H_1=[1]$, $H_2=\left[\begin{array}{cc}1&1\1&-1\end{array}\right]$,$\cdots$,$H_{2^h}=\left[\begin{array}{cc}H_{2^{h-1}}&H_{2^{h-1}}\H_{2^{h-1}}&-H_{2^{h-1}}\end{array}\right]$.
  • 计算 $H_{2^h}x$ 可以令 $x=\left[\begin{array}{c}x_1\x_2\end{array}\right]$, 从而 $$H_{2^h}x=\left[\begin{array}{c}H_{2^{h-1}}x_1+H_{2^{h-1}}x_2 \ H_{2^{h-1}}x_1-H_{2^{h-1}}x_2\end{array}\right]$$
  • 根据这样的算法, $\tau(d)=2\tau(d/2)+O(d)=O(d\log d)$
• $D=\left[\begin{array}{ccc}\pm 1&&0\&\ddots&\0&&\pm 1\end{array}\right]$, 其中$\pm1$ 的概率均为 $\frac{1}{2}$.

总复杂度: $O\left(n(d\log d+\frac{\log n^2}{d}\cdot k\cdot d)\right)=O\left(n(d\log d+\frac{\log n^2}{d}\cdot\frac{\log n}{\epsilon^2}\cdot d)\right)=O(n(d+\frac{1}{\epsilon^2}))$

Mailman Algorithm

考虑 $d$ 特别大, $d > 2^k$, $k=\Theta(\frac{\log n}{\epsilon^2})$. 可以构造:

• $U\in \mathbb{R}^{k\times 2^k}$ 包含了所有可能的 $\pm 1$ 列向量.
• 指示矩阵: $B \in {0, 1}^{2^k \times d}$, 每列只有一个 1, 指示该列是选择使用矩阵 $U$ 的哪一列.

则令 JL-Transformation 变换矩阵为 $A=U \cdot B$

做变换时, 先计算 $y=B\cdot x$, 然后计算 $U\cdot y$. 其中

• 计算 $B\cdot x$ 时, 由于只有 $d$ 个 $1$ 时间复杂度是 $\Theta(d)$,
• 计算 $U\cdot y$ 时, 按 $U$ 第一行为 $1$ 或为 $-1$ 分块为 $$U\cdot y= \left[\begin{array}{cc} 1 & -1 \ U_{k-1} & U_{k-1} \ \end{array}\right] \cdot \left[\begin{array}{c} y_{1} \ y_{2} \ \end{array}\right] = \left[\begin{array}{c} 1\cdot(y_1-y_2) \ U_{k-1}\cdot(y_1+y_2) \ \end{array}\right]
  $$

时间复杂度分析

• 构造 $U, B$ 的时间: $\Theta(k\cdot 2^k) + \Theta(d) + \Theta(k\cdot d)$
• 求 $y=B\cdot x$, $B$ 中只有 $d$ 个为 $1$, 故时间是 $\Theta(d)$
• 求 $U\cdot y$ 时, 时间复杂度满足 $T_k=\Theta(2^k) + \Theta(2^k) + T_{k-1}$, 从而知其为 $\Theta(2^k)$

因此变换的复杂度是 $Time(A\cdot x) = \Theta(d) + \Theta(2^k)=\Theta(d)$

总复杂度是 $\Theta(k\cdot 2^k) + \Theta(d) + \Theta(k\cdot d) + \Theta(n\cdot d)=\Theta((k+n)d)$

应用

• 分布式计算: 相同随机种子能生成相同矩阵
• 流数据:
• 隐私保护: 微小偏移

快速计算内积

可以令 $P=\left{ \left. \pm\frac{v_i}{|v_i|}, \pm\frac{u_j}{|u_j|} \right| 1\le i\le n, 1\le j\le m\right} \cup {0}$, 显然$|P|=2(n+m)+1=\Theta(n+m)$

向量内积的近似情况

假设 $S$ 是 $P$ 的 JL-Transformation. $\forall v_i, u_j$, 令 $a=|v_i|_2\cdot|u_j|_2$, 则 $$ \begin{aligned} \left< sv_i, su_j \right> &= \frac{a}{4}\left(\left|S\cdot\frac{v_i}{|v_i|}+S\cdot\frac{u_j}{|u_j|}\right|^2-\left|S\cdot\frac{v_i}{|v_i|}-S\cdot\frac{u_j}{|u_j|}\right|^2\right) \ &\le \frac{a}{4}\left((1+\epsilon)\left|\frac{v_i}{|v_i|}+\frac{u_j}{|u_j|}\right|^2-(1-\epsilon)\left|\frac{v_i}{|v_i|}-\frac{u_j}{|u_j|}\right|^2\right) \ &=\frac{a}{4}\left(4\cdot\left<\frac{v_i}{|v_i|},\frac{u_j}{|u_j|}\right> + \epsilon\left(\left|\frac{v_i}{|v_i|}+\frac{u_j}{|u_j|}\right|^2+\left|\frac{v_i}{|v_i|}-\frac{u_j}{|u_j|}\right|^2\right)\right) \ &=\frac{a}{4}\left(4\cdot\left<\frac{v_i}{|v_i|},\frac{u_j}{|u_j|}\right> + 2\epsilon\left(\left(\frac{v_i}{|v_i|}\right)^2+\left(\frac{u_j}{|u_j|}\right)^2\right)\right) \ &=\left< v_i, u_j \right> + \epsilon\cdot|v_i|\cdot|u_j| \end{aligned} $$

同理可得另一边. 故 $$\left&lt; v_i,u_j \right&gt; - \epsilon|v_i|\cdot|u_j| \le \left&lt; S\cdot v_i, S\cdot u_j \right&gt; \le \left&lt; v_i,u_j \right&gt; + \epsilon|v_i|\cdot|u_j|$$

矩阵内积

综上, 可以这样做矩阵内积: $$A\cdot B\Rightarrow (A\cdot S^T)\cdot(S\cdot B)$$

这样可以保证: $$|A\cdot B - (A\cdot S^T)\cdot(S\cdot B)|_F \le \epsilon\cdot |A|_F\cdot |B|_F$$

线性回归

Definition of Linear Regression

给定 $n$ 个数据, 每个形如 $(x_{i1}, x_{i2}, \cdots, x_{id}, y_i)$, 要求解线性方程 $y=\beta_1x_1+\beta_2x_2+\cdots+\beta_dx_d$(的系数), 目标是 $\mathtt{minimize} \sum\limits_{i=1}^n|\sum\limits_{j=1}^d\beta_j\cdot x_{ij} - y_i|^2$

记 $A= \left[\begin{array}{ccc} x_{11} & \cdots & x_{1d} \ \vdots & & \vdots \ x_{n1} & \cdots & x_{nd} \end{array}\right]$, $b= \left[\begin{array}{c} y_{1} \ \vdots \ x_{n} \end{array}\right]$

则目标可记为 $|A\beta - b|^2$, 故可以求出 $\beta_{opt}=(A^T A)^{-1}A^Tb$

注: 证明如下, $令 \frac{\partial |A\beta-b|^2}{\partial \beta} =\frac{\partial (A\beta-b)^T(A\beta - b)}{\partial \beta} =\frac{\partial \beta^TA^TA\beta + b^Tb-2b^TA\beta}{\partial \beta} =2A^TA\beta - 2A^Tb=0$ 可得 $\beta_{opt}=(A^TA)^{-1}A^Tb$

Sparse Regression

上面是比较标准的解法. 但如果 $n\gg d$, 可以考虑稀疏回归——把 $A\in \mathbb{R}^{n\times d}$ 看成 $R^n$ 中的 $d$ 个向量.

考虑 $k$ 维网格 $[-1,1]^k$, 其性质有:

• 网格间距 (side length) = $\frac{\epsilon}{k}$
• \sharp of 格点: $\left(\frac{2}{\epsilon / k}\right)^k=\Theta\left(\left(\frac{2k}{\epsilon}\right)^k\right)$
• 同一个细胞内任意两点间距 $\le \sqrt{\left(k\frac{\epsilon}{k}\right)^2}=\frac{\epsilon}{\sqrt{k}}$
• 若对所有格点作 JL-Transformation: $R^n \rightarrow R^{\Theta\left(\frac{1}{\epsilon^2}\cdot k\log\frac{k}{\epsilon}\right)}$
• 对单位球上的点 $u$: $u=g+\sum\limits_{l=1}^k e_i\epsilon_i, 0\le \epsilon_i\le \frac{\epsilon}{k}$, 其中 $e_{i}$ 张成网格决定的直角坐标系, $\epsilon_i \in \left[0,\frac{\epsilon}{k}\right]$, $g$ 是 $u$ 所在网格左下角点.

依据这些, 可以估计单位球上点 $u$ 的近似情况: $$\begin{aligned} |S\cdot u|2 &= \left|S\cdot (g + \sum\limits{i=1}^ke_i \epsilon_i)\right|_2\ &\le \left|S\cdot g\right|2 + \left|S\cdot\sum\limits{i=1}^ke_i \epsilon_i\right|_2 \ &\le \sqrt{1+\epsilon}\cdot |g|2 + \sum\limits{i=1}^k\epsilon_i|S\cdot e_i|_2 \ &\le \sqrt{1+\epsilon} |g|2 + \sum\limits{i=1}^k\epsilon_i\cdot \sqrt{1+\epsilon} \ &\le \sqrt{1+\epsilon} |g|2 + \sum\limits{i=1}^k\frac{\epsilon}{k}\cdot \sqrt{1+\epsilon} \ &= \sqrt{1+\epsilon} |g|_2 + \epsilon\cdot \sqrt{1+\epsilon} \ &\le \sqrt{1+\epsilon} (|u|_2+\epsilon/\sqrt{k}) + \epsilon\cdot \sqrt{1+\epsilon} \ &=\sqrt{1+\epsilon}(1+\epsilon/\sqrt{k}+\epsilon) \end{aligned}$$

因此 $$(1-\Theta(\epsilon))\cdot |u|_2^2 \le |S\cdot u|_2^2 \le (1+\Theta(\epsilon))\cdot |u|_2^2$$

如果用这样的方法进行 JL-Transformation, 假设原空间是 $F=span{A}$, 最优解值是 $u_{opt}=A\beta_{opt}$, 变换后是 $\widetilde{F}=span{S\cdot A}$. $\widetilde{\beta}_{opt}$ 是关于 $SA, Sb$ 的最优解.

$\widetilde{u}{opt}=SA\widetilde{\beta}{opt}$, 变换回去得到的是 $\widetilde{u}{opt}^{-1}=A\widetilde{\beta}{opt}$.

则有:

• $(1-\epsilon)|b-\widetilde{u}_{opt}^{-1}|2^2 \le |Sb-\widetilde{u}{opt}|_2^2$
• $|Sb-\widetilde{u}_{opt}|2^2 \le |Sb-Su{opt}|_2^2$
• $|Sb-Su_{opt}|2^2 \le (1+\epsilon)|b-u{opt}|_2^2$

综上三式得到: $$|b-\widetilde{u}_{opt}^{-1}|2^2 \le \frac{1+\epsilon}{1-\epsilon}|b-u{opt}|_2^2$$

压缩感知

原始信号 $x\in \mathbb{R}^d$ 经过 $A\cdot x$ 得到 $y$ 传给接收方. $y=A\cdot x\in \mathbb{R}^m$, 这里 $m\ll d$. 这里

• $A$ 满足 Restricted Isometry Property, 即 $|y|_2^2 \in (1\pm \epsilon)|x|_2^2$,
• $x$ 是一个 k-sparse 向量, 只有 $k$ 个非零元素, $k\ll d$. 所有 k-sparse 向量由 $C_k^d$ 个 k 维子空间组成.

总格点数为 $\Theta((\frac{2k}{\epsilon})^k\cdot d^k)=N$, 降维后维度为 $m=\Theta(\frac{\log N}{\epsilon^2}) = \Theta\left(\frac{1}{\epsilon^2}k\left(\log \frac{2k}{\epsilon}+\log d \right)\right)$