近似秩 | Codeboy's Blog

形式陈述

对通信矩阵或任意实矩阵 $A\in\mathbb R^{X\times Y}$ 和 $\varepsilon\ge0$ ，先在本页定义逐项最大范数

\|A\|_{\max}=\max_{x\in X,y\in Y}|A_{xy}|.

这不是最大行绝对和的诱导 $\ell_\infty$ operator norm。 $A$ 的 $\varepsilon$ -近似秩是在逐项误差约束内寻找最低实秩，定义为

\operatorname{rank}_\varepsilon(A) =\min\{\operatorname{rank}_{\mathbb R}(B): B\in\mathbb R^{X\times Y},\ \|A-B\|_{\max}\le\varepsilon\}.

对 Boolean 通信矩阵常取常数 $0<\varepsilon<1/2$ ；对 $\{\pm1\}$ 符号矩阵则常取 $0<\varepsilon<1$ 。约束是每个格都满足 $|A_{xy}-B_{xy}|\le\varepsilon$ ，不是平均平方误差、谱范数误差或只在某个输入分布下高概率接近。显然 $\operatorname{rank}_0(A)=\operatorname{rank}(A)$ ，而放宽 $\varepsilon$ 只会使最优秩不增。

若成本为 $c$ 的私有币协议以最坏错误 $\delta$ 计算 Boolean 矩阵 $M_f$ ，其接受概率矩阵 $P$ 满足 $\|P-M_f\|_{\max}\le\delta$ 。每条接受 transcript 的概率因私有随机带独立而分解成 Alice 因子与 Bob 因子的外积，且接受 transcript 至多 $2^c$ 条，所以 $\operatorname{rank}(P)\le2^c$ ，从而

R^{\mathrm{pri}}_\delta(f)\ge \log_2\operatorname{rank}_\delta(M_f).

无纠缠量子协议也让接受概率矩阵逐格逼近目标，但通信量与该矩阵秩之间的指数换算不同，不能沿用上式的系数。public-coin 情形则需计入 Newman 转换的输入长度与误差损失；直接对公共币种子取平均可能提高秩，不能无条件照搬私有币证明。

直觉

精确秩要求低维矩阵逐格重建 $A$ ，一个很小的数值扰动也可能大幅改变秩。近似秩把“协议允许错误”翻译为接受概率可偏离 $0/1$ 目标：只要每格仍落在正确概率区间，就不必保留精确代数恒等式。它因此测量的是在统一逐项容差下需要多少潜在维度。

逐项约束不可换成整体范数。若只控制均方误差，一个巨大矩阵中少数完全错误的格会被平均稀释，但最坏错误协议恰好禁止这种格；若只控制谱范数，则误差可沿奇异方向集中，也不保证任何单格概率合法。

例子与边界

考虑

A=I_2= \begin{pmatrix}1&0\\0&1\end{pmatrix}, \qquad B=\frac12 \begin{pmatrix}1&1\\1&1\end{pmatrix}.

$B$ 的秩为 $1$ ，且 $\|A-B\|_{\max}=1/2$ 。因此 $\operatorname{rank}_{1/2}(I_2)=1$ ；当 $\varepsilon<1/2$ 时，不存在秩一近似。证明如下：若 $B=uv^{\mathsf T}$ 并且两条对角线都大于 $1/2$ 、两条非对角线绝对值都小于 $1/2$ ，则

|B_{11}B_{22}|>1/4, \quad |B_{12}B_{21}|<1/4,

却与秩一恒等式 $B_{11}B_{22}=B_{12}B_{21}$ 冲突。这个两阶证书同时说明阈值处可发生跳变。

本页与Log-rank 猜想的对照在“精确/近似”和“上界/下界”两层都成立。它也不同于符号秩： $\varepsilon<1$ 的符号矩阵近似会保留符号并限制数值靠近 $\pm1$ ；符号秩只要求正负号正确，幅值可任意且不得出现零。于是 $\operatorname{signrank}(S)\le\operatorname{rank}_\varepsilon(S)$ ，反向无需成立。

推论与应用

近似秩把协议下界变成非凸低秩近似问题：给出一个低秩 $B$ 是上界证书，证明所有低秩 $B$ 都有某格超出容差才是下界。张量、对偶多项式和分解范数可用于后一任务，但必须保持逐项误差口径。

它不是 bounded-error 通信的普遍精确刻画。以 Set Disjointness 为代表的函数可有远小于随机通信复杂度指数所暗示的近似秩，因此“低近似秩”本身不构造低通信随机协议。若改成分布平均误差、Frobenius 误差或诱导矩阵范数，就得到另一个参数，现有定理不能只靠符号 $\infty$ 相似而迁移。

参考资料

Matthias Krause, “Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing,” Theoretical Computer Science 156, 1996, pp. 99–117.
Harry Buhrman and Ronald de Wolf, “Communication Complexity Lower Bounds by Polynomials,” Proceedings of CCC, 2001, pp. 120–130.
Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif, “The Log-Approximate-Rank Conjecture Is False,” Journal of the ACM 67(4), 2020, Article 23.
Troy Lee and Adi Shraibman, Lower Bounds in Communication Complexity, Foundations and Trends in Theoretical Computer Science, 2009, Chapter 4.

形式陈述 ​

反向链接

形式陈述