# 高维几何与集中不等式详解

> 高维几何为什么反直觉？1000 维球体 99.995% 的体积集中在表面 1% 薄层，随机向量几乎正交。系统讲解 Markov、Chebyshev、Hoeffding 等集中不等式，及其在 Johnson-Lindenstrauss 引理、QJL 内积估计与 PolarQuant 角度量化中的应用——TurboQuant 背后的数学基础。

Canonical: https://doraemeng.dev/notes/high-dim-geometry-concentration/


1000 维单位球，剥掉最外层 1% 的壳，剩下多少体积？答案小到可以忽略：几乎所有体积都贴着表面。这个反直觉的结论是理解高维几何的起点：随机向量的长度高度集中，方向几乎正交，内积接近 0。TurboQuant 这类量化方法能成立，靠的就是这些集中性质。

## 一、高维几何：反直觉的世界

### 1.1 高维球体的"空心化"

三维球的体积在半径上分布得比较均匀；到了 1000 维以上，几乎所有体积都贴着表面。把这个直觉写成公式：d 维单位球的体积随半径的 d 次方增长，

```
V_d(r) = π^(d/2) / Γ(d/2 + 1) · r^d
```

当 d 很大时，半径缩到 1-ε 处的体积占比是

```
V_d(1-ε) / V_d(1) = (1-ε)^d ≈ e^(-εd)
```

这个比值只和 εd 有关，维度越高衰减越快。d=1000、ε=0.01 时，只剥掉外层 1% 的壳，剩余体积是

```
剩余体积 = (0.99)^1000 ≈ e^(-10) ≈ 0.000045
→ 99.995% 的体积在表面1%的薄层！
```

维度越高，这层壳越薄，所谓"球"在几何上更接近一层皮。对 TurboQuant 来说，这意味着高维向量几乎等长，长度集中在球面上；PolarQuant 利用的正是这一点：半径相对稳定，角度承载主要信息。

### 1.2 随机向量几乎正交

在 d 维空间里随机取两个单位向量 u、v，当 d→∞，内积趋于 0：

```
<u, v> → 0
```

设 u,v~N(0,I_d)，归一化后内积是

```
<u/||u||, v/||v||> = (1/d)∑u_i v_i · d/(||u||||v||)
```

由大数定律，(1/d)∑u_i v_i→E[u_i v_i]=0，||u||²/d→1，所以内积≈0，夹角≈90°。模拟结果也符合：d=3 时夹角方差很大；d=100 时集中在 90°±8°；d=10000 时集中在 90°±0.8°。

```
d=3:   随机向量夹角平均约 90°，方差大
d=100: 夹角集中在 90° ± 8°
d=10000: 夹角集中在 90° ± 0.8°
```

对 TurboQuant 的意义是，QJL 的 sign-random-projection 依赖随机方向足够分散；高维里少量投影就能把不同向量区分开。

### 1.3 高斯分布的集中性

一维高斯有厚尾，P(|X|>2σ)≈5%。到了 d 维，||X||²=∑X_i² 高度集中。对 X~N(0,I_d)，

```
||X/√d||^2 = (1/d)∑X_i^2 → 1 (当 d→∞)
```

方差是

```
Var(||X||^2/d) = 2/d → 0
```

100 维时，半径几乎都落在 √100=10 附近，分布像一个薄球壳，不再是一维那条带尾巴的钟形曲线。

## 二、集中不等式：概率的上界艺术

集中不等式干的事情，是给偏离均值的概率加上界。Markov 不等式只需要非负随机变量和期望：对 X≥0、a>0，

```
P(X ≥ a) ≤ E[X]/a
```

如果平均工资是 5000，收入超过 50000 的人不超过 10%。这个界很松，但不需要方差，也不需要分布形状。

Chebyshev 不等式把方差用上：

```
P(|X - E[X]| ≥ t) ≤ Var(X)/t^2
```

它给出的是偏离均值超过 t 的概率上界，比 Markov 更紧，但仍然只用了二阶矩。

Hoeffding 不等式是后面 JL 和 QJL 分析里的核心工具。设 X_1,...,X_n 独立且有界，X_i∈[a_i,b_i]，S_n=∑X_i，则

```
P(|S_n - E[S_n]| ≥ t) ≤ 2exp(-2t^2 / ∑(b_i-a_i)^2)
```

同分布、[0,1] 有界时，式子简化成

```
P(|(1/n)∑X_i - μ| ≥ ε) ≤ 2e^(-2nε^2)
```

它的两个关键特性：误差概率随 n 指数衰减；只要求有界，不要求正态分布。

亚高斯分布把这套界抽象成一个定义：如果

```
P(|X - E[X]| ≥ t) ≤ 2e^(-t^2/2σ^2)
```

就说 X 是亚高斯的。有界随机变量、正态分布、Rademacher 变量都是例子。独立亚高斯变量的和仍然是亚高斯，方差参数相加。

## 三、在 TurboQuant/JL 中的应用

### 3.1 Johnson-Lindenstrauss 引理证明骨架

JL 引理要证明的是，随机投影 f(x)=1/√k Rx（R_ij~N(0,1)）在 k 足够大时保持距离。证明分四步，核心是固定一个向量看投影后的长度。

固定单位向量 x，第 j 个投影分量是

```
y_j = (1/√k)∑R_{ji}x_i ~ N(0, 1/k)
```

于是 ||f(x)||²=∑y_j² 是 k 个独立 χ² 变量之和。用亚指数/χ² 版本的集中不等式，偏差超过 ε 的概率满足

```
P(|||f(x)||^2 - 1| ≥ ε) ≤ 2e^(-ckε^2)
```

最后对所有 n 个点的 C(n,2) 对距离做 union bound，要求

```
k ≥ 4logn / (ε^2/2 - ε^3/3) = O(ε^(-2)log n)
```

这就是 JL 引理的样本复杂度：投影维度只需随 log n 增长，和原始维度 d 无关。

### 3.2 QJL 的误差分析

QJL（Quantized Johnson-Lindenstrauss）用 sign-random-projection 估计内积。查询 q、键 k，投影矩阵 R∈R^{m×d}，元素 i.i.d. N(0,1)；量化后 q̂=sign(Rq)，k̂=sign(Rk)；估计量是

```
ṡ = (1/m)∑q̂_i · k̂_i
```

单个投影的期望是

```
E[sign(R_i q) · sign(R_i k)] = 1 - 2θ/π
```

其中 θ=arccos(<q,k>/(||q||||k||)) 是夹角。因为 q̂_i·k̂_i∈{-1,+1} 有界，Hoeffding 直接给出

```
P(|ṡ - E[ṡ]| ≥ t) ≤ 2e^(-mt^2/2)
```

所以 m=O(ε^{-2}log(1/δ)) 足以保证误差小于 ε 的概率大于 1-δ。

### 3.3 PolarQuant 的几何基础

极坐标变换把 x=(x_1,...,x_d) 映射成 (r,θ_1,...,θ_{d-1})：

```
x = (x_1, x_2, ..., x_d) → (r, θ_1, θ_2, ..., θ_{d-1})
```

递归结构可以拿 4D 举例：先把 (x1,x2) 变成 (r12,θ12)，(x3,x4) 变成 (r34,θ34)，再把 (r12,r34) 变成 (R,θ1234)，最终存 R、θ12、θ34、θ1234。

```
Level 0: (x1, x2) → (r12, θ12)
         (x3, x4) → (r34, θ34)

Level 1: (r12, r34) → (R, θ1234)

最终存储: R, θ12, θ34, θ1234
```

高维随机向量的方向在球面上均匀分布；TurboQuant 先做随机旋转，让数据各向同性，角度分布更规则，便于量化。每个角度量化引入的误差 δθ 对最终内积的影响约为

```
Δ ≈ r · sinθ · δθ
```

高维里 r 稳定，比特可以按层级分给不同角度，控制总误差。

## 四、这些性质的适用边界

这些性质放在一起，才是 QJL 和 PolarQuant 的数学基础：高维向量长度集中，方向近似正交，少量随机投影就能以高概率保住内积；角度量化则利用半径稳定、角度承载主要信息。它们都有前提。数据要经过随机旋转，各向同性才成立；投影维度 k 或 m 要满足上面的集中界，太小则误差界不成立；数据分布如果有强相关结构，随机投影的方差会变大，误差界要重新算。把它们当成"高维一定好"的结论，会在真实 embedding 上翻车。

