矩阵求逆首个无条件归约;行列式阈值在部分有限域降到 4.4%

Worst-Case to Average-Case Reductions for Basic Linear Algebra

Or Zamir

cs.DS, cs.CC

2026-11-02

矩阵求逆的首个无条件最坏情形到平均情形归约:随机可逆矩阵上任意常数成功率的算法,可导出同指数的最坏情形算法

这篇在解决什么

矩阵乘法有一条 1993 年的经典结论:Blum、Luby、Rubinfeld 证明,能对超过 75% 的矩阵对算对乘积的算法,可以转成以几乎相同运行时间对付任意矩阵对的算法,后续工作把 75% 压到任意正常数。缺口在求逆、解线性方程组、求秩、求行列式这边:它们在最坏情形下都与矩阵乘法计算等价,却一直没有同类归约。卡点也很具体,经典归约产生的中间矩阵高度结构化,只对均匀随机输入可靠的算法在这些矩阵上没有任何保证。Vaikuntanathan 与 Zamir 前不久用 trapdoor matrices 补上缺口,代价是押在 LPN 这类密码学假设上。这篇回答两件事:假设能不能去掉;平均成功率要多高才够。

方法

求逆的无条件归约分两层。

第一层处理成功率接近 1 的情形,核心是一个新恒等式。随机采样 R,先求 R⁻¹ 与 (I−R)⁻¹,把目标乘积 BC 嵌进两个 2n×2n 分块矩阵,前后共六次求逆调用,再用两个互补的 Schur complement(分块求逆时对其余块的修正量)拼出 BC = BRC + B(I−R)C。要点在于:只要 A、A′、R 均匀随机,这六次调用的输入在可逆条件下也各自均匀随机,平均情形算法恰好覆盖。得到的平均情形乘法再走 BLR 老路,随机平移加 Freivalds 检验,升级成最坏情形算法。

第二层把任意常数成功率 ε 放大上去。反复加秩一扰动 A → A + uvᵀ,Sherman–Morrison/Woodbury 恒等式保证扰动前后的逆可以廉价互相换算;傅里叶分析显示这条随机游走带谱隙,走 O(log(1/ε)) 步之后,扰动矩阵在任何有界检验眼里都与均匀矩阵无差别。放大开销对 1/ε 近似线性,论文证明这个依赖是最优的。

条件性部分依赖 trapdoor matrices:伪随机矩阵,持有秘密 trapdoor 就能近线性时间算矩阵向量乘。一个观察顶了大用:任何这类族都自带近二次时间的行列式与单个方程组求解(走 Wiedemann 方法配 Berlekamp–Massey),于是此前需要更专门密码学假设的行列式阈值,在通用假设下就能拿到。剩余归约靠「秩轮廓」:比较算法在随机指定秩矩阵与加掩目标矩阵上的输出分布,平均算法只要比常数答案好 ε,某个秩层面的统计差异必然暴露目标是否可逆。

结果

平均情形成功率换到的最坏情形能力假设
求逆,任意常数 ε矩阵乘法,进而求逆无条件
可逆性,比 max{s,1−s} 高 ε可逆性判定、精确秩trapdoor
行列式,比 s 高 ε秩与可逆性trapdoor
可逆输入上比 1/(q−1) 高 ε行列式模一个阶 < min{q−1, 2/ε} 的子群trapdoor
F₂₀₄₈ 上 0.044+ε精确行列式trapdoor

s 是均匀随机矩阵奇异的概率,不超过 1/(q−1)。可逆性与秩的阈值已到最优,只要求比「永远输出最常见答案」的平凡算法好一点。求逆定理本身:运行 T(m) 的算法只要成功率 ≥ ε,任意 n×n 矩阵对都能以高概率在 Õε(T(2n)) 内乘出,维度翻倍,指数不动。行列式的精确计算阈值降到 s + (1−s)/ℓ + ε(ℓ 是 q−1 的最小素因子),此前所有充分阈值都超过 1/2;取 q = 2^r(r 为奇素数)还能得到无限多个阈值 O(1/log q) 的域,要多小有多小。

为什么重要

对做机器学习的人,这是概念校准:随机输入上的平均表现,什么条件下能兑换成最坏情形保证?线性代数恰好是大规模计算和 ML 的底座,求逆现在有了无条件答案,兑换门槛低到常数成功率。也要说清楚,这是纯复杂度理论工作,不会改变你明天编译的任何 kernel,价值在于是非题被逐个关闭:求逆无条件解决,秩与可逆性到最优阈值,行列式卡在子群模糊这道坎。论文还在致谢里披露,公开 AI 工具被大量用作试方向、补技术空白的加速器,核心思路与最终定稿来自作者本人。

局限与存疑

作者在讨论一节自己列了三条。行列式绕不开乘法掩码的子群模糊,一个把 det(A) 与 −det(A) 混着返回、成功率仍高于 1/2 的算法,现有技术分不开,这和「可逆性 oracle 能否推出行列式」的开放问题绑死。秩、可逆性、行列式的归约全部押在 trapdoored matrices 的存在性上(LPN、McEliece 型假设),去掉假设仍开放;解单个线性方程组 Ax=b 的无条件归约同样没解决。还有个容易误读的细节:阈值任意小的结论要先固定那个域,并假设其上存在相应 trapdoor 族。全文最扎实的是无条件求逆归约,证明链完整;条件性结果的分量,取决于你对 trapdoor 假设的信心。

术语

原文与代码

社区讨论

相关论文

全部论文解读