Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
Phuc Tran and Nisheeth K. Vishnoi and Van H. Vu
机器学习的一个核心挑战是了解噪声或测量误差如何影响低等级近似值,特别是在光谱规范中。 这个问题在差异式私有低等级近似值中尤其重要,其中一个旨在保留数据派生矩阵的顶p结构,同时确保隐私。 之前的工作经常分析Frobenius规范错误或重建质量的变化,但这些指标可能会过度或低估真正的子空间失真。 相比之下,光谱规范捕获了最坏情况的方向性错误,并提供了最强的实用保证。 我们为对称矩阵建立了新的高概率光谱-规范扰动边界,这些矩阵完善了经典的Eckart-Young-Mirsky定理,并明确地捕获矩阵A ∈R^n × n和任意对称扰动E之间的相互作用。 在温和的特征差距和规范条件下,我们的边界产生了对(A + E)_p - A_p的尖锐估计,其中A_p是A的最佳排名近似值,改进幅度高达√(n)。 作为应用程序,我们获得了改进的实用保证,用于差异私有PCA,解决了文献中的一个开放问题。 我们的分析依赖于复杂的分析中的一种新颖的轮廓引导方法,并将其扩展到广泛的光谱功能,包括多项式和矩阵指数。 现实世界数据集的实证结果证实,我们的边界密切跟踪不同扰动机制下的实际光谱误差。
A central challenge in machine learning is to understand how noise or measurement errors affect low-rank approximations, particularly in the spectral norm. This question is especially important in differentially private low-rank approximation, where one aims to preserve the top-p structure of a data-derived matrix while ensuring privacy. Prior work often analyzes Frobenius norm error or changes in reconstruction quality, but these metrics can over- or under-estimate true subspace distortion. The...