Near-Optimal Bounds for Sketching the Schatten--1 Norm
Lin F. Yang
cs.DS, cs.CC, math.ST
2026-08-23
任意 n×n 实矩阵核范数的常数因子线性素描需要平方级测量：下界只少 polylog，上界大约少一个对数，多项式压缩不可能，此前夹在线性与整矩阵之间。
核范数（nuclear / Schatten–1）是矩阵奇异值之和。问题设定很干净：事先抽一个随机线性映射 S，把 n×n 实矩阵 A 压成 k 个实数 S(A)，再解码出 (1±ε) 倍的 ||A||{S1}。对每一个固定的 A，成功概率至少 2/3。线性映射在看到 A 之前就抽好，对所有输入共用。
如果事先承诺 A 半正定，核范数等于迹，测一次就够。向量的 ℓ1 范数也早就有与维度无关的 polylog 素描。矩阵这边卡住，是因为改一个条目会牵动全部奇异值，而左右奇异方向事先都不知道。
Li、Nguyễn、Woodruff 把这个问题钉在「一般线性素描」模型里。会议版给出 Ω(√n) 下界，期刊版抬到 Ω(n)，上界一直是把整张矩阵存下来的 O(n²)。正确复杂度落在这条多项式缝里的哪一段，一直没人收口。这篇几乎把它收了。
下界对所有 rank-k 线性测量和所有可测解码器同时成立。做法是造两族随机矩阵：核范数差一个固定相对量，但任何 k 维投影几乎分不开它们。能估核范数就能给这两族贴标签，分不开就说明估不出来。
标量层先造两个分布。把 x 看成平方奇异值，则 x^q 控偶数阶谱矩，√x 进核范数。两个分布的 0 到 K 阶矩完全一样，√x 的期望差一个相对缺口。K 取约 (1/100) log n / log log n。原子概率一般不是 1/n 的倍数，还不能直接当矩阵谱。论文用 Steinitz 重排加控制粒子，把它们改成 n 个等权粒子，并连成一条路上每一步都保持前 K 阶矩不变的路径。左右奇异向量独立抽 Haar 正交阵，再加一小点高斯噪声，让观测密度可微。
沿路径用 Fisher 信息积分控总变差。前 2K 阶张量因为矩匹配全部消掉，第一个活下来的是奇数阶 m=2K+1。一条奇数阶随机旋转引理说明，rank-k 投影最多只能看见大约 (k/n²)^{K+1} 的能量。K 那么大时，k ≤ n²/(log n)^{Aε} 就分不开。
上界用四块事先抽好的高斯矩阵积：GA、WA、AR₀、YA。解码器在存下来的数据上挑谱截断。头部是少数大奇异值对应的未知子空间，尾部要求 stable rank 够大：能量没有堆在单个方向上。头用一次高斯回归直接估核范数，不用把 A 重建出来。尾把 √x 用约 log n / log log n 次多项式逼近，再用高斯圈统计无偏估各阶功率和。头的代价大约 n² log b / b，尾大约 n^{2-c/b} poly(b)，在 b ≍ log n / log log n 处对上。截断全在解码器里选，四块映射本身是固定线性的。
主定理：对每个固定 0<ε<1，存在只依赖 ε 的常数 Aε、Cε，使得充分大的 n 满足
n² / (log n)^{Aε} ≤ kε(n) ≤ Cε n² {log log(e^e n)}² / log(e n)
| 工作 | 模型 | 下界 | 上界 |
| Li–Nguyễn–Woodruff 会议版 | 一般线性 | Ω(√n) | O(n²) |
| 同上期刊版 | 一般线性 | Ω(n) | O(n²) |
| 本篇 | 一般线性 | n²/(log n)^{Aε} | Oε(n² (log log n)² / log n) |
多项式缝被收成 polylog 缝。对每个固定 c>0，O(n^{2-c}) 次测量不可能。上界相对存整张矩阵大约省下 log n / (log log n)² 倍。上界算法把失败概率各分 1/100 给协方差、Frobenius、头回归和尾估计，联合成功至少 0.96；相对误差参数取 α=ρ=η=ε/20，总误差不超过 2ε/5。
半正定输入仍然是一次测量。这篇管的是任意实方阵。
如果核范数只是矩阵补全、低秩模型里的凸代理，这篇给的不是一个能直接跑的压缩算法。它钉的是测量学事实：在「事先固定线性测量、精确实数算术、对所有矩阵都要 (1±ε)」这条最干净的规则下，核范数几乎不能被压。向量 ℓ1 那种与维度脱钩的素描，在这里不存在。
能省的只有 polylog。对本来就要存整张 n×n 矩阵的人来说，这点节省通常换不来一套复杂解码器。解码器的计算代价也不在这个模型里。
该带走的分界是：障碍不在「把奇异值加起来」，而在左右方向都未知时还要把它们加起来。矩阵一旦半正定、稀疏、按行到达、或允许多遍扫描，已有文献可以走完全不同的空间。双线性素描（存 SAT 那种）此前就有接近线性的下界，这篇没有重做那条线。
对数缝还在。下界是 n²/(log n)^{Aε}，指数依赖 ε；上界是 Oε(n² (log log n)² / log n)。最优的 log n 次数没钉死，也不排除再叠一层 log log。ε 是先固定再让 n 变大的，n 与 ε 的联合依赖没做。
模型是精确实数线性测量，不是有限比特流。不能翻译成「任意流算法需要 n^{2-o(1)} 比特」：Li–Nguyễn–Woodruff 的 turnstile 线性化定理管的是可达状态数的对数，不是素描行数。有限内存这边目前最强的仍是稀疏有界整数矩阵上、非偶数 Schatten 幂（含 p=1）的近线性比特下界。两条下界互补，不能直接比。
上界也不是图灵机算法。高斯系数是实数，存的是精确实数，解码工作内存不计。要落到有限精度，还得离散化随机映射、控截断/回归/矩估计的舍入，并给每个测量分配比特数 b。这篇只钉了 k，没钉 b。矩形矩阵、复矩阵、更新时间、解码时间、数值稳定性都没覆盖。
脚注写明全文用 GPT-5.6-sol 辅助撰写。证明链写得很完整，常量未优化，也没有数值实验。