球面均匀随机采样
cos. 的 locality sensitive hashing 方法估算需要球面均匀采样, 计算时随机数生成速度和存储是一个瓶颈.
为方便, 采用伪随机生成的方法, 假设各维度独立同分布, 然后缩放到球面上.
注意到球面均匀分布在正交变换下不变, 有各维度分布在模1向量加权和下不变. 设其特征函数为 $cf(t)$, 则有方程 :
$cf(t) = \prod cf(y_it)$, 其中 $y_i$ 满足 $\sum y_i^2=1$.
假设连续, 取对数, 即得 Cauchy 型函数方程. 可以解得分布为均值为零的正态分布.
另一种方法是各维度均匀分布, 除掉球面外的点. 但由于单位球体体积随维度收敛于零, 此方法复杂度上为维度的指数.
均匀分布如果不除掉球面外的点, 则 $(1, \ldots, 1, 0, \ldots, 0)$($k$ 个 1) 与 $(1, 0, \ldots, 0)$ 处的密度比为 $\sqrt{k}$, 显然非均匀.
为方便, 采用伪随机生成的方法, 假设各维度独立同分布, 然后缩放到球面上.
注意到球面均匀分布在正交变换下不变, 有各维度分布在模1向量加权和下不变. 设其特征函数为 $cf(t)$, 则有方程 :
$cf(t) = \prod cf(y_it)$, 其中 $y_i$ 满足 $\sum y_i^2=1$.
假设连续, 取对数, 即得 Cauchy 型函数方程. 可以解得分布为均值为零的正态分布.
另一种方法是各维度均匀分布, 除掉球面外的点. 但由于单位球体体积随维度收敛于零, 此方法复杂度上为维度的指数.
均匀分布如果不除掉球面外的点, 则 $(1, \ldots, 1, 0, \ldots, 0)$($k$ 个 1) 与 $(1, 0, \ldots, 0)$ 处的密度比为 $\sqrt{k}$, 显然非均匀.
