分析噪声下低秩逆近似的误差,给出更精准的误差边界。
Perturbation Bounds for Low-Rank Inverse Approximations under Noise
- 用轮廓积分法分析噪声对低秩矩阵逆近似的影响。
- 误差与特征值间隔、谱衰减及噪声方向相关,可小至原估计的1/√n。
- 适用于需要高精度矩阵逆的机器学习与科学计算场景。
低秩伪逆广泛用于大规模机器学习、优化和科学计算中的矩阵逆近似。然而真实世界矩阵常受采样、随机投影和量化等噪声影响。目前对低秩逆近似在谱范数下的鲁棒性理解仍不充分。本文系统研究了 $n imes n$ 对称矩阵 $A$ 在噪声 $ ilde{A} = A + E$ 下的谱范数误差 $igackslashackslash ( ilde{A}^{-1})_p - A_p^{-1} igackslashackslash$,其中 $A_p^{-1}$ 是 $A^{-1}$ 的最优秩-$p$ 近似。在噪声假设较弱的前提下,推导出精确的非渐近扰动界,揭示误差如何依赖于特征值间隔、谱衰减以及噪声与 $A$ 低曲率方向的对齐情况。分析首次将轮廓积分技术应用于非整函数 $f(z) = 1/z$,所得边界相比经典全逆结果的简单推广可改进达 $igackslashackslash ext{sqrt}{n}igackslashackslash$ 倍。实验表明,该边界在多种真实与合成矩阵上均能紧密追踪实际误差,而传统方法常严重高估。研究为噪声环境中低秩逆近似提供了实用、谱感知的保证。
原文摘要 · Abstract (English)
Low-rank pseudoinverses are widely used to approximate matrix inverses in scalable machine learning, optimization, and scientific computing. However, real-world matrices are often observed with noise, arising from sampling, sketching, and quantization. The spectral-norm robustness of low-rank inverse approximations remains poorly understood. We systematically study the spectral-norm error $\| (\tilde{A}^{-1})_p - A_p^{-1} \|$ for an $n\times n$ symmetric matrix $A$, where $A_p^{-1}$ denotes the best rank-\(p\) approximation of $A^{-1}$, and $\tilde{A} = A + E$ is a noisy observation. Under mild assumptions on the noise, we derive sharp non-asymptotic perturbation bounds that reveal how the error scales with the eigengap, spectral decay, and noise alignment with low-curvature directions of $A$. Our analysis introduces a novel application of contour integral techniques to the \emph{non-entire} function $f(z) = 1/z$, yielding bounds that improve over naive adaptations of classical full-inverse bounds by up to a factor of $\sqrt{n}$. Empirically, our bounds closely track the true perturbation error across a variety of real-world and synthetic matrices, while estimates based on classical results tend to significantly overpredict. These findings offer practical, spectrum-aware guarantees for low-rank inverse approximations in noisy computational environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。