Matrix Completion from Noisy Entries
Matrix Completion from Noisy Entries
复制标题
DOI：
10.5555/1756006.1859920
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Raghunandan H. Keshavan;A. Montanari;Sewoong Oh
中科院分区：
文献类型：
--
作者：
Raghunandan H. Keshavan;A. Montanari;Sewoong Oh
给定一个低秩矩阵\(M\)，我们考虑从其少量随机子集元素的含噪观测值中对其进行重构的问题。这个问题出现在从协同过滤（“网飞问题”）到运动恢复结构和定位等多种应用中。我们研究了在[1]中引入的一种低复杂度算法，它基于谱技术和流形优化的组合，在此我们称之为OPTSPACE。我们证明了在多种情况下具有最优阶的性能保证。
Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the 'Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here OPTSPACE. We prove performance guarantees that are order-optimal in a number of circumstances.