A Deterministic Theory of Low Rank Matrix Completion
A Deterministic Theory of Low Rank Matrix Completion
复制标题
DOI：
10.1109/tit.2020.3019569
复制
发表时间：
2020-12-01
影响因子：
2.5
通讯作者：
Chatterjee, Sourav
中科院分区：
文献类型：
--
作者：
Chatterjee, Sourav
利用揭示条目的子集来完成大型低秩矩阵的问题在过去十年中受到了广泛的关注。本文的主要结果用图极限论的语言给出了具有任意缺失模式的矩阵补全问题序列渐近可解的一个充要条件。然后证明了对Candes-Recht核范数最小化算法的一个小修改，只要问题序列是渐近可解的，就提供了所需的渐近解。这个理论是完全确定的，没有随机假设。列出了一些悬而未决的问题。
The problem of completing a large low rank matrix using a subset of revealed entries has received much attention in the last ten years. The main result of this paper gives a necessary and sufficient condition, stated in the language of graph limit theory, for a sequence of matrix completion problems with arbitrary missing patterns to be asymptotically solvable. It is then shown that a small modification of the Candes-Recht nuclear norm minimization algorithm provides the required asymptotic solution whenever the sequence of problems is asymptotically solvable. The theory is fully deterministic, with no assumption of randomness. A number of open questions are listed.