我们希望将一个集合中的高维的点转化为较低维度的点. JL 方法希望我们这个降维是尽可能保距的. 即希望 \(||f(x)-f(y)||^2\in(1\pm \epsilon)||x-y||^2\).
令 \(m\) 表示最终的维度，则 JL 方法有 \(m=O(\epsilon^{-2}\log n)\).
我们先看如果仅考虑两个点 \(x,y\) 有距离 \(v=x-y\)，我们可以有一个线性的随机映射 \(g:R^d\to R\) 且 \(E[g(v)^2]=g(v)\). 那么我们取多组 \(g\) 作为多个维度就能尽量减少误差.
方法就是取一个每个维度都采自高斯分布 \(N(0,1)\) 的 \(r\) 维向量 \(z\)，然后做内积. 注意到这个和 Simhash 有所区别：Simhash 中要求 \(z\) 为单位方向向量（因为要做投影），而这个则是每个维度采样自 \(N(0,1)\).
\(N(0,1)\) 变量的性质是平方的期望为 \(1\)，所以 \(E[g(v)^2]=\sum_i v_i^2E[w_i^2]=\sum v_i^2=g(v)\). 所以 \((v\mid w)^2\) 为 \(||v||^2\) 的无偏估计.
然后我们再取 \(m\) 个这样的随机映射 \(g_i(x)=(z_i\mid x)\)，然后最后令降维映射 \(f(x)=\frac{1}{\sqrt{m}}(g_1(x),g_2(x),\dots,g_m(x))\). 这样得到的 \(f\) 就是我们得到的一个期望下保距的降维映射.
JL 降维有一个比较复杂的误差分析. 我不会. 并且 JL 降维的这个 \(O(\log n)\) 的界是紧的，不存在更优的保距的降维方法.
JL 降维有一个好处，就是 Data Oblivious. 我们只需要事先生成 \(m\) 个 \(d\) 维的 \(z_i\)，即可对于任意 \(d\) 维输入向量进行降维！这在数据流中就很好.
一个小简化：可以令 \(z_i\) 的每个维度为 \([-1,1]\) 的随机值. 这符合我们上面对于 \(E[g(v)^2]\) 的分析.
现在我们将其应用至 Linear Regression 上.
Linear Regression 要解决的问题是，有一个 \(n\times d\) 的矩阵 \(X\) 和 \(n\) 维向量 \(Y\)，然后我们希望找到一个 \(d\) 维度的向量 \(w\)，最小化 \(||Xw-Y||_2\).
这个典型问题的最优解是 \(w=(X^{T}X)^{-1}X^{T}y\). 当然 \(X^TX\) 不满秩的时候会求逆的时候加上 \(\epsilon\times id\) 来近似求解广义逆. 但是对于 \(n>d\) 的大多数随机情况，这个大抵是满秩的. 我们的计算复杂度是计算矩阵乘法的 \(O(nd^2)\).
但是大多数情况下 \(n\) 太大了，而且 \(X\) 很稀疏，也有很多重复表达的数据. 也就是说我们要对 \(n\) 这一个维进行降维. 并且由于最小化的是距离，所以我们希望降维是保距的.
那么我们的 JL 降维相当于一个 \(m\times n\) 的矩阵 \(A\)，然后将由 \(n\) 个行向量组成的 \(n\times d\) 的矩阵 \(X\) 变成 \(m\times d\) 的 \(AX\). 最终 \(m\) 应该可以和 \(O(d\text{ poly}\epsilon^{-1})\) 同阶. 这个矩阵乘法需要 \(nd^2\) 次乘法. 这并没有优化复杂度. 但是后续的复杂度变成了 \(O(d^3)\).
我们现在考虑优化降维这一步骤的复杂度. 一个外星人的神秘做法：令 \(A\) 为每列仅有一个元素（并随机取为 \(\pm 1\)）的矩阵，那么我们可以发现前面的那个无偏估计的证明还是适用的. 但唯一的区别是 \(m\) 需要取 \(O(\epsilon^{-2}d^2\text{polylog}(\epsilon^{-1}d))\) 才能保证 Linear Regression 的结果适用.
取 \(A\) 为这样的矩阵之后，我们实际上就只需要遍历每个 \(X\) 中有值的元素 \(X_{i,j}\)，然后令 \(A\) 中第 \(i\) 列有值的行为 \(p\)，则贡献到 \((AX)_{p,j}\). 这个复杂度是 \(O(nnz(X))\)，其中 \(nnz\) 为非零值个数. 由于 \(m\) 变大，最后复杂度为 \(O(md^2)=O(d^4)\). 实际测试下来 \(d^2\) 是远不需要的.
Trick：矩阵乘法 \(a_{i,j}\leftarrow b_{i,k}c_{k,j}\) 的循环顺序应该是 \(k,i,j\)，这样对 Cache 比较友好.