高级算法 (Spring 2026)/作业3
低 [math]\displaystyle{ \ell_\infty }[/math]-norm 对高斯 JL 变换没有帮助
令 [math]\displaystyle{ \Pi \in \mathbb R^{m\times d} }[/math] 是一个高斯 Johnson-Lindenstrauss 变换，其中每个元素独立服从 [math]\displaystyle{ N(0,1/m) }[/math]。给定任意固定单位向量 [math]\displaystyle{ x\in\mathbb S^{d-1} }[/math]。
- 证明 [math]\displaystyle{ \Pi x }[/math] 的每个坐标都独立服从 [math]\displaystyle{ N(0,1/m) }[/math]。
- 证明 [math]\displaystyle{ \|\Pi x\|_2^2 }[/math] 与 [math]\displaystyle{ \frac{1}{m}\chi_m^2 }[/math] 同分布。因此 [math]\displaystyle{ \|\Pi x\|_2 }[/math] 的分布与 [math]\displaystyle{ \|x\|_\infty }[/math] 无关。
- 解释为什么如果使用高斯 JL 变换，即使 [math]\displaystyle{ x }[/math] 满足很强的平坦性条件，例如 [math]\displaystyle{ \|x\|_\infty \le O(1/\sqrt d) }[/math]，为了保证 [math]\displaystyle{ \mathbb P[\|\Pi x\|_2^2-1|\gt \epsilon]\le \delta }[/math]，所需的目标维数仍然是 [math]\displaystyle{ m=\Theta(\epsilon^{-2}\log(1/\delta)) }[/math]。
- 对比坐标采样型（即 [math]\displaystyle{ \Pi x }[/math]直接随机输出 [math]\displaystyle{ x }[/math]的某几个维度）降维，简要解释为什么低 [math]\displaystyle{ \ell_\infty }[/math]-norm 对坐标采样有帮助，但对高斯 JL 变换没有帮助。
torus 上的随机网格 LSH
考虑 metric space [math]\displaystyle{ ( [0,n]^d,d_{\mathrm{torus}} ) }[/math]，其中距离定义为 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)=\sqrt{\sum_{i=1}^d \min{|x_i-y_i|,n-|x_i-y_i|}^2} }[/math]。给定网格宽度 [math]\displaystyle{ w\gt 0 }[/math]。随机选择平移向量 [math]\displaystyle{ s\in[0,w)^d }[/math]，并定义 hash function [math]\displaystyle{ h_s(x)=(\lfloor (x_1+s_1)/w\rfloor,\dots,\lfloor (x_d+s_d)/w\rfloor) }[/math]，其中每个坐标都按照 torus 的方式取模。
(1) 对于两个点 [math]\displaystyle{ x,y\in[0,n]^d }[/math]，记 [math]\displaystyle{ \Delta_i=\min\{|x_i-y_i|,n-|x_i-y_i|\} }[/math]。证明如果对所有 [math]\displaystyle{ i }[/math] 都有 [math]\displaystyle{ \Delta_i\lt w }[/math]，那么 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)]=\prod_{i=1}^d (1-\Delta_i/w) }[/math]。
(2) 证明如果 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)\le r }[/math]，那么 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)]\ge 1-\sqrt d,r/w }[/math]。提示：可以使用 [math]\displaystyle{ \sum_i\Delta_i\le \sqrt d\sqrt{\sum_i\Delta_i^2} }[/math]。
(3) 解释为什么这个 LSH family 的随机桶可以看成随机平移后的 axis-aligned cube。请从“近点容易落在同一个随机集合中，远点不容易落在同一个随机集合中”的角度解释这个构造的直觉。
(4) 讨论这个构造在高维空间中的局限性。特别地，当距离 [math]\displaystyle{ d_{\mathrm{torus}}(x,y) }[/math] 分散在很多个坐标上时，为什么随机网格更容易把 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 切开？
球面上的随机超平面 LSH
考虑球面空间 [math]\displaystyle{ (\mathbb S^{d-1},d) }[/math]，其中距离定义为 [math]\displaystyle{ d(x,y)=\arccos\langle x,y\rangle }[/math]。随机选择 [math]\displaystyle{ g\sim N(0,I_d) }[/math]，并定义 hash function [math]\displaystyle{ h_g(x)=\operatorname{sign}\langle g,x\rangle }[/math]。
(1) 对任意 [math]\displaystyle{ x,y\in\mathbb S^{d-1} }[/math]，令 [math]\displaystyle{ \theta=\arccos\langle x,y\rangle }[/math]。证明 [math]\displaystyle{ \mathbb P[h_g(x)=h_g(y)]=1-\theta/\pi }[/math]。
(2) 解释上述公式的几何直觉：随机超平面什么时候会把 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 分到两侧？
(3) 现在使用 [math]\displaystyle{ k }[/math] 个独立随机超平面 [math]\displaystyle{ g_1,\dots,g_k }[/math]，并定义组合 hash key 为 [math]\displaystyle{ H(x)=(h_{g_1}(x),\dots,h_{g_k}(x)) }[/math]。证明 [math]\displaystyle{ \mathbb P[H(x)=H(y)]=(1-\theta/\pi)^k }[/math]。
(4) 给定两个角度阈值 [math]\displaystyle{ 0\lt \theta_1\lt \theta_2\lt \pi }[/math]。令近点满足 [math]\displaystyle{ d(x,y)\le \theta_1 }[/math]，远点满足 [math]\displaystyle{ d(x,y)\ge \theta_2 }[/math]。写出这个 LSH family 的参数 [math]\displaystyle{ p_1 }[/math] 和 [math]\displaystyle{ p_2 }[/math]，并推导标准 LSH exponent [math]\displaystyle{ \rho=\log(1/p_1)/\log(1/p_2) }[/math]。
由范数保持推出内积保持
设线性映射 [math]\displaystyle{ \Pi }[/math] 对向量集合 [math]\displaystyle{ {x,y,x+y,x-y} }[/math] 都保持平方范数，即对所有 [math]\displaystyle{ v\in{x,y,x+y,x-y} }[/math] 都有 [math]\displaystyle{ (1-\epsilon)\|v\|_2^2\le \|\Pi v\|_2^2\le (1+\epsilon)\|v\|_2^2 }[/math]。
- 使用恒等式 [math]\displaystyle{ \langle x,y\rangle=(\|x+y\|_2^2-\|x-y\|_2^2)/4 }[/math]，证明 [math]\displaystyle{ |\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon)(\|x\|_2^2+\|y\|_2^2) }[/math]。
- 在 [math]\displaystyle{ \|x\|_2=\|y\|_2=1 }[/math] 的情况下，将上式化简为 [math]\displaystyle{ |\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon) }[/math]。
- 解释为什么如果 JL 变换对 [math]\displaystyle{ n }[/math] 个点的所有两两距离都近似保持，那么这些点的两两内积也近似保持。
- 进一步讨论：如果这些点都在单位球面上，那么 JL 降维之后，球面角度 [math]\displaystyle{ \arccos\langle x,y\rangle }[/math] 在什么意义下也被近似保持？
从阈值版 Approximate Near Neighbor 到 Approximate Nearest Neighbor
假设你有一个阈值版 Approximate Near Neighbor 黑盒。给定半径 [math]\displaystyle{ r }[/math] 和查询点 [math]\displaystyle{ q }[/math]，如果数据集 [math]\displaystyle{ P }[/math] 中存在点 [math]\displaystyle{ p }[/math] 满足 [math]\displaystyle{ |p-q|\le r }[/math]，那么黑盒会返回某个点 [math]\displaystyle{ p' }[/math]，并保证 [math]\displaystyle{ |p'-q|\le a r }[/math]。
现在希望用这个黑盒解决普通 Approximate Nearest Neighbor 问题。设真正最近邻距离为 [math]\displaystyle{ d^\star=\min_{p\in P}|p-q| }[/math]。我们建立一组半径 [math]\displaystyle{ r_0,r_1,r_2,\dots }[/math]，满足 [math]\displaystyle{ r_{i+1}=b r_i }[/math]。查询时，从小到大尝试这些半径，并返回第一个成功的黑盒查询结果。
(1) 证明最终得到的近似比至多为 [math]\displaystyle{ ab }[/math]。
(2) 如果希望最终得到 [math]\displaystyle{ c }[/math]-approximate nearest neighbor，应该如何选择 [math]\displaystyle{ a }[/math] 和 [math]\displaystyle{ b }[/math]？
(3) 解释为什么常见做法中，会把阈值版 ANN 黑盒的 approximate ratio 从 [math]\displaystyle{ c }[/math] 设置为 [math]\displaystyle{ \sqrt c }[/math]。
(4) 如果最近邻距离的可能范围被限制在 [math]\displaystyle{ [1,\Delta] }[/math] 中，分析需要建立多少个半径层级。
torus 上随机网格 LSH 的维数影响
继续考虑 metric space [math]\displaystyle{ ( [0,n]^d,d_{\mathrm{torus}} ) }[/math]，其中 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)=\sqrt{\sum_{i=1}^d \min{|x_i-y_i|,n-|x_i-y_i|}^2} }[/math]。使用题目 4 中的随机平移网格 hash function [math]\displaystyle{ h_s }[/math]，其中网格宽度为 [math]\displaystyle{ w }[/math]。
(1) 设 [math]\displaystyle{ x,y }[/math] 只在一个坐标上相差 [math]\displaystyle{ r }[/math]，其他坐标完全相同。计算 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)] }[/math]。
(2) 设 [math]\displaystyle{ x,y }[/math] 在每个坐标上都相差 [math]\displaystyle{ r/\sqrt d }[/math]，因此 [math]\displaystyle{ d_{\mathrm{torus}}(x,y)=r }[/math]。在 [math]\displaystyle{ r/\sqrt d\lt w }[/math] 的条件下，计算 [math]\displaystyle{ \mathbb P[h_s(x)=h_s(y)] }[/math]，并将其写成 [math]\displaystyle{ (1-r/(w\sqrt d))^d }[/math] 的形式。
(3) 比较上述两种情况。说明即使两对点的 torus 距离都等于 [math]\displaystyle{ r }[/math]，随机网格 LSH 的碰撞概率仍然可能不同。
(4) 解释这说明了什么：axis-aligned grid LSH 并不是只依赖于欧氏距离的完美 LSH family，而是会受到坐标方向和维数的影响。
先用 JL 降维，再做随机超平面 LSH
设 [math]\displaystyle{ P\subseteq\mathbb S^{d-1} }[/math] 是 [math]\displaystyle{ n }[/math] 个单位向量。令 [math]\displaystyle{ \Pi:\mathbb R^d\to\mathbb R^m }[/math] 是一个 JL transform，并假设对所有 [math]\displaystyle{ x,y\in P }[/math]，都有 [math]\displaystyle{ ||\Pi x-\Pi y|_2^2-|x-y|_2^2|\le \epsilon }[/math]。同时假设对所有 [math]\displaystyle{ x\in P }[/math]，都有 [math]\displaystyle{ ||\Pi x|_2^2-1|\le \epsilon }[/math]。
(1) 证明对所有 [math]\displaystyle{ x,y\in P }[/math]，都有 [math]\displaystyle{ |\langle \Pi x,\Pi y\rangle-\langle x,y\rangle|\le O(\epsilon) }[/math]。
(2) 令 [math]\displaystyle{ \theta=\arccos\langle x,y\rangle }[/math]，并令 [math]\displaystyle{ \widetilde\theta=\arccos(\langle \Pi x,\Pi y\rangle/(|\Pi x|_2|\Pi y|_2)) }[/math]。在 [math]\displaystyle{ \theta }[/math] 不太接近 [math]\displaystyle{ 0 }[/math] 或 [math]\displaystyle{ \pi }[/math] 的情况下，给出 [math]\displaystyle{ |\theta-\widetilde\theta| }[/math] 的上界。
(3) 解释为什么可以先对数据集 [math]\displaystyle{ P }[/math] 做 JL 降维，再在低维空间中使用随机超平面 LSH。
(4) 讨论当两个点的夹角非常小时，为什么需要更小的 JL 误差才能保证角度的相对误差较好。
为什么 CountSketch 需要随机符号
考虑一个没有随机符号的 CountSketch。对每个 [math]\displaystyle{ i\in[n] }[/math]，随机选择桶 [math]\displaystyle{ h(i)\in[m] }[/math]，并令 [math]\displaystyle{ \Pi_{h(i),i}=1 }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。
取向量 [math]\displaystyle{ x=(1,1,\dots,1)/\sqrt n }[/math]。
(1) 证明 [math]\displaystyle{ \mathbb E|\Pi x|_2^2=1+(n-1)/m }[/math]。
(2) 说明如果 [math]\displaystyle{ m=o(n) }[/math]，那么这个没有随机符号的 sketch 对该向量的范数估计会有严重偏差。
(3) 现在考虑标准 CountSketch：对每个 [math]\displaystyle{ i\in[n] }[/math]，随机选择桶 [math]\displaystyle{ h(i)\in[m] }[/math]，并随机选择符号 [math]\displaystyle{ \sigma_i\in{-1,1} }[/math]，令 [math]\displaystyle{ \Pi_{h(i),i}=\sigma_i }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。解释随机符号 [math]\displaystyle{ \sigma_i }[/math] 如何使不同坐标碰撞产生的交叉项在期望中相互抵消。
(4) 总结随机符号在 CountSketch 中的作用：它并不能避免碰撞，但可以让碰撞带来的误差成为均值为零的随机噪声。
CountSketch OSE 的 [math]\displaystyle{ m=O(d^2) }[/math] 上界
令 [math]\displaystyle{ U\in\mathbb R^{n\times d} }[/math] 是一个列正交矩阵，即 [math]\displaystyle{ U^\top U=I_d }[/math]。令 [math]\displaystyle{ \Pi\in\mathbb R^{m\times n} }[/math] 是 CountSketch 矩阵：对每个原始坐标 [math]\displaystyle{ i\in[n] }[/math]，随机选择桶 [math]\displaystyle{ h(i)\in[m] }[/math]，并随机选择符号 [math]\displaystyle{ \sigma_i\in{-1,1} }[/math]；然后令 [math]\displaystyle{ \Pi_{h(i),i}=\sigma_i }[/math]，其他位置为 [math]\displaystyle{ 0 }[/math]。记 [math]\displaystyle{ u_i }[/math] 为 [math]\displaystyle{ U }[/math] 的第 [math]\displaystyle{ i }[/math] 行，视为 [math]\displaystyle{ \mathbb R^d }[/math] 中的列向量。
(1) 证明 [math]\displaystyle{ \Pi^\top\Pi-I_n }[/math] 的第 [math]\displaystyle{ (i,j) }[/math] 个元素在 [math]\displaystyle{ i\ne j }[/math] 时等于 [math]\displaystyle{ \mathbf 1_{h(i)=h(j)}\sigma_i\sigma_j }[/math]，在 [math]\displaystyle{ i=j }[/math] 时等于 [math]\displaystyle{ 0 }[/math]。
(2) 推出 [math]\displaystyle{ U^\top\Pi^\top\Pi U-I_d=\sum_{i\ne j}\mathbf 1_{h(i)=h(j)}\sigma_i\sigma_j u_i u_j^\top }[/math]。
(3) 证明在计算 [math]\displaystyle{ \mathbb E[|U^\top\Pi^\top\Pi U-I_d|_F^2] }[/math] 时，随机符号会使所有交叉项的期望为 [math]\displaystyle{ 0 }[/math]。也就是说，只有同一对 [math]\displaystyle{ (i,j) }[/math] 与自身相乘的项会保留下来。
(4) 证明 [math]\displaystyle{ \mathbb E[|U^\top\Pi^\top\Pi U-I_d|*F^2]\le \frac{1}{m}\sum*{i\ne j}|u_i|_2^2|u_j|_2^2 }[/math]。
(5) 使用 [math]\displaystyle{ \sum_i|u_i|_2^2=|U|_F^2=d }[/math]，证明 [math]\displaystyle{ \mathbb E[|U^\top\Pi^\top\Pi U-I_d|_F^2]\le d^2/m }[/math]。
(6) 用 Markov 不等式证明，如果 [math]\displaystyle{ m\ge d^2/(\epsilon^2\delta) }[/math]，那么以概率至少 [math]\displaystyle{ 1-\delta }[/math]，有 [math]\displaystyle{ |U^\top\Pi^\top\Pi U-I_d|_F\le \epsilon }[/math]。
(7) 证明如果 [math]\displaystyle{ |U^\top\Pi^\top\Pi U-I_d|_2\le \epsilon }[/math]，那么对所有 [math]\displaystyle{ x\in\mathbb R^d }[/math] 都有 [math]\displaystyle{ (1-\epsilon)|Ux|_2^2\le |\Pi Ux|_2^2\le (1+\epsilon)|Ux|_2^2 }[/math]。并解释为什么第 (6) 问中的 Frobenius norm bound 足以推出 spectral norm bound。
(8) 总结：说明 CountSketch 虽然每一列只有一个非零元素，但当 [math]\displaystyle{ m=O(d^2/(\epsilon^2\delta)) }[/math] 时，仍然可以作为一个 [math]\displaystyle{ d }[/math] 维子空间的 Oblivious Subspace Embedding。