随机超平面角度指纹

形式陈述 ​

一个指纹必须连同哪份配置一起解释 ​

给定整数 $d,q\ge 1$。输入是实内积空间理路内积空间Inner product space带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。 ${\mathbb{R}}^d$ 中的非零有限向量 $x$；数学对象是方向 $\overline{x}=x/\Vert x{\Vert }_2$，两个对象间的角度为

零向量没有这个方向，接口拒绝它。这里保留正负方向的区别，$x$ 与 $-x$ 的夹角是 $\pi$，不是同一条无向直线。

一次建立共享配置 $G=(g_0,\dots ,g_{q-1})$，定义

边界上的零内积统一编码为 $1$。对同一配置编码的两个向量，输出失配数 $H$ 和归一化角度估计

这里真正计算的是等长字串的Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。；不能把两份各自重新抽样的指纹逐位比较。

公开参考规定第 $i$ 位放入第 $\lfloor i/8\rfloor$ 个字节的第 $7-(imod8)$ 位，末字节低端未使用位全部为零。载荷长度恰为 $\lceil q/8\rceil$ 字节。指纹还持有不可变配置的共享句柄，比较时要求句柄是同一个对象；即使两份独立配置碰巧有相同系数，也保守地拒绝跨句柄比较。载荷本身不包含维数、位数或超平面，重载字节必须另外提供同一配置。长度与填充检查只能证明语法规范，不能证明这些字节确实由某个宣称的向量生成。

概率结论的抽样条件 ​

保证要求 $g_i$ 是相互独立理路独立性Statistical independence从概率表理解独立性，区分两两、相互和条件独立，并用可计算反例澄清零协方差与条件均值的限度。的标准多元正态向量理路多元正态分布Multivariate normal distribution · Multivariate Gaussian distribution · Jointly Gaussian vector以所有线性组合都正态刻画联合高斯向量，并由特征函数连接线性构造、退化支撑、全维密度与条件分布。 $N(0,I_d)$，并且待比较的 $x,y$ 在抽取 $G$ 之前已固定。更一般地，独立且方向在球面上均匀的非零法向量也够用；长度不影响符号。独立不等于各向同性，给各坐标不同方差通常改变角度度量。

随机超平面分离引理理路Goemans–Williamson Max-Cut 近似Goemans-Williamson Max-Cut · GW algorithm · Max-Cut SDP rounding以单位向量半正定松弛和随机过原点超平面舍入无向非负权 Max-Cut，并由逐边角度不等式得到 0.87856 期望近似比。已经给出单次失配概率 $a=\theta /\pi$。本接口把同一对向量放进 $q$ 个独立副本，于是

同一位上的两个符号共享一张平面；不同位的失配指标才独立。由Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。，对 $\epsilon >0$，

若事先固定了 $m\ge 1$ 对向量，取

可使这 $m$ 对的误差同时小于 $\epsilon$，失败概率至多 $\delta$。这里对各对使用并集界，不要求不同向量对的误差独立。如果固定 $n$ 个向量并要求所有两两距离，可取 $m=(\genfrac{}{}{0ex}{}{n}{2})$；$n<2$ 时没有待保证的不同对象对，不使用这个对数式。

编码、比较与费用 ​

编码逐行算点积，把符号置入相应字节。已经处理前 $i$ 行时，前 $i$ 个有效位与定义完全一致，其余位保持零；一次置位建立下一步不变量，结束后得到规范载荷。比较逐字节异或，再累计置位数。由于无效填充位都为零，它们不会增加失配数。

稠密实数算术模型下，一次编码需 $O(qd)$ 运算，共享配置占 $O(qd)$ 个系数。每个指纹另占 $\lceil q/8\rceil$ 个字节和一个句柄；存 $n$ 个指纹不能把共享配置重复算 $n$ 次，也不能把配置完全删去。公开实现先形成 $q$ 个符号，临时工作空间为 $O(q+d)$，不是只有输出位串那么多。比较两份已验证指纹需 $O(\lceil q/8\rceil )$ 时间，估计值可作为分数 $H/q$ 精确输出。

参考程序只接受整数向量和整数法向量，以 Python 整数精确判定正、负、零。这是可复核的给定配置执行器，没有把有限整数法向量称为连续各向同性抽样器。它对点积的运算次数仍是 $O(qd)$，大整数乘加的位成本另计。理论上的归一化不必在此真的求平方根，因为除以正的 $\Vert x{\Vert }_2$ 不改变符号。把实现换成浮点数时，溢出、消去和临近零的符号误判需要单独的数值策略，不能用本整数实验替它作保证。