A Simpler Approach to Matrix Completion
A Simpler Approach to Matrix Completion
复制标题
DOI：
10.5555/1953048.2185803
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
B. Recht
中科院分区：
文献类型：
--
作者：
B. Recht
本文给出了迄今为止关于重构一个未知低秩矩阵所需随机采样元素数量的最佳界限。这些结果改进了坎德斯和赖希特（2009年）、坎德斯和陶（2009年）以及凯沙万等人（2009年）之前的工作。重构是通过在与所提供元素一致的条件下最小化隐藏矩阵的核范数（即奇异值之和）来实现的。如果基础矩阵满足一定的不相干性条件，那么所需元素的数量等于一个二次对数因子乘以奇异值分解中的参数数量。这一论断的证明简短、自成一体，并且使用了非常基础的分析方法。这里的新颖技术基于量子信息理论的近期研究成果。
This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low-rank matrix. These results improve on prior work by Candes and Recht (2009), Candes and Tao (2009), and Keshavan et al. (2009). The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.