符号秩 | Codeboy's Blog

形式陈述

取有限非空 $X,Y$ ，令 $S\in\{\pm1\}^{X\times Y}$ 是函数的符号通信矩阵。符号秩是在所有严格同号实现中寻找最低实秩，定义为

\operatorname{signrank}(S) =\min\{\operatorname{rank}_{\mathbb R}(A): A\in\mathbb R^{X\times Y},\ S_{xy}A_{xy}>0\ \forall(x,y)\}.

不等式必须严格，因此合法 $A$ 没有零条目，也无需另选 $\operatorname{sign}(0)$ 的 convention。若最优秩为 $r$ ，可分解 $A=UV^{\mathsf T}$ ，把第 $x$ 行和第 $y$ 行记作 $u_x,v_y\in\mathbb R^r$ ，则

S_{xy}=\operatorname{sign}\langle u_x,v_y\rangle.

所以符号秩也等于用 $r$ 维原点超平面严格分离每行正负列集合所需的最小维数。所有秩和内积均在实数上；模二秩没有正负次序，不能替代。

Paturi–Simon 定理给出

\operatorname{UPP}^{\mathrm{cc}}(S) =\log_2\operatorname{signrank}(S)+O(1),

其中 UPP 是私有币、逐输入成功概率严格大于 $1/2$ 的无界错误模型。加性常数来自一向协议化与索引/符号 bit，不能把该式改写成无 convention 的字面相等；镜像关系由无界错误通信复杂度页补全协议方向。

直觉

符号秩丢弃数值幅度，只保留每格在零的哪一侧。协议的优势可以极小：接受概率是 $1/2+10^{-100}$ 仍算正确，因此决定输出的正是“偏置的符号”，而非它离 $1/2$ 多远。把偏置矩阵中心化后，合法协议产生一个与 $S$ 同号的低秩实矩阵。

几何上，每个 Alice 输入给出点 $u_x$ ，每个 Bob 输入给出法向量 $v_y$ ；内积的正负决定答案。低符号秩表示同一组低维超平面能同时实现整张通信矩阵的分类模式。

例子与边界

取 XOR 的符号矩阵

S= \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix} = \begin{pmatrix}1\\-1\end{pmatrix} \begin{pmatrix}1&-1\end{pmatrix}.

这个显式外积秩为 $1$ 且无零条目，故 $\operatorname{signrank}(S)=1$ 。相反，矩阵

T=\begin{pmatrix}1&1\\1&-1\end{pmatrix}

不可能有秩一同号实现：秩一矩阵满足 $A_{11}A_{22}=A_{12}A_{21}$ ，左边应为负、右边应为正，矛盾；而 $T$ 自身实秩为 $2$ ，故符号秩恰为 $2$ 。这是一份可复算的最小下界证书。

与近似秩相比，符号秩允许任意小正间隔。例如把 $T$ 的某个合法实现条目缩到 $10^{-100}$ 不影响符号秩，却会破坏固定 $\varepsilon<1$ 的逐项近似要求。若允许 $A_{xy}=0$ 再随意规定其符号，上述严格分离和 UPP 偏置都会失效。

推论与应用

符号秩下界可由几何、谱缩放或组合符号模式证明，并立即转成 UPP 通信下界。Forster 的缩放方法例如把符号矩阵的谱范数与维数联系起来，从而为 Hadamard 型模式给出高符号秩。

在相同私有币模型、相同输出约定下，每个错误率至多 $\varepsilon<1/2$ 的协议也都是 UPP 协议，因此

R^{\mathrm{priv}}_\varepsilon(S)\ge\operatorname{UPP}^{\mathrm{cc}}(S) =\log_2\operatorname{signrank}(S)+O(1).

所以 UPP 下界可以传递为 bounded-error 下界。不能免费传递的是上界：低符号秩只保证一个可能具有极小优势的低通信协议，将其优势放大到常数要付出依赖偏置的重复成本。公币协议属于另一模型，不能直接代入这个包含关系。

符号秩也不是精确实秩：允许在不穿过零的前提下移动条目，秩可能显著下降。使用结论时仍须报告符号编码、实数域、严格非零和 coin 口径。

参考资料

Ramamohan Paturi and Janos Simon, “Probabilistic Communication Complexity,” Journal of Computer and System Sciences 33(1), 1986, pp. 106–123.
Jürgen Forster, “A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity,” Journal of Computer and System Sciences 65(4), 2002, pp. 612–625.
Nati Linial and Adi Shraibman, “Learning Complexity versus Communication Complexity,” Combinatorics, Probability and Computing 18, 2009, pp. 227–245.