标题： 谱扰动界限用于低秩逼近及其在隐私中的应用 显示英文标题

标题： Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

摘要： 机器学习中的一个核心挑战是理解噪声或测量误差如何影响低秩逼近，尤其是在谱范数下。 这个问题在差分隐私低秩逼近中尤为重要，其中目标是在保持数据生成矩阵的顶部-$p$结构的同时确保隐私。 先前的工作通常分析Frobenius范数误差或重建质量的变化，但这些指标可能会高估或低估真实的子空间失真。 相比之下，谱范数可以捕捉最坏情况下的方向误差，并提供最强的效用保证。 我们建立了对称矩阵的新高概率谱范数扰动界限，改进了经典的Eckart--Young--Mirsky定理，并明确捕捉了矩阵 $A \in \mathbb{R}^{n \times n}$ 与任意对称扰动 $E$ 之间的相互作用。 在适度的特征间隔和范数条件下，我们的界为$\|(A + E)_p - A_p\|$提供了精确的估计，其中$A_p$是$A$的最佳秩-$p$逼近，改进幅度可达因子$\sqrt{n}$。 作为应用，我们推导了差分隐私主成分分析的改进效用保证，解决了文献中的一个开放问题。 我们的分析依赖于复分析中的一种新颖的轮廓自举方法，并将其扩展到包括多项式和矩阵指数在内的广泛谱泛函类。 在真实数据集上的实验结果证实，我们的界在多种扰动条件下紧密跟踪实际的谱误差。 显示英文摘要

摘要： 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 spectral norm, by contrast, captures worst-case directional error and provides the strongest utility guarantees. We establish new high-probability spectral-norm perturbation bounds for symmetric matrices that refine the classical Eckart--Young--Mirsky theorem and explicitly capture interactions between a matrix $A \in \mathbb{R}^{n \times n}$ and an arbitrary symmetric perturbation $E$. Under mild eigengap and norm conditions, our bounds yield sharp estimates for $\|(A + E)_p - A_p\|$, where $A_p$ is the best rank-$p$ approximation of $A$, with improvements of up to a factor of $\sqrt{n}$. As an application, we derive improved utility guarantees for differentially private PCA, resolving an open problem in the literature. Our analysis relies on a novel contour bootstrapping method from complex analysis and extends it to a broad class of spectral functionals, including polynomials and matrix exponentials. Empirical results on real-world datasets confirm that our bounds closely track the actual spectral error under diverse perturbation regimes.