Johnson-Lindenstrauss Transform
给定误差 $\varepsilon$，JL是映射 $f:\mathbb{R}^d \to \mathbb{R}^m, m=O\left(\varepsilon^{-2}\log n\right)$
使得：
$$
\forall x, y\in P, \Vert f(x) - f(y)\Vert_2\in (1\pm \varepsilon) \cdot \Vert x - y\Vert_2
$$
具体地，取 $\mathbb{R}^d$ 上随机向量 $w$，其每一维均为独立的 $N(0, 1)$，取 $g(v):=\langle v, w\rangle$
有 $E(g^2(v)) = \sum_{i}v_i^2E(w_i^2)=\Vert v\Vert_2^2$
通过多个 $g$ 拼接即可得到：
$$
f(v) := \frac{1}{\sqrt{m}}(\langle w_1, v\rangle,\langle w_2, v\rangle, \cdots, \langle w_m, v\rangle)
$$
显然 $E(\Vert f(v)\Vert_2^2) = \Vert v\Vert_2^2$
下面给出结论：
$$
\mathbf{Pr}\left(\Vert f(v)\Vert_2^2 \in (1\pm \varepsilon) \cdot \Vert v\Vert_2^2\right) \ge 1-\exp(-O(\varepsilon^2m))
$$
据此及 Union bound 可得出：$m=O\left(\varepsilon^{-2}\log n\right)$
Linear Regression
一般求解
设输入为：$(x_1, y_1),(x_2, y_2), \cdots,(x_n, y_n)$
设 $X \in \mathbb{R}^{n \times d} = {x_i}, y = {y_i}$
求 $\arg \min_{w\in\mathbb{R}^d} \Vert Xw - y\Vert$
则最优 $w^{*} = (X^TX)^{-1}X^Ty$
此时复杂度：$O(nd^2+d^3)$
降维
降维需要保证：对所有 $w \in \mathbb{R}^d, \Vert AXw - Ay\Vert^2$ 误差在 $\varepsilon$ 以内。
朴素的 $m=O\left(\varepsilon^{-2}\log n\right)$ 此时需要 $m\to \infty$
考虑特殊性：$w$ 是 $d$ 维，因此所有要考虑的 $Xw - y$ 仅在一 $d$ 维子空间 $\mathcal{U}$ 中。
有结论：$m=O\left(\frac{d\log(\epsilon^{-1})+\log(1/\delta)}{\epsilon^2}\right)$ 在 $\mathcal{U}$ 上成立。
但此时求 $AX$ 仍需 $O(nd^2)$
优化
若有 $X$ 稀疏，记 $\operatorname{nnz}(X)$ 为非 0 元素数，则有 $O(\operatorname{nnz}(X))$ 求 $AX$：
限定 $A$ 为每一列仅有一个均匀随机位置非 0，且均匀取 ${1,-1}$
对于 $m=O(\varepsilon^{-2}d^2\cdot\operatorname{poly}\log(\varepsilon^{-1}d))$ 有相应误差保证。
设 $A$ 的第 $i$ 列只有第 $\pi(i)$ 行非 0，此时求 $AX$ 只需扫描 $X$ 的非 0 项 $x_{i, j}$，令 $m_{\pi(i), j} += x_{i,j}$
此时由于 $m=O(d^2)$，此时复杂度为 $O(d^4 + \operatorname{nnz}(X))$