在仅有少量观测且存在噪声的情况下，实现低秩矩阵的精确恢复。
Fast exact recovery of noisy matrix from few entries: the infinity norm approach
- 基于无穷范数设计新算法，仅需低秩、非相干和足够采样三个基本假设。
- 首次在无额外谱条件约束下实现噪声环境中的精确恢复。
- 提出全新的轮廓积分分析方法，适用于理论研究者。
矩阵恢复问题是数据科学与理论计算机科学的核心问题，目标是从少量观测值中重建矩阵 $A$。一般情况下该任务不可行，但在满足三个基本假设时——矩阵秩远小于其维度（低秩）、奇异向量分布均匀（非相干）、采样量充足——可多项式时间内以高概率实现精确恢复。已有算法包括凸优化（Candes, Tao, Recht, 2009）、交替投影（Hardt & Wooters, 2014）和梯度下降低秩逼近（Keshavan et al., 2009, 2010）。然而在实际应用中数据常含噪声，现有方法仅能提供近似恢复，且难以转为精确解。近期研究（Abbe et al., 2017；Bhardwaj et al., 2023）表明，在矩阵具有有界精度的前提下，通过无穷范数逼近可实现精确恢复，但需额外假设：矩阵条件数小或相邻奇异值间距大。本文移除了这些额外谱假设，提出了首个仅依赖三个基本假设即可在噪声下实现精确恢复的简单算法。为此，引入一种全新的轮廓积分分析方法，与以往技术完全不同，可能具有独立研究价值。
原文摘要 · Abstract (English)
The matrix recovery (completion) problem, a central problem in data science and theoretical computer science, is to recover a matrix $A$ from a relatively small sample of entries. While such a task is impossible in general, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, from a random subset of entries, under three (basic and necessary) assumptions: (1) the rank of $A$ is very small compared to its dimensions (low rank), (2) $A$ has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. There are many different algorithms for the task, including convex optimization by Candes, Tao and Recht (2009), alternating projection by Hardt and Wooters (2014) and low rank approximation with gradient descent by Keshavan, Montanari and Oh (2009, 2010). In applications, it is more realistic to assume that data is noisy. In this case, these approaches provide an approximate recovery with small root mean square error. However, it is hard to transform such an approximate recovery to an exact one. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) concerning approximation in the infinity norm showed that we can achieve exact recovery even in the noisy case, given that the ground matrix has bounded precision. Beyond the three basic assumptions above, they required either the condition number of $A$ is small (Abbe et al.) or the gap between consecutive singular values is large (Bhardwaj et al.). In this paper, we remove these extra spectral assumptions. As a result, we obtain a simple algorithm for exact recovery in the noisy case, under only the three basic assumptions. This is the first such algorithm. To analyse this algorithm, we introduce a contour integration argument which is totally different from all previous methods and may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。