近似秩

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

这些误差口径不能互换。均方误差会把少数完全错误的格稀释掉，因此不够控制最坏输入。谱范数则是另一方向：误差矩阵 $E$ 满足 $\Vert E{\Vert }_{max}\le \Vert E{\Vert }_2$，所以未经维数归一化的谱范数界 $\Vert E{\Vert }_2\le \epsilon$ 已经蕴含逐项界，而且通常更强。例如 $N\times N$ 的全 $\epsilon$ 矩阵逐项最大值为 $\epsilon$，谱范数却是 $N\epsilon$。用谱范数替换逐项约束会改变可行近似矩阵，而不是得到同一个参数。

考虑

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

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

本页与Log-rank 猜想公理库Log-rank 猜想Log-rank conjecture · Lovász–Saks log-rank conjecture猜测总 Boolean 函数的确定性通信复杂度可由其实通信矩阵秩的对数的固定多项式上界控制。的对照在“精确/近似”和“上界/下界”两层都成立。它也不同于符号秩公理库符号秩Sign rank · Sign-pattern rank在所有严格实现同一正负号模式的实矩阵中取最低秩，并以此刻画无界错误通信的维度。：$\epsilon <1$ 的符号矩阵近似会保留符号并限制数值靠近 $\pm 1$；符号秩只要求正负号正确，幅值可任意且不得出现零。于是 $\mathrm{signrank}(S)\le {\mathrm{rank}}_{\epsilon }(S)$，反向无需成立。

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

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