程设笔记

主讲内容：近似算法 / 随机算法，中间会插入 oop 部分。 ## Intro

有关近似的概念

相对误差的近似：

\(\alpha\) 近似：\(output \leq \alpha \cdot ans\) 的算法

\((1+\varepsilon)\) 近似：\(output \leq (1+\varepsilon) \cdot ans\) 的算法，算法的复杂度为 \(O(f(\frac{1}{\varepsilon}))\)，这里通常 \(\varepsilon \in [0.01,0.3]\)

有关随机的概念

随机有两种：

1. 蒙特卡洛式：性能较高，但是有一定出错率。
2. 拉斯维加斯式：正确性有保证，随机性与效率有关。

常见领域

1. 工程领域的近似场景
2. 高并发场景
3. 大数据处理
4. 数据流的 时 / 空 亚线性算法
5. 数据科学：如与 AI 有关的聚类 / 回归

分析：数学基础

Markov 不等式 :

若随机变量 \(X \ge 0\)，则 \[ \Pr[X \ge a] \leq \dfrac{\mathbb{E}[X]}{a} \] 用于最优化问题的概率分析。

Chernoff Bound:

若 \(X_1 \sim X_n \in [0,1]\) 为独立随机变量，\(X=\sum X_i\)，则 \[ \forall t\in[0,1],\Pr[|X-\mu|\ge t\mu]\leq 2\exp(-t^2\mu/3) \] Hoeffding 不等式：

设独立随机变量 \(X_1\sim X_n\in[a,b]\)，\(X = \sum X_i\)，则： \[ \Pr[X-\mathbb{E}[X]\ge t] \leq 2\exp(-\frac{2t^2}{n(b-a)^2}) \]

代码基础

随机发生器

1. 系统真随机，如 /dev/urandom，算法中不推荐，在生成密钥时可能可用
2. minstd_rand，一个折中的选择
3. Mersenne Twister: std::mt19937() from <random>，快
4. Lagged Fibonacci: std::ranlux24, ranlux48，有很好的随机性

随机分布

1. 整数均匀：uniform_int_distribution <int> (l, r)
2. 实数均匀：uniform_real_distribution <> (l, r)
3. 离散分布：std::discrete_distribution <> d({1.5, 1.5, 1.5, 3.0})
4. bernoulli 分布：std::bernoulli_distribution d(0.25)

hash 函数

#define mix(h) ({					\
			(h) ^= (h) >> 23;		\
			(h) *= 0x2127599bf4325c37ULL;	\
			(h) ^= (h) >> 47; })
u64 fasthash64(u64 v) {
	const uint64_t m = 0x880355f21e6d1965ULL;
	u64 h = seed;
	h ^= mix(v);
	h *= m;
	return mix(h);
}

经典算法

最大割问题

描述：

\(\mathtt{input}: G = (V,E)\)

\(\mathtt{output}: \arg \max\{\text{cut}(S) = \sum_{u\in S, v\in V\backslash S} w(u,v) \mid S \subseteq V\}\)

这里，\(w(u,v) = 1\)，即割为一个边集。

近似算法：\(T\) 轮，随机生成一个 \(S\): 考虑每一个点 \(u \in V\)，有 \(50\%\) 的概率放入 \(S\) 中

分析：

1. 一个弱的期望分析：\(\mathbb{E}[\text{cut}(S)] = \sum \Pr[(u,v) \in \text{cut}(S)] \ge 0.5|E|\)，这里 \(E\) 为最优解。

2. 达到 \(0.5-\epsilon\) 近似的概率：

   由 Markov 不等式，\(\Pr[\text{cut}(S) < (0.5 -\epsilon) E] \leq \frac{0.5\mathbb{E}[\text{cut}(S)]}{(0.5 - \epsilon)E}\)

   \(T\) 取 \(\frac{\log (1/\delta)}{\epsilon}\)，\(\delta\) 为失败概率。

3. 复杂度为 \(O(Tm)\)。

矩阵乘法校验

描述：

\(\mathtt{input}: A \in M_{n \times m}(\mathbb{R}),B \in M_{m\times k}(\mathbb{R}),C\in M_{n\times k}(\mathbb{R})\)

\(\mathtt{output}: [A \cdot B = C]\)

近似算法：\(T\) 轮，每次随机一个向量 \(x\)，比较 \(ABx = Cx\)，\(T\) 轮都相同认为相等。

分析：

1. 如果 \(x_i\in \{0,1\}\)，一轮出错的概率 \(\leq 0.5\)。
2. 复杂度为 \(O(T(nm + mk + nk))\)。

蒙特卡洛估计积分

描述：

\(\mathtt{input}: f:[0,1] \to [0,1]\)。

\(\mathtt{output}: M:=\int_0^1 f(x)\ \mathrm{d}x\)，要求 \(|\hat M - M| \leq \epsilon\)。

近似算法： 多次随机选点 \(x_i\)，输出 \(f(x_i)\) 的平均值。

1. \(\displaystyle \mathbb{E}[f(X)] = \int_0^1 f(x)\ \mathrm{d}x\)
2. 由 Hoeffding 不等式可以确定 \(T= O(\epsilon^{-2} \log (1/\delta))\)

*平面图近似 TSP

思想：存在一个结构简单的平面结构 \(\text{STSP}\) 是 \((1+\epsilon)\) 近似的，通过 dp 找到这样的 \(\text{STSP}\)。

详询：Arora, 1998

分布式快排

假设每台机器存储 \(s=O(\sqrt n)\) 的数据。

快排过程：

1. 一号机器生成 \(\sqrt n\) 个随机 pivot （即键值），广播给所有机器。
2. 每一台机器对于自己的数据进行分类，然后分发给其他机器。
3. 每台机器收到数据后，进行本地排序。

*平面图的 Balanced Separator

Mikkel Thorup, JACM 04

用 \(O(\sqrt n)\) 条水平 / 竖直的线将平面图分割，是的任意两点间的最短路仅跨过 \(O(1)\) 个 Separator。

负载均衡

将 \(n\) 个文件分配个 \(m\) 台服务器，需要支持 \(m\leftarrow m + 1\)。

1. 若 \(m\) 不变，采用随机 hash：

   理想随机 hash: \(h: [n] \to [m]\), s.t \(\Pr[h(i)=h(j)] = 1 \leq m\)。

2. 若 \(m\) 改变，采用 Consistent Hashing:

   将文件和服务器都 hash 映射到 \([M]\)，并且将 \([M]\) 看成一个 \(M\) 元环（\(M\) 足够大）。

   文件分配：文件 \(file\) 找到 \(h(file)\) 在环上最近的后继 \(h(server)\)，交给 \(server\)。

   新增服务器：新增服务器之后需要移动 \(O(n/m)\) 个文件。

   用数据结构维护即可。

数据流近似 Point Query

描述：先给定数据流 \(a_1,a_2,\cdots,a_N\in [n]\)，随后查询某个数出现的次数 \(C\)，要求空间较小。

近似算法 Count-min：

算法目标：概率求出 \(\hat C\), s.t. \(C\leq \hat C \leq C+\epsilon \cdot N\)，使用 \(O(\text{poly}\log n /\epsilon)\) 的时空。

大致算法：采用一个随机 hash: \(h : [n] \to [m]\)，用 \(m\) 个桶存下来。存储多个这样的随机 hash 和桶，取最小值。

概率分析：

\(\begin{aligned}\mathbb{E}[C(h(x)] &= \mathbb{E}[C_x+\sum_{y \ne x} [h(y)=h(x)]\cdot C_y] \\&= C_x + \sum_{y\ne x} \Pr[h(y)=h(x)]\cdot C_y\\ &\leq C_x + N / m \end{aligned}\)

再利用 Markov 不等式：

\(\Pr[C(h(x)) -C_x > \epsilon \cdot N] \leq \dfrac{\mathbb{E}[C(h(x))-C_x]}{\epsilon \cdot N}=\dfrac{N/m}{\epsilon \cdot N}\leq \dfrac{1}{\epsilon \cdot m}\)

取 \(m=2/\epsilon\)，得到一个 \(50\%\) 概率的算法 \(1+\epsilon\) 近似算法。

由于需要存多个桶，最终时空复杂度为 \(O(Tm)=O(\log(1/\delta)\cdot (2/\epsilon))\)

数据流近似 Heavy Hitter

k-Heavy Hitter：

输出数据流中出现次数超过 \(N/k\) 的元素。

要求：

1. 空间较小。
2. 出现 \(N/k\) 的元素必须找出。
3. 所有被找出的元素出现次数 \(\ge N/k-\epsilon N\)。
4. \(N\) 在接收数据流时未知

算法：使用 count-min 维护次数，此外，再维护一个表存储出现次数超过当前 \(N/k\) 的元素，在插入时修改。

数据流精确 Majority

Majority: 出现次数超过一半的元素。

算法1：若 \(x\) 出现超过一半，则 \(x\) 的每一个 \(0/1\) 位都出现超过一半，支持加 / 删。

算法2：

1. 初始化 count = 0, current = NULL
2. 一次考虑 \(a_i\)
3. 若 counter = 0，设置 current = \(a_i\)
4. 若 current = \(a_i\), counter 加，否则减。

以上两个算法值只能在确定 Majority 存在的情况下使用。

*Bloom Filter

描述：

维护集合 \(S\)，支持插入，删除，值域 \(S\) 可能为字符串

询问一个元素是否在集合中，要求漏过一个元素的概率 \(\leq \delta\)。

算法：

维护 \(m\) 个桶，\(T\) 个随机 hash 函数 \(h^i:S\to [m]\)。

桶维护 \(h^j(a_i)\) 的次数，插入删除时修改 \(T\) 个位置。

查询：所有 \(h^{i}(x)\) 的位置都 \(>0\) 就返回 Yes。

分析：

1. 考虑其余 \(n\) 个数冲突覆盖掉所有 \(h^i(x)\) 的概率，即 \((1-(1-1/m)^{Tn})^T \approx (1-\exp(-nT/m))^T\)
2. 若 \(m,n\) 固定，则取 \(T = \frac{m}{n}\ln 2\)
3. 若要求失败概率 \(\delta\)，则 \(m = \frac{n\ln \delta^{-1}}{\ln ^2 2}, T= \log_2(\delta^{-1})\)

空间是线性的，若没有删除操作，可以将桶换成 bitset。

集合的 Jaccard Similarity 近似

\(J(A,B) = \dfrac{|A\cap B|}{|A\cup B|}\)

描述：给定多个集合 \(S_i\)，多个查询 \(J(S_{p_i},S_{q_i})\)。

算法 MinHash：

取 hash 函数 \(h:[n] \to [0,1]\) 或者一个足够大的整数域。

Claim：\(\Pr[\min\{h(A_i)\} = \min\{h(B_i)\}]=J(A,B)\)

Proof：

\(\min\{h(A),h(B)\}\) 一定是集合 \(A\cup B\) 中随机选出的一个，

仅当恰好选到 \(A\cap B\) 时，\(\min\{h(A_i)\}=\min\{h(B_i)\}\)

取 \(T\) 个 hash 函数，求出概率即可。

由 Chernoff bound，\(T=O(\log n)\) 时，失败概率为 \(1/\text{poly}(n)\)

*向量的 Cosine Similarity 近似

\(x,y \in \mathbb{R}^d, \sigma(x,y) = \dfrac{x \cdot y}{\|x\|_2\cdot \|y\|_2} = \cos \langle x,y\rangle\)

算法：

生成一个随机向量 \(w\)（这里需要在 \(d\) 位单位球的表面随机选择一个点，生成方式为生成 \(d\) 个正态变量，随后放到球面，wiki）。

使用 hash 函数 \(h(x)=[w \cdot x\ge 0]\)

Claim：\(\Pr[h(x) \ne h(y)] = \sigma(x,y)\)

注：使用该 hash 函数后，\(T\) 个输出结果组成了一个 \(T\) 位二进制数。

Hamming 空间最近点近似算法

Hamming 空间：\(\mathbb{H}^d\)，即 \(d\) 位二进制数，\(dis(x,y)=\text{popcount}(x\oplus y)\)。

描述：给定一组点和若干最近点查询，要求 \((1+\epsilon)\) 近似。

算法：\(T\) 次，用随机排列 \(\sigma_i\) 映射二进制位，对于映射完的数 \(a_i\) 取字典序最近的 \(c\) 个更新答案。

复杂度：\(O(T n(\log n+c))\)。

参数选择：\(T=O(n^{1/(1+\epsilon)})\)。

欧氏距离直径近似

描述：\(P_i\in \Delta^d, \Delta=[2^{32}]\) 或 \([0,10^9]\)，求 \(\max\{\text{dist}(P_i,P_j)\}\)

算法：

1. 求一个 \(2-\)近似直径 \(T (\frac{1}{2}\text{diam}\leq T \leq \text{diam})\)。
2. 以 \(\ell=\dfrac{\epsilon \cdot T}{\sqrt{d}}\) 的方格划分空间，将每个点放到最近的立方体顶点上。
3. 暴力枚举不同的点求距离

分析：

1. 误差分析：以长 \(\ell\) 的方格划分，每个点移动的距离不超过 \(\frac{1}{2}\sqrt{d} \ell\)，

   故求出直径的偏差不超过 \(2\sqrt{d}\ell = \epsilon T \leq \epsilon \cdot \text{diam}\)

2. 复杂度分析：直径 \(\text{diam}\leq 2T\)，故按照 \(\ell\) 划分时，每一维坐标的的差距不超过 \(\frac{2T}{\ell}=2\sqrt{d}/\epsilon\)，

   总划分后点数上界为 \(O((2\sqrt{d}/\epsilon)^d)=O(\epsilon^{-O(d)})\)

   总复杂度为 \(O(n+\epsilon^{-O(d)})\)

注：直接划分到方格的左下角，虽然每个点都移动了 \(\sqrt{d}\ell\)，但是总体偏差依然正确（可以在移动之后给 \(x,y\) 都加上 \(\frac{1}{2}\ell\) 移动到方格中心）

欧氏空间最小包围球近似

描述：\(P_i\in \mathbb{R}^d\)，求 \(C\in \mathbb{R}^d\)，最小化 \(f(P,c) = \max\{\text{dist}(P_i,c)\}\)

\(\epsilon-\)Coreset：找到 \(S\subseteq P\)，使得 \(\forall c, f(S,c) \ge (1-\epsilon)f(P,c)\) （近似凸包）

算法：

1. 用 \(O(n)\) 的时间找一个 \(2\) 近似的值 \(T\) （\(f(P,c) \leq T \leq 2f(P,c)\) ）

2. 作 \(\ell=\dfrac{\epsilon}{2\sqrt{d}}\cdot T\) 的网格，并 round 点集 \(P\) 得到新点集 \(P'\)

   （也可以找到 \(P'\) 在原 \(P\) 上对应的一组点）

并行算法：修改 \(\epsilon\)，做分治合并，每次合并之后再求 coreset。

数据流算法：依次接收每个数据点，维护分治合并路径上的一组点（类似二进制分组）。

四分树

\(\mathtt{input}: P_i \in \Delta^d\)。

建树：

\(\mathtt{Build}(S, \square)\): 当前点集为 \(S\)，对应着立方体 \(\square\)。

1. 若 \(S=\emptyset\)，返回 NULL。
2. 新建节点 \(u\)
3. 若 $|S|=$1，返回 \(u\)。
4. 将 \(\square\) 的每一维按中点划分，划分为 \(2^d\) 个矩形 \(\square_i\)。
5. \(u.son_i=\mathtt{Build}(S\cap \square_i, \square_i)\)

树有 \(\log \Delta\) 层，朴素的实现有 \(O(n\log \Delta)\) 个节点。

若对于树做路径压缩， 则共有 \(O(n)\) 个节点，可以用动态数组存储 \(u.son\)。

四分树近似最近邻查询

描述：给定点集 \(P_i\in \Delta^d\) 和查询 \(Q_i\)，输出 \((1+\epsilon)\) 近似的最近点。

算法：

建立四分树，为每个四分树节点选择一个点集的代表点 \(\text{rep}_u\)（任意一个点即可）。

维护一个全局的答案 \(ans\) 和对应的点编号。

\(\mathtt{Query}(u, \square, q)\):

1. 用 \(\text{rep}_u\) 和 \(\text{rep}_{u.son_i}\) 更新答案

2. 剪枝：考虑 \(v=u.son_i\)，

   若 \(ans \leq (1+\epsilon) (\text{dist}(q,\text{rep}_v)-\text{diam}(\square_v))\)，则调用 \(\mathtt{Query}(v, \square_v,q)\)

   这里 \(\text{dist}(q,\text{rep}_v)-\text{diam}(\square_v)\) 是 \(\min\{\text{dist}(q,S_v)\}\) 的放缩。

分析：

1. 剪枝是基于 \((1+\epsilon)\) 近似的

2. 复杂度分析：给出一个剪枝的界：

   算法运行至 \(\text{diam}(\square)\leq \dfrac{\epsilon}{2}\cdot r^{*}\) 时，有：

   \(\begin{aligned} (1+\epsilon) \cdot (\text{dist}(q,rep_u)-\text{diam}(\square_u)) &\ge (1+\epsilon) (r-\text{diam}(\square_u)) \\ & \ge (1+\epsilon)(1-\frac{\epsilon}{2})r \\ & \ge r\end{aligned}\)

   故这样的点会被剪枝。

   故复杂度的上界为 \(O(\epsilon^{O(-d)} \log \Delta)\)。

欧氏空间 WSPD (Well-separated pair decomposition)

描述：\(\epsilon-\)WSPD，对于点集 \(P\)，要求找到若干对点集：\(\{(A_i,B_i)\}_{i=1}^s\)，使得：

1. \(\max\{\text{diam}(A_i),\text{diam}(B_i)\} \leq \epsilon \cdot \text{dist}(A_i,B_i)\),

   where \(\displaystyle \text{dist}(A,B)=\min_{u\in A,v\in B}\{\text{dist}(u,v)\}\)

2. \(\displaystyle \bigcup_i A_i \times B_i = P \times P\)

算法：

建立四分树，定义 \(\delta(u)=\left\{\begin{aligned} \text{diam}(\square_u) && |\square_u \cap P|\ge 2 \\ 0 && \text{otherwise}\end{aligned}\right.\)

\(\mathtt{WSPD}(u,v)\):

1. 若 \(u=v\) 且 \(\delta_u=0\)，返回 \(\emptyset\)。（边界）
2. 若 \(\delta_u < \delta_v\)，交换 \(u,v\)。
3. 若 \(\delta_u \leq \epsilon \cdot \text{dist}(\square_u,\square_v)\)，则返回 \((u,v)\)。这里 \(\text{dist}\) 直接求两个矩形的距离。
4. \(\mathtt{WSPD}(u.son_i,v)\)。

分析：

输出大小与算法复杂度均为 \(O(n\epsilon^{O(-d)}\log \Delta)\)。

应用：

1. 最近点对：取 \(\epsilon = 1\)，空间中的最近点对一定出现在一对 \((A_i,B_i)\) 中，且 \(|A_i|=|B_i|=1\)。

2. \((1+\epsilon)\) 近似直径：构造 \(\epsilon /2\)-WSPD，在每个点集任取一个代表点 \(\text{rep}(A)\)，答案为 \(\max\{\text{dist}(\text{rep}(A_i),\text{rep}(B_i))\}\)

3. \((1+\epsilon)\) Spanner: 求完全图 \(P\times P\) 的一个子图 \(H\)，使得 \(\text{dist}(x,y) \leq \text{dist}_H(x,y)\leq (1+\epsilon)\text{dist}(x,y)\)：

   算法：求 \(\epsilon/4\)-WSPD，在每个 \(A_i,B_i\) 中选择一个代表点连边。

   可以用于求 MST

Tree Embedding

描述：将点集 \(P\) 从 \(\mathbb{R}^d\) 映射到一颗树 \(T\) 上，尽量最小化 \(\text{Distortion}=\max\{\dfrac{\text{dist}_T(x,y)}{\text{dist}(x,y)}\}\)。

算法：

1. 在 \(2\Delta\) 上构造四分树
2. 随机一个 \([-\Delta,0]^d\) 上的向量 \(v\)，将整棵树平移 \(v\)。
3. 将数据点放在四分树的叶子上，其余点每个点向儿子连接 \(\sqrt{d} \cdot \Delta\cdot 2^{\text{-dep}}\) 的边。

\(\text{dist}(x,y) \leq \text{dist}_T(x,y),\mathbb{E}[\text{dist}_T(x,y)] \leq O(dh) \cdot \text{dist}(x,y)\)，\(h\) 为四分树的高度。

劣势：近似比大 \(O(dh)\)

优势：

1. 因为每对点期望距离都能保持，因此广泛适用于目标函数是点距离和的问题
2. 树上算法性能较好，可解决问题多，有树算法就有欧氏空间近似算法
3. 没有 \(2^d\)，对于高维也相对适用

Johnson-Linderstrauss 降维问题

描述：

给定 \(n\) 个 \(\mathbb{R}^d\) 中的点，将它们映射到 \(\mathbb{R}^m\) 上，

并且 \(\|f(P_1)-f(P_2)\|_2\in (1\pm \epsilon)\cdot \|P_1-P_2\|_2\)（距离 \(\epsilon\) 近似）。

这里 \(m=O(\epsilon^{-2}\log n)\)。

应用引入：

k 聚类问题 2-近似： Gonzalez 算法

描述：找到点集 \(C \subseteq P\)，\(\displaystyle \text{minimize}: \min_{c\in C}\max_{p\in P} \text{dist}(p,c)\)

流程：

1. 任选一个点 \(c_1\)，初始化 \(C=\{c_1\}\)
2. \(k-1\) 轮，不断找出距离 \(C\) 最远的点 \(p\)，放入 \(C\) 中。

复杂度为 \(O(nkd)\)，如果使用 JL 方法优化，则可以降低到 \(O(nk\log n)\)。

JL 问题的下界分析

\(m=O(\log n)\) 是一个紧的下界。

一个构造证明：

\(d=n\) 时，分别取 \(p_i=e_i\)（仅第 \(i\) 维为 \(1\)）。

则降维后，在每个点 \(p'_i\) 的半径 \(\sqrt 2 \cdot (1-\epsilon)\) 范围内不能存在点，且所有点必须在 \(\sqrt n (1 + \epsilon)\) 的球内。

则用体积估计可以得到 \(n\cdot V_m(\sqrt 2(1-\epsilon)) \leq V_m(\sqrt n(1+\epsilon))\)

\(V_m(r) = O(r^m)\)，故 \(m=O(\log n)\)。

JL 构造算法

原问题的一个强化版为 \(\text{dist}(f(p_1),f(p_2))^2\in (1\pm \epsilon)\cdot \text{dist}(p_1,p_2)^2\)

构造思路：

对于一对点 \(x,y\)，考虑 \(v=x-y\)，

我们希望找一个随机映射 \(g_i: \mathbb{R}^d\to \mathbb{R}\)，使得 \(E[g(v)^2]=|v|^2\)

独立生成若干个这样的随机映射后组合 \(f(p)=\frac{1}{\sqrt m}(g_1(p),g_2(p),\cdots,g_m(p))\)。

\(g_i\) 的构造：

生成一个 \(\mathbb{R}^d\) 的随机向量 \(w\)，\(w\) 的每一位采样自 \(\mathscr{N}(0,1)\)。

取 \(g(v)=v\cdot w\)

\(\mathbb{E}(g(v)) = \mathbb{E}(v\cdot w) = |v| \cdot \mathbb{E}(\mathscr{N}(0,1))\)

\(\mathbb{E}(g(v)^2) = \mathbb{E}(\sum (v_iw_i)^2) = |v|^2 E(\mathscr{N}(0,1)^2)=|v|^2\)

误差估计：\(\Pr[f(v)^2] \in (1+\epsilon) |v|^2 \ge 1-\exp(-O(\epsilon^2m))\)

对于 \(n^2\) 对点，用 uion bound 得到一个松的估计为：误差概率 \(\exp(-O(\epsilon^2m))\cdot O(n^2)\leq \delta\), \(\delta\) 为失败概率。

解得 \(m=O(\epsilon^{-2}\log (\frac{n}{\delta}))\)

该算法实际上仅有参数 \(m\)，构造的映射不依赖输入数据（Data Oblivious）。

应用： Linear Regression

输入 \((p_i,v_i)(i=1,2,\cdots,n), p_i\in \mathbb{R}^d,v_i \in \mathbb{R}\)

在实际场景中，\(d \ll n\)。

找到一个 \((w,w_0)\)，最小化 \(\displaystyle \sum_{i} ((x\cdot w)+w_0-y)^2\)

写成归一形式即：\(\arg\min \|Xw-y\|^2\)，最优的 \(w^*=(X^TX)^{-1}X^T y\)

思路：将 JL 写成 \(A\in \mathbb{R}_{m\times n}\), 问题就变成了 \(AWw-Ay\) （不是对 \(d\) 降维，而是对 \(n\) 降维！）。

问题：不能直接降维，因为降维的正确性分析依赖于涉及的不同向量数量 \(n\)，这个 \(n\) 会囊括回归过程中的所有中间 \(Xw\)。

（实际上取 \(m= O(d)\) 即可）。

新的问题：计算 \(AW\) 需要 \(O(nd^2)\) 的时间，即便只需要计算一次。

优化：用稀疏矩阵代替 \(S\) 代替 \(A\)。

\(S\in \mathbb{R}^{m\times n}\)，每一列随机选择一个位置赋予 \(\pm 1\)，取 \(A = \sqrt{\frac{n}{m}} S\)。

这样计算 \(AX\) 的复杂度降到了 \(X\) 的非零位置个数。

应用：离散化 \(\epsilon-\)net

\(d\) 维单位球面 \(\mathcal{S}_{\mathscr{U}}\) 上的一个离散子集 \(N_{\epsilon}\)，使得：

1. (covering)：任何球面上的点都能找到距离 \(\epsilon\) 内的代表。
2. (packing)： \(N_{\epsilon}\) 中任意两个点距离 \(>\epsilon\)。

用一个 trivial 的构造容易说明存在这样的离散集，且其大小为 \(O(\epsilon^{-d})\)

PCA (Principle Components Analysis，主成分分析) 降维

和 JL 的区别：

1. PCA 不针对欧式距离
2. PCA 通过数据直接的关系来降维，而 JL 不依赖数据
3. PCA 降维的基通常都有实际意义

目标描述：

输入 \(x_i\in \mathbb{R}^d\)，找到 \(m\) 个基 \(v_i \in \mathbb{R}^d\)，使得 \(x_i \approx \sum_j a_{i,j} v_j\)

即用较少的基近似线性表示所有的向量。

预处理：

1. 去均值：记 \(\overline{x} = \text{average}\{x_i\}, x_i \leftarrow x_i - \overline{x}\)，将中心移动到原点。
2. 归一化：\(x_{i,j} = \dfrac{x_{i,j}}{\sqrt{\sum_{k} x_{k,j}^2}}\)，尽量让每一个维度的长接近，否则目标函数上会出现维度间的主次。

形式化

\(m=1\) 时，问题等价于找一条直线 \(\ell: k \cdot v_1\)。

目标为： \[ \arg \min_{v} \frac{1}{n} \sum (\text{dist}(v,x_i))^2 \]

\(\text{dist}^2(v,x_i)=x_i^2-(x_i \cdot v)^2\)，所以等价于最大化 \((x_i\cdot v)^2\)。

扩展到任意 \(m\) 的情况，目标同样可以写作最大化投影： \[ \arg \max_{m-\dim \text{subspace} s} \frac{1}{n} \sum_i (\text{length of } x_i\text{'s injection on }s) \] \(m-\) 维的子空间可以用 \(m\) 个 orthonormal（正交标准基）的向量表示。

用 \(\text{span}(v_i) = \{\sum \lambda_i v_i\mid \forall \lambda_i\}\) 来表示平面，则投影长度为 \(\sum_i (x\cdot v_i)^2\)，投影坐标即为 \((x\cdot v_i)_{i=1}^m\)。

求解：

\(m=1\) 时，目标重写为 \(\sum (x_i\cdot v)^2 = \|Xv\|_2^2=v^TX^TXv\)，设 \(A=X^TX\)，

则相当于最大化一个二次型 \(v^TAv\)，而实二次型的标准型为对角矩阵。

做正交对角化，设 \(A=Q\cdot \text{diag}\{\lambda_i\}\cdot Q^T\)，对于对角矩阵求出最优的 \(Q^Tv\) 即可。

若 \(|\lambda_1|\ge |\lambda_2|\cdots\)，则最优的 \(Q^Tv\) 显然为 \(e_1\)，则 \(v=Q\cdot e_1\)，即 \(Q\) 的第一列。

一般的 \(m\)：改为前 \(m\) 列即可。

容易发现，其实求出的就是 \(\lambda_i\) 对应的一个特征向量。

直接用线性代数方法求解不太实用。

近似求最大特征向量（即 \(m=1\)）Power Iteration：

1. 任取一个向量 \(u_0\)。
2. 枚举 \(i\)，求出 \(u_i=A^iu_0\)。
3. 当 \(\dfrac{u_i}{\|u_i\|}\) 接近不变时停止，并返回这个值作为结果。

原理：不断乘 \(A\) 的过程中，会在最大特征向量的方向上被不断拉长。

从右边开始计算 \(Au=X^TXu\) 的复杂度为 \(X\) 的非零元个数，所以复杂度近似 \(O(\text{nnz}(X))\)。

迭代次数估计： \[ (u_t \cdot v_1) \ge 1 - \left(\frac{\lambda_2}{\lambda_1}\right)^t \] 达到 \(1-\epsilon\) 误差需要迭代次数 \(t=O(\frac{\log (d/\epsilon)}{\log(\lambda_1 / \lambda_2)})\)

计算 \(m>1\) ：

先找到 \(v_1\) 之后把 \(x_i \leftarrow x_i - (x_i \cdot v_1) \cdot v_1\) 即可。

PCA 局限性：只能线性拟合的情况下，拟合力有限，当 \(m\) 增大时可能也只有前几个向量比较有意义。

奇异值分解（Singular Value Decomposition）

\(\text{rank}\) 为 \(k\) 的矩阵 \(A\) 可以分解为 \(n\times k, k\times n\) 的两个矩阵的乘积。

\(A=USV^T\)，其中 \(U,V^T\) 为正交矩阵的前 \(k\) 列/前 \(k\) 行， \(S\) 为奇异值矩阵（对角线为奇异值）。

或者写作 \(A = \sum_{i=1}^n s_i \cdot u_iv_i^T\)。

SVD low-rank 近似：仅保留 \(k\) 个，令 \(A_k=\sum_{i=1}^k s_i\cdot u_iv_i^T\)，可以用极少的元素存储 \(A\) 的信息。

用 SVD 做 PCA:

设 \(X=(USV^T)\)，则 \(A=X^TX=VS^TU^TUSV^T=VS^TSV^T\)，将 \(S^TS\) 看作 \(D\)，用 \(V\) 就知道前面的 \(Q\) 了。

SVD 的缺陷：

可能将原本的稀疏的矩阵反而变稠密了：

SVD 做 \(k-\) 聚类问题降维：

对于坐标矩阵（\(n\times d\)）求 SVD，取 \(m=\lceil k/\epsilon\rceil\) 的 low-rank SVD 近似，得到映射。

在 \(X_m\) 上的聚类是 \(\epsilon\) 近似的。

CUR 降维

取 \(\text{rank}=k\)，将 \(A\) 写作 \(A=CUR\)，其中 \(U\) 是 \(\text{rank}(k)\) 的矩阵，但是是稠密的。

\(C,R\) 分别对应原本 \(A\) 的一些列/行。

算法寻找重要的列/行：

复杂度为 \(O(\text{nnz}(A)\cdot \text{poly} \log n+ \text{poly}(k/\epsilon)\)

压缩感知 Compressive Sensing

近似 \(k-\) 稀疏：只有 \(k\) 个位置的绝对值远大于其它位置。

算法原理：（实际上是某种程度上 Input Oblivious 的降维）

1. 生成一组 \(a_1,a_2,\cdots,a_m\in \mathbb{R}^n\)
2. 对于任意的输入量 \(z\)，在传输过程中仅传输 \(b=(z\cdot a_i)\)。
3. 接收方要能从 \(b\) 恢复 \(z\)。

记 \(A=\begin{pmatrix}a_1^T \\ a_2^T \\ \vdots \\ a_m^T\end{pmatrix}\)，则 \(b=Az\)，解 \(Ax=b\) 为欠定方程。

在 \(z\) 任意取稠密输入时，\(m=n\) 是可反解的充要条件。

在 \(z\) 为 \(k-\)稀疏（即至多 \(k\) 个非零，\(k \ll n\)

压缩感知定理：

设 \(A\in \mathbb{R}^{m\times n}\)，其中 \(m=O(k\log (n/k))\)，\(A_{i,j} = \mathcal{N}(0,1)\)。

则有大概率可以从 \(b=Az\) 中恢复 \(z\)（\(z\) 为任意 近似\(k-\)稀疏向量）。

恢复 \(z\)：

\(z\) 不唯一，恢复的方式则是找到非零位置数目最小的一个 \(z\)。

理想目标记做

\[ \arg \min_{Ax=b}\{|\text{supp}(x)|\} \] 这里 \(\text{supp}(x)\) 表示非零坐标数目，也称作 \(\ell_0\)-范数。

由于 \(\ell_0\)-最小化问题是 NPH，可以退一步通过 \(\ell_1\) 来近似，即最小化 \(\sum |x_i|\)。

实际目标为：

\[ \arg \min_{Ax=b}\{\sum |x_i|\} \] 可以用一个线性规划来解决： \[ \begin{aligned} \min&&& \sum y_i \\ s.t. &&& Ax=b \\ &&& y_i -x_i \ge 0 \\ &&& y _i + x_i\ge 0 \end{aligned} \] LP 问题的 Poly 解法：Ellipsoid Method，常用解法：Simplex

稍微修改条件就可以处理数据有噪声的情形。

完整算法：

1. 给定 \(k,n\)。
2. 取 \(m =O(k\log (n/k))\)，随机生成矩阵 \(A \in \mathbb{R}^{m\times n}, A_{i,j} =\mathcal{N}(0,1)\)。
3. 计算 \(b= A z\)。
4. LP 反解 \(x\)。

最小点覆盖 2 近似

转化为： \[ \begin{aligned} \min&&& \sum x_i \\ s.t. &&& x_{u_i}+x_{v_i} \ge 1 \\ &&& x_i \ge 0 \end{aligned} \]

数据流算法

Sparse Recovery

数据流：支持插入删除，要求空间消耗优于直接存储的算法。

定义：

1. 频数向量 \(x\)，每一个维度表示一个不同的数据点出现的次数。

2. support: \(\text{supp}(x)=\{p \mid x_p \ne 0\}\)。

3. \(\|x\|_0=|\text{supp}(x)|\)

4. \(k-\)sparse: \(\|x\|_0 \leq k\)。

Sparse Recovery 算法：检查数据流是否满足 \(k-\)sparse，若满足就需要恢复出 \(\text{supp}(x)\)。

存在一个 \(O(\text{poly}\log n)\) 更新，\(O(k\cdot \text{poly}\log n)\) 查询，空间为 \(O(k\cdot \text{poly} \log n)\) 的算法。

\(k=1\):

1. 维护 \(\text{count, sum}\)，则结果一定为 \(v=\text{sum}/\text{count}\)。
2. 再随机一个常数 \(r\)，维护 \(s=\sum \text{count}_p \cdot r^p \mod q\)，其中 \(q=O(\text{poly}(n))\) 为质数（假设值域也为 \(\text{poly}(n)\) 级别）。
3. 检验 \(v\) 是否为整数，以及 \(s \xlongequal{?} r^v \cdot \text{count}\) 即可判定唯一。

概率分析：

设 \(g(r) = \sum \text{count}_p \cdot r^p - \text{count} \cdot r^v\)，则 \(g(r)\) 是 \(n\) 次多项式，故错误概率为 \(n / q\)。

任意 \(k\)：

考虑一个随机 hash 到 \([2k]\)，若不超过 \(k\) 个元素 \(v_1,\cdots,v_k\)，则 \(v_i\) 单独一个桶的概率 \(>0.5\)。

多取几个 hash，维护 \(2k\) 个 \(k=1\) 的情况即可。

完整算法：

1. 取 \(T=O(\log k)\) 个独立 hash: \(h_i: [\Delta] \to [2k]\)。
2. 对于每一个 \(h_t\)， 将 \(a_i\) 放入 \(h_t(a_i)\) 个 Sparse 进行维护。
3. 结束后，恢复所有结果的并集，判断找到的元素数量和出现频次是否满足要求。

平面近似直径

回顾：近似直径即 round 到 \(\ell = \varepsilon \cdot T / \sqrt{2}\) 的格点上，其中 \(T\) 为一个 2-近似直径，方格数量为 \(O(\epsilon^{-O(d)})\)。

目标空间复杂度：\(O(\varepsilon^{-d} \text{ poly} \log n)\)。

思路：猜测一个直径 \(D\)。

具体：

1. 枚举 \(i=0 \sim \log \Delta\)。
2. 维护点集 round 到 \(\ell=\epsilon\cdot 2^{i}\) 时的 \(k-\)sparse，其中 \(k\) 为确定的 \(O(\epsilon^{-O(d)})\) 级的参数。
3. 找到最小的 \(i\) 使得 \(k-\)sparse 成立，根据 \(k-\)sparse 确定的点集。

实际上找到的 \(i\) 不一定满足 \(2^i \ge \text{diam}\)，但是 \(i\) 越小解越精确，同时又有 \(k\) 限制保证了精确度的下限。

需要维护 \(\log \Delta\) 个结构。

\(\ell_0\) 采样

Sparse Recover 用于恢复具体的数据，\(\ell_0\) 采样则返回单个元素 \(p\)，且 \(p\) 满足分布： \[ \forall q \in \text{supp}(x), \Pr[p=q] =\frac{1}{|\text{supp}(x)|} \] 思路：

设 \(\text{supp}(x)=k\)，将所有元素以 \(\frac{1}{k}\) 的概率保留，在保留下来的元素中均匀采样。

保留下来的元素有常数概率只有一个。

具体实现：

1. 维护 \(m=O(\log n)\) 个 \(1-\)sparse Recovery \(\mathcal{S}_i\)。
2. 维护随机 hash \(h_i:[\Delta]\to \{0,1\}\)，且 \(\forall p\in [\Delta],\Pr[h(p)=1]=2^{-i}\)。
3. 插入时仅保留 \(h_t(a_i)=1\) 的 \(a_i\) 放入 \(\mathcal{S}_t\)。
4. 找到一个返回 Yes 的 \(\mathcal{S}_i\)，返回恢复出来的元素。

数据流图连通分量

\(n\) 确定，\(m\) 条边为数据流。

存在一个 \(\tilde{O}(n)=O(\text{poly}\log n)\) 空间，单次操作 \(\text{poly}\log n\) 时间的算法。

记一个广义频数向量： \[ x^u_{(u,v)} = \left\{\begin{aligned} 1 && (u,v) \in E, u< v \\ -1 && (u,v) \in E, u > v \\ 0 &&\text{otherwise}\end{aligned} \right. \]

\[ x^{S} = \sum_{u\in S} x^u \]

则 \(\text{supp}(x^S)\) 仅包含 \(S\) 与 \(V \backslash S\) 之间的边。

注意到 \(\ell_0\) 采样具有可合并性：

1. 对于每一个点 \(v\) 维护 \(\ell_0\) 采样 \(\mathscr{L}_v\)。
2. 插入删除时对于 \(\mathscr{L}_u,\mathscr{L}_v\) 操作。
3. 做正常的合并操作，每次可以合并两个点集之后需要同时合并对应的 \(\ell_0\) 采样。

此外，还可以做一个数据流近似 Boruvka 算法

思路是对于每一种边权建立一个 \(\ell_0\) 采样，但是需要将边权 round 到最近的 \((1+\varepsilon)^w\)。

这样就只需要 \(O(n\cdot \log_{1+\varepsilon} \Delta)\) 个采样，做 Boruvka 的过程中枚举边权。

大数据算法

MPC (Massively Parallel Computing).

MapReduce, RDD(Resilient Distributed Dataset)

MapReduce 框架

表示一种大数据处理的格式约定。

数据以 \((K,V)\) (key, value) 二元组形式表示，

Mapper: \(\{(K,V)\}_{i=1}^n \to \{(K',V')\}_{i=1}^{n\times m}\)。

Reducer: 输入为一组 \(K\) 相同的二元组 \((K^*,\{V_i\})\)，输出也为 \((K^*,\{V_i\})\) 的形式。

mapper 负责调整数据形式，reducer 负责合并数据。

如求 \(\ell_0\) 范数的操作：

1. 输入 \((i,a_i)\)。
2. 第一轮：
   1. Mapper: \((i,a_i) \mapsto (a_i,1)\)。
   2. Reducer: \((K=a_i, \{1,1,1,1,\cdots\}) \mapsto (a_i,1)\)，（对于同一个 \(a_i\) 合并）。
3. 第二轮：
   1. Mapper: \((a_i,1) \mapsto (0,1)\)。
   2. Reducer: \((0,\{1,1,1,1\}) \mapsto (0,1+1+1+\cdots)\)。

MPC 框架

输入 \(n\) 个值 \(p_i\)。

每台机器有 \(s=o(n) = n^{\alpha}\) 的存储容量。

机器个数为 \(m = \Omega(n/s)\)。

每一轮可以完成机器间信息收发，但是每台机器传输量为 \(o(s)\)。

优化的主要目标为轮数，其次是每轮的本地效率。

一个简单的问题：Broadcast。

一号机存储了一条信息 \(t\)，\(s\ge t^{1+\epsilon}\)，要求广播给所有机器。

根据传输量的限制，不能一轮发送给所有机器，可以呈现多叉树方式传递。

MPC 排序：

每轮：一号机随机选择 \(\sqrt s\) 个 Pivot，每台机子本地进行一轮 Pivot，将 \(\sqrt s\) 个区间的内数的个数返还给一号机。

每台机器根据汇总的个数，重新分发数据给其他机子。

复杂度：排序共 \(O(\log_s n)\) 轮，每轮需要汇总信息要 \(O(\log_s n)\) 的时间，总轮数为 \(O(\log_s^2n)\)。

super-linear: \(s=n^{1+\epsilon}\)

near-linear: \(s=\tilde{O}(n)\)

sub-linear: \(s=n^{1-\epsilon}\)

super-linear MST:

先将所有边按照较小顶点的编号排序，然后每台机子本地做对应边集的结果，最后直接全部发送到 \(1\) 号点合并。

MPC 近似直径

直径可以合并，但是会累积误差。