Perturbation Bounds for Low-Rank Inverse Approximations under Noise¶

会议: NeurIPS 2025
arXiv: 2510.25571
代码: 无
领域: 数值线性代数 / 矩阵理论
关键词: 低秩近似, 伪逆, 扰动界, 谱范数, 特征间隙

一句话总结¶

首次给出在加性噪声下低秩逆近似 $\|(\tilde{A}^{-1})_p - A_p^{-1}\|$ 的非渐近谱范数扰动界，利用轮廓积分技术得到依赖特征间隙、谱衰减和噪声对齐的锐界，比经典全逆界改进高达 $\sqrt{n}$ 倍。

研究背景与动机¶

领域现状：低秩伪逆广泛用于加速 ML、优化和科学计算中的逆矩阵近似。经典扰动理论只针对全逆 $\|A^{-1} - \tilde{A}^{-1}\|$ 给出界。
核心矛盾：经典界忽略了截断到秩 p 的结构，不考虑噪声与特征间隙的交互，常给出过于悲观的估计。
核心idea：用轮廓积分技术对非全函数 $f(z) = 1/z$ 进行局部 resolvent 展开，在最小特征值附近精确控制 Riesz 投影的扰动。

方法详解¶

问题建模¶

给定 $n \times n$ 实对称正定矩阵 $A$，特征值 $\lambda_1 \geq \cdots \geq \lambda_n > 0$，对称扰动 $E$，则 $\tilde{A} = A + E$。研究的核心量是：$\|(\tilde{A}^{-1})_p - A_p^{-1}\|$，其中 $A_p^{-1} = \sum_{i=n-p+1}^{n} \lambda_i^{-1} u_i u_i^\top$ 是 $A^{-1}$ 的最佳秩-$p$ 近似。

关键结果¶

主定理 (Theorem 2.1)：在 $4\|E\| \leq \min\{\lambda_n, \delta_{n-p}\}$ 条件下： $$\|(\tilde{A}^{-1})_p - A_p^{-1}\| \leq 5\left(\frac{\|E\|}{\lambda_n^2} + \frac{\|E\|}{\lambda_{n-p} \delta_{n-p}}\right)$$ 其中 $\delta_{n-p} = \lambda_{n-p} - \lambda_{n-p+1}$ 是特征间隙
与经典界的对比：经典EYM-N界为 $\frac{8\|E\|}{3\lambda_n^2} + \frac{2}{\lambda_{n-p}}$，其第二项不随 $\|E\| \to 0$ 消失——即使无噪声也给出非零误差！本文的界在 $\|E\| \to 0$ 时正确地趋于零

技术贡献¶

轮廓积分技术扩展：从全函数（如矩阵指数 $e^z$）扩展到非全函数 $f(z) = 1/z$
局部化 resolvent 展开：围绕最小特征值构造 Cauchy 轮廓，放大利用随局部谱结构变化的信息
Riesz 投影扰动控制：精确控制噪声对低曲率子空间特征投影的影响
扩展到一般对称矩阵：含秩不足的情况（通过伪逆）

应用：PCG 收敛率改进¶

通过本文的界可为低秩+正则化预条件子的 PCG 方法得到更紧的条件数估计，可证明地改进 $n^{1/4}$ 倍的迭代次数保证。

实验关键数据¶

主实验¶

矩阵类型	本文界的跟踪误差	经典界的跟踪误差
样本协方差	小常数因子	1-2个数量级高估
离散化椭圆算子	小常数因子	1-2个数量级高估
BCSSTK09 刚度	小常数因子	1-2个数量级高估

噪声条件可行性验证¶

在 1990 US Census 协方差和 BCSSTK09 刚度矩阵上验证，安全裕量远超差分隐私和结构工程中的常见噪声水平。

亮点与洞察¶

低秩逆近似可以比全逆更鲁棒——只要特征间隙足够大。这与直觉相反（截断通常被认为引入额外误差）
谱感知的扰动界在实际中远比最坏情况界有用，因为它利用了矩阵的谱结构信息
PCG 方法的收敛率可用此界改进 $n^{1/4}$ 倍，具有直接的算法应用价值
技术上，将轮廓积分从全函数扩展到非全函数是非平凡的数学贡献

局限性 / 可改进方向¶

噪声条件 $4\|E\| < \min\{\lambda_n, \delta_{n-p}\}$ 在某些场景可能较强
仅考虑谱范数，Frobenius 范数界待发展
结构化噪声（如低秩扰动）可能得到更紧的界

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个低秩逆扰动的非渐近谱范数界，填补重要空白
实验充分度: ⭐⭐⭐⭐ 多种真实和合成矩阵验证，界跟踪精度高
写作质量: ⭐⭐⭐⭐⭐ 严谨流畅，证明结构清晰
价值: ⭐⭐⭐⭐⭐ 对数值计算/ML优化有基础性贡献