提出新方法RGNMR，能用少量数据准确恢复被污染的低秩矩阵
RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees
- 基于高斯-牛顿迭代与异常值剔除，简单高效地完成矩阵补全
- 理论证明可精确恢复低秩矩阵，且对小样本、过参数化均鲁棒
- 适合处理数据少、噪声多或病态条件下的矩阵补全任务
从部分观测条目中恢复一个低秩矩阵，其中一些条目可能被污染，称为鲁棒矩阵补全（RMC）问题。现有方法存在诸多局限：需要较多观测条目；在过参数化情况下（假设秩高于真实值）可能失败；难以恢复轻微病态的矩阵。本文提出一种新方法RGNMR，克服上述限制。RGNMR是一种基于因子分解的迭代算法，结合高斯-牛顿线性化与疑似异常值条目的剔除策略。理论上，在合理假设下，我们证明RGNMR可保证精确恢复底层低秩矩阵，其理论结果优于当前最先进因子分解类方法。实验表明，RGNMR在多种模拟场景中显著优于现有方法，尤其在观测条目稀少、秩假设过高及矩阵病态等条件下仍具强鲁棒性。
原文摘要 · Abstract (English)
Recovering a low rank matrix from a subset of its entries, some of which may be corrupted, is known as the robust matrix completion (RMC) problem. Existing RMC methods have several limitations: they require a relatively large number of observed entries; they may fail under overparametrization, when their assumed rank is higher than the correct one; and many of them fail to recover even mildly ill-conditioned matrices. In this paper we propose a novel RMC method, denoted $\texttt{RGNMR}$, which overcomes these limitations. $\texttt{RGNMR}$ is a simple factorization-based iterative algorithm, which combines a Gauss-Newton linearization with removal of entries suspected to be outliers. On the theoretical front, we prove that under suitable assumptions, $\texttt{RGNMR}$ is guaranteed exact recovery of the underlying low rank matrix. Our theoretical results improve upon the best currently known for factorization-based methods. On the empirical front, we show via several simulations the advantages of $\texttt{RGNMR}$ over existing RMC methods, and in particular its ability to handle a small number of observed entries, overparameterization of the rank and ill-conditioned matrices.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。